文档内容基于 B 站视频： https://www.bilibili.com/video/BV1nJ411V7bd 数据结构以及算法的代码实现： https://github.com/BlckKn1fe/Data-Structure-and-Algorithm

3.1 Stack 和 Queue 的定义和特点

Stack 和 Queue 也是很常用的数据结构，他们的特点是限定了插入和删除只能在表的端点进行。所谓端点就是指的把头或结尾。

在线性表中，添加或删除的位置可以是在 0 <= i <= n的而另外两个与之不同

3.1.1 Stack

Stack 添加元素和删除元素都是在 n（表尾）的位置，所以它具有后进先出（LIFO）的特性。如果问题的求解过程也具有后进先出的特性，那么我们就可以使用 Stack 这种数据结构来求解，比较常见的案例有：

• 数制转换：如 10 进制转 8 进制，把余数丢到 Stack 里，然后全 pop 出来
• 括号匹配
• 行编辑程序
• 迷宫求解
• 表达式求值
• 八皇后问题
• 递归调用
• …

Stack 可以用顺序表来实现，也可以用链表来实现

3.1.2 Queue

Queue 添加元素限定添加在 n 的位置，而删除的时候规定只能删除第一个元素，所以它具有先进先出（FIFO）的特性。所以类似解决排队问题的时候，Queue 就会是一个合适的数据结构。

• 打印机
• 网络电文传输
• 多用户系统排队，分时循环使用 CPU 和内存资源
• …

3.2 Stack 和 Queue 的实现

3.2.1 Stack

#define MAXSIZE 100
typedef struct {
    SElemType *base;  // 栈底指针
    SElemType *top;  // 栈顶指针
    int stackSize;  // 栈的最大容量
} SqStack;

这里只记录 Stack 的两种实现方式：

• 通过 Array 实现：Stack 需要设置大小，考虑栈溢出的情况
• 通过 LinkedList 实现：理论上可以假设其大小无限

（两个实现方式都在 GitHub 上了）

3.2.2 Queue

#define MAXQSIZE 100
typedef struct {
    QElemType *base;  // 初始化动态分配储存空间使用
    int front;  // 头指针
    int rear;  // 栈的最大容量
} SqQueue;