栈¶
定义¶
栈（stack）是限定仅在表尾进行插入和删除操作的线性表。栈遵循后进先出（Last In First Out，LIFO）的特点，即最后插入的元素最先被删除。
允许插入和删除的一端称为栈顶（top），另一端则称为栈底（bottom）:
栈的特殊之处在于其限制了元素插入与删除操作的可执行位置。栈的插入操作称为入栈（push），也可称为压栈、进栈等；删除操作称为出栈（pop），也可称为弹栈。将栈比作一个弹夹，同时将栈内元素比作子弹来理解栈的概念会形象得多。
Note
注意栈首先是一个线性表，也就是说，栈的元素具有线性关系，即前后驱动关系。
栈的顺序存储结构¶
栈的本质是一个线性表，那么基于线性表的两种基本存储逻辑，也就可以通过顺序存储结构与链式存储结构两种方式实现。
顺序栈的实现¶
#define MaxSize 100
typedef struct {
ElemType data[MaxSize];
int top; // 栈顶指针
} SqStack;
基本操作¶
初始化¶
void InitStack(SqStack *S) {
S->top = -1;
}
判空¶
bool StackEmpty(SqStack S) {
return S.top == -1;
}
入栈¶
bool Push(SqStack *S, ElemType e) {
if (S->top == MaxSize - 1) { // 栈满
return false;
}
S->data[++S->top] = e; // 栈顶指针加1，将元素e入栈
return true;
}
出栈¶
bool Pop(SqStack *S, ElemType *e) {
if (S->top == -1) { // 栈空
return false;
}
*e = S->data[S->top--]; // 出栈，栈顶指针减1
return true;
}
获取栈顶元素¶
bool GetTop(SqStack S, ElemType *e) {
if (S.top == -1) { // 栈空
return false;
}
*e = S.data[S.top]; // 获取栈顶元素
return true;
}
共享栈¶
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在数组的两端，两个栈顶向数组中间延伸，这就构成了一组共享栈。
栈的链式存储结构¶
栈也可基于链表实现，称为链栈。
栈元素的删除与插入操作均在栈顶进行，因此链表的头部通常可以直接作为栈顶。
对于链栈而言，基本不存在栈满的情况，因为链表可以动态扩展。
链栈的实现¶
typedef struct StackNode {
ElemType data;
struct StackNode *next;
} StackNode, *LinkStack;
基本操作与链表类似，注意链表是否具有头节点。
栈的典型应用¶
栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考方位缩小，更加聚焦于我们所要解决的问题核心。
以下是栈的几个典型应用场景：