一、栈的介绍
栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。
允许插入和删除运算的一端称作栈顶（top）。
不允许插入和删除的另一端称作栈底（bottom）。
在栈顶进行的插入操作称为入栈或进栈(push)
在栈顶进行的删除操作称为出栈或退栈(pop)
栈的特点：后进先出，即 LIFO(Last In First Out)
如下图：
顺序栈的数据类型
静态分配：
#define MaxSize 100#define int ElemType typedef struct{ElemType data[MaxSize]; // 数组存储空间int top; //栈顶下标} SqStack; // 顺序栈数据类型
MaxSize为顺序栈的最大容量；
top为栈顶元素的下标，0 <= top <= MaxSize-1
栈空：top = -1; 栈满：top = MaxSize-1
注意栈空和栈满的判断条件，如上图，栈顶top = 0 时，有数据元素a1，所以top = -1时，才能判断栈空。栈满时，由上图看知。
动态分配：
#define int ElemType typedef struct{ElemType *base; //栈底的指针ElemType *top; //栈顶的指针} SqStack; // 顺序栈数据类型
链式栈的数据型
typedef struct LNode{ElemType data;//数据域struct LNode *next; //后继结点指针} LinkStNode; //链栈结点类型
S：单链表头指针，指向头结点。
栈顶：单链表第一个元素结点的位置，即头结点的后一个位置。
二、顺序栈的基本运算
1、初始化栈
建立一个新的空栈s，实际上是将栈顶指示变量置-1即可。
//初始化空顺序栈int InitStack(SqStack &S){S.top = -1;return 1;}
2、入栈：
①判断栈是否已满，若满则产生上溢出错误，退出算法，否则执行第②步；
②栈顶下标增一（top++），指向新的栈顶位置；
③将新元素置于栈顶。
//item是需要入栈的数据元素bool Push(SqStack &S, ElemType item){if (S.top == MaxSize - 1){cout << "栈满" << endl;return false;}S.top++;S.data[S.top] = item;return true;}
3、出栈：
①判断栈是否为空，若空则产生下溢出错误，退出算法，否则执行第②步；
②栈顶元素出栈；
③栈顶下标减一（top++），指向新的栈顶位置；
bool Pop(SqStack &S, ElemType &item){if (S.top == -1){cout << "栈空" << endl;return false;}item = S.data[S.top];S.top--;return true;}
4、判断栈是否为空
栈S为空的条件是s.top==-1。
//判栈空int StackEmpty(SqStack &S){if(S.top==-1)return 1;elsereturn 0;}
5、取栈顶元素
在栈不为空的条件下，将栈顶元素赋给e。
//取栈顶int GetTop(SqStack &S, DataType &e){if(S.top <= -1){cout<<"栈空"<<endl;return 0;}item=S.items[S.top];return 1;}
注意：
取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈顶指针并没有改变。如下图：
入栈时要判断栈是否满，出栈时要判断是否为空。
三、链式栈的基本运算
1、初始化栈
建立一个空栈s。实际上是创建链栈的头结点，并将其next域置为NULL。
void (SNode *&s){s=(SNode *)malloc(sizeof(SNode));//s=new SNode;s->next=NULL;}
2、入栈：
bool Push(LinkStNode *S, ElemType item){//带头结点单链表的表头插入法LinkStNode *t = new LinkStNode; //①生成新结点if (t == NULL){cout << "内存不足";return false;}t->data = item;//②在栈顶插入新结点t->next = S->next;S->next = t; //③return true;}
3、出栈：
bool Pop(LinkStNode *S, ElemType &item){//删除单链表的第一个元素结点//①判断栈是否为空if (S->next == NULL){cout << "栈空";return false;}//②删除栈顶元素LinkStNode *t = S->next;S->next = t->next;item = t->data;delete t;return true;}
4、销毁栈
//释放链栈void Destroy(SNode *&s){SNode *p;while(s!=NULL){p=s;s=s->next;delete p;}}
5、判断栈是否为空
栈S为空的条件是s->next==NULL，即单链表中没有数据结点。
//判栈空int StackEmpty(SNode *s){if(s->next==NULL)return 1;elsereturn 0;}
6、取栈顶元素
int GetTop(SNode *s，DataType &e){if (s->next==NULL)//栈空的情况{return 0;}e=s->next->data;return 1;}
如果觉得《【数据结构与算法】栈的介绍及基本运算（出栈 入栈 销毁栈等）》对你有帮助，请点赞、收藏，并留下你的观点哦！
