3.1. 栈
定义
只允许在一端进行插入或删除操作的线性表。
- 栈顶：线性表允许进行插入和删除操作的一端
- 栈底：固定的，不允许进行插入和删除操作的一端
- 空栈：不含任何元素的空表
- 后进先出（Last In First Out , LIFO）
基本操作
- 空栈初始化（InitStack）
- 判断栈是否为空(StackEmpty)
- 进栈(Push)
- 出栈(Pop)
- 读取栈顶元素(GetTop)
- 销毁栈(ClearStack)
栈的顺序存储
- 共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸（更有效的利用存储空间）
栈的链式存储
- 优点：便于多个栈共享存储空间和提高效率，不存在栈满上溢的情况。
3.2. 队列
定义
一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除。
- 队头：允许删除的一端，又称队首
- 队尾：允许插入的一端
- 空队列：不含任何元素的空表
- 先进先出（First In First Out , FIFO）
常见操作
- 初始化队列（InitQueue）
- 判断队列是否为空（QueueEmpty）
- 入队（EnQueue）
- 出队（DeQueue）
- 读队头元素（GetHead）
队列的顺序存储结构
- 顺序队列：分配一块连续的存储单元存放队列中的元素，设置队尾指针（rear）和队首指针（front）【容易形成假溢出】
- 循环队列：把存储队列元素的表视为一个环空间。当队首指针到达最后一个位置时，自动到0【利用%操作】
- 循环队列的满空判断：（1）牺牲一个单元来区分队空和队满（2）增加一个记录元素个数的数据成员（3）增加一个tag来区分队满还是队空
队列的链式存储
队列的链式表示，一个同时带有队头指针和队尾指针的单链表。
双端队列
允许两端都可以进行入队和出队操作的队列
- 输出受限的双端队列：允许在一端进行插入和删除，另一端只能插入的双端队列
- 输入受限的双端队列：允许在一端进行插入和删除，另一端只能删除的双端队列
3.3. 栈和队列的应用
栈用于括号匹配
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8- 1入栈，2入栈，3入栈，4入栈，3和4匹配为一套完整括号，3、4出栈
- 5入栈，6入栈，5和6匹配为一套完整括号，5、6出栈
- 7入栈，2和7匹配为一套完整括号，2、7出栈
- 8入栈，1和8匹配为一套完整括号，1、8出栈
- 若最后栈中为空，则输入的括号为正确格式
栈用于表达式求值
各个运算符和括号具有优先级，运用后缀表达式的方法来考虑运算优先级
| 中缀表达式 | 后缀表达式 |
|---|---|
| A+B*(C-D)-E/F | ABCD-*+EF/- |
栈在递归中的作用
队列在层次遍历中应用
队列在迷宫寻路中的作用
队列在计算机系统中的作用