第三章《栈与队列》
（一）栈简介
栈(Stack)：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在某一端进行插入和删除操作
栈顶(top)：线性表允许进行插入和删除的那一端。（开口的那一端）
栈底(bottom)：固定的，不允许进行插入和删除的另一端。（封死的那一端）
空栈：不含任何元素的空表。
栈的“先进后出”原则（FILO）：已上图为例，栈中存放了 4 个数据元素，进栈的顺序是 A 先进栈，然后 B 进，然后 C 进，最后 D 进栈；当需要调取 A 时，首先 D 出栈，然后 C 出栈，然后 B 出栈，最后 A 才能出栈被调用。
栈的两种表示方式：栈的本质是线性表，那么它就同样有线性表的两种表示形式：顺序栈 和 链式栈（简称“链栈”）
两者的区别：存储的数据元素在物理结构上是否是相互紧挨着的。顺序栈存储元素预先申请连续的存储单元；链栈需要即申请，数据元素不紧挨着。
栈的“上溢”和“下溢”问题：
“上溢”：在栈已经存满数据元素的情况下，如果继续向栈内存入数据，栈存储就会出错。（栈满还存会“上溢”）
“下溢”：在栈内为空的状态下，如果对栈继续进行取数据的操作，就会出错。（栈空再取会“下溢”）
对于栈的两种表示方式来说，顺序栈两种情况都有可能发生；而链栈由于“随时需要，随时申请空间”的存储结构，不会出现“上溢”的情况。
栈的基本操作：
InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈S为空返回true，否则返回false。
Push(&S, x)：进栈，若栈S未满，将x加入使之成为新桟顶。
Pop(&S, &x)：出栈，若栈S非空，弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，用x返回栈顶元素。
ClearStack(&S)：销毁栈，并释放栈S占用的存储空间。
注意：符号'&'是C++特有的，用来表示引用，有的书上釆用C语言中的指针类型‘*’，也可以达到传址的目的。
（二）顺序栈
1、简介
定义：栈的顺序存储称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针(top)指示当前栈顶的位置。
(a)是空栈，(c)是A、B、C、D、E共5 个元素依次入栈后的结果，(d)是在图3-2 (c)之后E、D、C相继出栈，此时栈中还 有2个元素，或许最近出栈的元素C、D、E仍在原先的单元存储着，但top指针已经指向了 新的栈顶，则元素C、D、E已不在栈中了，
栈顶指针：S.top，初始时设置S.top=-1；栈顶元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：S.top=-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。
2、常见操作
① 结构体定义
#define MaxSize 50 //定义栈中元素的最大个数 typedef struct{ Elemtype data[MaxSize]; //存放栈中元素 int top; //栈顶指针 }SqStack;