栈是应用较广的一种数据结构，分为链栈和顺序栈。
链栈的实现：
#include <iostream> using namespace std; struct node { int data; node *next; }; node *top; void push(int x) { node *n=new node; n->data=x; n->next=top; top=n; } void pop() { if(top==NULL) { cout<<"no elements"<<endl; } else { node *p=top; cout<<"delete:"<<top->data<<endl; top=top->next; delete p; } } void show() { node *n=top; while(n!=NULL) { cout<<n->data<<endl; n=n->next; } } int main() { int ch, x; do { cout << "\n1. Push"; cout << "\n2. Pop"; cout << "\n3. Print"; cout << "\nEnter Your Choice : "; cin >> ch; if (ch == 1) { cout << "\nInsert : "; cin >> x; push(x); } else if (ch == 2) { pop(); } else if (ch == 3) { show(); } } while (ch != 0); return 0; }
顺序栈的实现：
#include <iostream> using namespace std; int *stack; int top=0; void push(int x,int size) { if(top==size) { cout<<"overflow"<<endl; } else { stack[top++]=x; } } void pop() { if(top==0) { cout<<"no elements"<<endl; } else { cout<<stack[--top]<<"deleted"<<endl; } } void show() { for(int i=0;i<top;i++) { cout<<stack[i]<<endl; } } void topmost() { if(top==0) { cout<<"no elements"<<endl; } else { cout<<"top elements:"<<stack[top-1]<<endl; } } int main() { int size; cout<<"enter the stack‘s size"<<endl; cin>>size; stack=new int[size]; int ch,x; do { cout<<"1.push"<<endl; cout<<"2.pop"<<endl; cout<<"3.show"<<endl; cout<<"4.show top"<<endl; cout<<"enter your choice"<<endl; cin>>ch; if(ch==1) { cout<<"\ninsert:"; cin>>x; push(x,size); } else if (ch==2) { pop(); } else if(ch==3) { show(); } else if(ch==4) { topmost(); } }while(ch!=0); return 0; }
栈是一种先入后出的数据结构（LIFO），栈主要对一端进行操作，栈的实现主要是通过一个top指针，出栈和入栈都是通过top指针来进行操作的，对于链栈，入栈时先申请节点，将所需入栈的值赋给节点，再将原先的top指针指向下一个指针，新申请的节点成为新的top；出栈时，将top节点赋给一个新申请的节点，top指向下一个节点，然后删除原先的top节点。对于顺序栈，需要定义其数组的大小，当数组的元素满了时，便不能继续添加元素了，入栈时，将入栈元素赋给stack数组的第top个元素（stack[top]），然后top+1，指向栈顶；出栈时，将栈顶的数组元素删除，即stack[--top]。需要注意的是，对于顺序栈，top指向的是栈顶后面的空元素，栈顶的元素是stack[top-1]，而链栈中的top指针指向的直接就是栈顶的元素。
原文：https://www.cnblogs.com/ztzzz/p/11782483.html