文章目录
一、前言
二、栈
1. 栈的定义和特点
2. 栈的操作
2.1 入栈示意图
2.2 出栈示意图
3. 栈与一般线性表的对比
4. 顺序栈
5. 链栈
6. 栈与递归
三、队列
1. 队列的定义和特点
2. 队列的操作
3. 队列与一般线性表的对比
4. 顺序队列
5. 链队列
四、单调栈
1. 伪代码
2. 单调栈的应用
五、单调队列
1. 单调队列的应用
2. 与单调栈的异同
2.1 相同点
2.2 不同点
提示：栈和队列相关例题见栈和队列——相关例题
一、前言
- 栈和队列是两种常用的、重要的数据结构。
- 栈和队列是限定插入和删除只能在表的端点进行的线性表。
- 普通线性表的插入和删除操作如下：
栈和队列的各项具体操作应该由具体情况进行代码的编写，故在此不进行详细编写，在例题当中会进行体现。
二、栈
- 栈是先进后出。类似于手电筒的电池，弹夹里的子弹和堆摞的盘子。
- 如果问题求解的过程具有后进先出的特性时，则求解的算法中也必然需要使用栈。
1. 栈的定义和特点
栈（stack） 是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表。
由于最后一个进行的要最先被删除，因此又称为后进先出的线性表，检测 LIFO 结构。
插入元素到栈顶（即表尾）的操作，称为 入栈。
从栈顶（即表尾）删除最后一个元素的操作，称为 出栈 。
栈只能在栈顶进行操作
2. 栈的操作
2.1 入栈示意图
2.2 出栈示意图
3. 栈与一般线性表的对比
| 结构规则 | 一般线性表 | 栈 |
| 逻辑结构 | 一对一 | 一对一 |
| 存储结构 | 顺序栈、链栈 | 顺序栈、链栈 |
| 运算规则 | 随机存取 | 后进先出 |
4. 顺序栈
存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
设 top 指针，指示栈顶元素在顺序栈中的位置。但是，为了操作方便，通常 top 指示真正的 栈顶元素之上 的下标地址。
设 base 指针，指示栈底元素在顺序栈中的位置。
使用 stacksize 表示栈可使用的最大容量。
栈满时，要分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。
出栈过程与上图类似。
5. 链栈
- 链栈时运算受限的单链表，只能在 链表头部 进行操作。
- 链表的头指针就是栈顶，不需要头节点。
- 空栈相当于头指针指向空，插入和删除仅在栈顶处执行
6. 栈与递归
- 若一个对象部分地包含自己，或者自己给自己定义，则称这个对象是递归地。
- 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
- 递归必备的三个条件：
- （1）能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的。
- （2）可以通过上述转化而使问题简化。
- （3）必须有一个明确的递归出口，或称递归的边界。
借助栈改写递归：
- （1）递归程序在执行时需要系统提供栈来实现。
- （2）仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序。
- （3）改写后的非递归算法与原来的递归算法相比，结构不够清晰，可读性较差，有的还需要经过一系列优化。
三、队列
- 队列是先进先出。类似于生活中的排队问题。
- 由于队列的操作具有先进先出的特性，使得队列成为程序设计中解决类似排队问题的有用工具
1. 队列的定义和特点
队列（queue） 是一种先进先出的线性表。在表一端插入（表尾），在另一端（表头）删除。
由于最后一个进行的要最先被删除，因此又称为后进先出的线性表，检测 LIFO 结构。
插入元素到栈顶（即表尾）的操作，称为 入栈。
从栈顶（即表尾）删除最后一个元素的操作，称为 出栈 。
栈只能在栈顶进行操作
2. 队列的操作
- 关键是掌握入队和出队操作，具体实现以顺序队或链队的不同而不同。
3. 队列与一般线性表的对比
| 结构规则 | 一般线性表 | 栈】队列 |
| 逻辑结构 | 一对一 | 一对一 |
| 存储结构 | 顺序栈、链栈 | 顺序队、链队 |
| 运算规则 | 随机存取 | 先进先出 |
4. 顺序队列
队列的顺序表示——一维数组。
顺序队的四要素（初始时front=rear=-1）：
rear指向队尾元素；front指向队头元素的前一个位置。
队空条件：front = rear 。
队满条件：rear＝MaxSize－1 。
元素e进队：rear ++; data[rear] = e 。
元素e出队：front ++; e = data[front] 。
5. 链队列
- 若用户无法估计所用队列的长度，则应该使用链队列。
- 链队列运算指针变化状况：
- （1） 空队列：
（2） 元素 x 入队列
：
（3） 元素 y 入队列：
（4） x 出队列：
