Chapter3.1：栈
该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛 组编)，完整内容请阅读原书。
1.栈
1.1 栈的基本概念
-
栈的定义
-
栈(Stack)({\rm Stack})(Stack)：只允许在一端进行插入或删除操作的线性表；
-
栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作；
-
栈结构图解如下：
-
栈顶(Top)({\rm Top})(Top)：线性表允许进行插入和删除操作的一端；
-
栈底(Bottom)({\rm Bottom})(Bottom)：固定，不允许进行插入和删除操作的一端；
-
空栈：不含任何元素的空表；
-
假设某个栈S=(a1,a2,a3,a4,a5)S=(a_1,a_2,a_3,a_4,a_5)S=(a1,a2,a3,a4,a5)，如上图的栈结构，根据栈顶栈底定义，可知，a1a_1a1为栈底元素，a5a_5a5为栈顶元素；进栈次序依次为：a1,a2,a3,a4,a5a_1,a_2,a_3,a_4,a_5a1,a2,a3,a4,a5，出栈次序依次为：a5,a4,a3,a2,a1a_5,a_4,a_3,a_2,a_1a5,a4,a3,a2,a1；
-
栈的操作特性概括为：后进先出(LastInFirstOut，LIFO)({\rm Last\ In\ First\ Out，LIFO})(Last In First Out，LIFO)；
-
栈的数学性质：nnn个不同元素进栈，出栈元素不同排列的个数为：1n+1C2nn\displaystyle\frac{1}{n+1}C_{2n}^nn+11C2nn，称为卡特兰(Catalan)({\rm Catalan})(Catalan)数；
-
-
栈的基本操作
- InitStack(&S){\rm InitStack(\&S)}InitStack(&S)：初始化一个空栈SSS；
- StackEmpty(S){\rm StackEmpty(S)}StackEmpty(S)：判断一个栈是否为空，若栈SSS为空，则返回true{\rm true}true，否则返回false{\rm false}false；
- Push(&S,x){\rm Push(\&S,x)}Push(&S,x)：进栈，若栈SSS未满，则将x{\rm x}x加入使之成为新栈顶；
- Pop(&S,&x){\rm Pop(\&S,\&x)}Pop(&S,&x)：出栈，若栈SSS非空，则弹出栈顶元素，并用x{\rm x}x返回；
- GetTop(S,&x){\rm GetTop(S,\&x)}GetTop(S,&x)：读栈顶元素，若栈SSS非空，则用x{\rm x}x返回栈顶元素；
- DestroyStack(&S){\rm DestroyStack(\&S)}DestroyStack(&S)：销毁栈，并释放栈SSS占用的存储空间；
1.2 栈的顺序存储结构
1.2.1 顺序栈的实现
-
采用顺序存储的栈称为顺序栈，其利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)({\rm top})(top)指示当前栈顶元素的位置；
-
栈的顺序存储类型描述：
#define MaxSize 50 // 定义栈中元素的最大个数 typedef struct{Elemtype data [MaxSize]; // 存放栈中元素int top; // 栈顶指针 }SqStack; -
栈顶指针：S.top{\rm S.top}S.top，初始时设置S.top=−1{\rm S.top=-1}S.top=−1；栈顶元素：S.data[S.top]{\rm S.data[S.top]}S.data[S.top]；
-
进栈操作：栈不满时，栈顶指针先加111，再送值到栈顶元素；
-
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减111；
-
栈空条件：S.top==−1{\rm S.top==-1}S.top==−1；栈满条件：S.top==MaxSize−1{\rm S.top==MaxSize-1}S.top==MaxSize−1；栈长：S.top+1{\rm S.top+1}S.top+1；
1.2.2 顺序栈的基本运算
-
栈顶指针和栈中元素间的关系图解如下：
- 上述图解相关说明：图(a){\rm (a)}(a)为空栈，图(b){\rm (b)}(b)只有111个栈元素，图(c){\rm (c)}(c)是A、B、C、D、E{\rm A、B、C、D、E}A、B、C、D、E依次进栈的结果，图(d){\rm (d)}(d)是E、D、C{\rm E、D、C}E、D、C元素相继出栈，此时栈顶指针移至元素B{\rm B}B；
-
顺序栈常用的基本运算
-
初始化：
void InitStack(SqStack &S){S.top=-1; // 初始化栈顶指针 } -
判栈空：
bool StackEmpty(SqStack S){if(S.top==-1)return true; // 栈空返回trueelsereturn false; // 栈非空返回false } -
进栈操作：
bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1)return false; // 栈满，报错S.data[++S.top]=x; // 栈顶指针先加1，再入栈return true; } -
出栈操作：
bool Pop(SqStack &S,ElemType &x){if(S.top==-1)return false; // 栈空，报错x=S.data[S.top--]; // 先出栈，栈顶指针再减1return true; } -
读栈顶元素：
// 此操作仅是读取栈顶元素，但没有出栈 bool GetTop(SqStack S,ElemType &x){if(S.top==-1)return false; // 栈空，报错x=S.data[S.top]; // x记录栈顶元素return true; }
-
1.2.3 共享栈
-
利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸；
-
共享栈的结构图解：
-
两个顺序栈的栈顶指针均指向栈顶元素，top0=−1{\rm top0=-1}top0=−1时，000号栈为空；top1=MaxSize{\rm top1=MaxSize}top1=MaxSize时，111号栈为空；当两个栈顶指针相邻，即top1−top0=1{\rm top1-top0=1}top1−top0=1时，判断为栈满；
-
当000号栈进栈时，top0{\rm top0}top0先加111再赋值，111号栈进栈时，top1{\rm top1}top1先减111再赋值；出栈操作则相反；
-
共享栈目的：为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被栈满时才会发生上溢，其存取数据的时间复杂度均为O(1)O(1)O(1)；
1.3 栈的链式存储结构
-
采用链式存储的栈称为链栈；
-
链栈的优点：便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况；
-
链栈通常采用单链表实现，并规定所有操作都在单链表的表头进行；
-
链栈存储结构图解如下(此处规定链栈没有头结点，Lhead{\rm Lhead}Lhead指向栈顶元素)：
-
栈的链式存储类型描述：
typedef struct Linknode{ElemType data; // 数据域struct Linknode *next; // 指针域 }*LinkStack; // 栈类型定义