“栈”数据的实现 数据抽象和封装途径 ·定义栈数据类型 const int STACK SIZE=100; class Stack public:/对外的接口（外部可使用的内容） Stack(); void push(int i); void pop(int &i); private:/隐藏的内容，外部不可使用 int top; int buffer[STACK SIZE]; };
“栈”数据的实现 －－数据抽象和封装途径 ◼ 定义栈数据类型 const int STACK_SIZE=100; class Stack { public: //对外的接口（外部可使用的内容） Stack(); void push(int i); void pop(int &i); private: //隐藏的内容，外部不可使用 int top; int buffer[STACK_SIZE]; };
void Stack:push(int i) if (top =STACK_SIZE-1) cout <"Stack is overflow.\n"; exit(-1); } else { top++;buffer[top]i; return; Stack:Stack() {top=-1; void Stack:pop(int &i) if (top =-1) {cout≤<“Stack is empty.n", exit(-1); ) else i buffer[top];top--; return;
void Stack::push(int i) { if (top == STACK_SIZE-1) { cout << “Stack is overflow.\n”; exit(-1); } else { top++; buffer[top] = i; return; } } void Stack::pop(int &i) { if (top == -1) { cout << “Stack is empty.\n”; exit(-1); } else { i = buffer[top]; top--; return; } } Stack::Stack() { top = -1; }
·使用栈类型数据 Stack st;/会自动地去调用st.Stack()对st进行初始化。 int x; st.push(12);/把12放进栈st。 st.pop(x);/把栈J顶元素退栈并存入变量x。 st.top =-1;//Error st.top++;//Error st.buffer[st.top]12;//Error st.f();//Error 数据表示发生变化不会影响使用者！
◼ 使用栈类型数据 Stack st; //会自动地去调用st.Stack()对st进行初始化。 int x; st.push(12); //把12放进栈st。 ...... st.pop(x); //把栈顶元素退栈并存入变量x。 ...... st.top = -1; //Error st.top++; //Error st.buffer[st.top] = 12; //Error st.f(); //Error ◼ 数据表示发生变化不会影响使用者！
“栈”数据的另一种实现（链表） 一一数据抽象和封装途径 class Stack public: Stack(); void push(int i); void pop(int &i); private: struct Node int content; Node *next; *top; top 31 a2 an NULL
“栈”数据的另一种实现（链表） －－数据抽象和封装途径 class Stack { public: Stack(); void push(int i); void pop(int &i); private: struct Node { int content; Node *next; } *top; }; top a1 a2 an NULL
void Stack:push(int i) Node *p=new Node; if (p =NULL) cout <"Stack is overflow.\n"; exit(-1); ) else { p->content i; p->next top;top p; Stack:Stack() return; top NULL; } void Stack:pop(int &i) if (top =NULL) { cout <"Stack is empty.\n"; exit(-1); else 改变栈类型数据的表示对 { Node *p=top; 使用者没有影响！ top top->next; i p->content; Stack st; delete p; int x; return; st.push(12); st.pop(x);
void Stack::push(int i) { Node *p=new Node; if (p == NULL) { cout << "Stack is overflow.\n"; exit(-1); } else { p->content = i; p->next = top; top = p; return; } } void Stack::pop(int &i) { if (top == NULL) { cout << "Stack is empty.\n"; exit(-1); } else { Node *p=top; top = top->next; i = p->content; delete p; return; } } • 改变栈类型数据的表示对 使用者没有影响！ Stack st; int x; st.push(12); st.pop(x); Stack::Stack() { top = NULL; }