思维导图：点我

一、栈

1. 顺序栈

1. 存储结构

1. 初始化

1. 判栈空

1. 进栈

1. 出栈

1. 读栈顶元素

2. 共享栈

3. 带头结点的链栈

1. 存储结构

1. 初始化

1. 进栈

1. 出栈

1. 判栈空

1. 读栈顶元素

4. 不带头结点的链栈

1. 存储结构

1. 进栈

1. 出栈

1. 判栈空

1. 读栈顶元素

二、栈的应用

1. 括号匹配

2. 表达式求值

1. 中缀表达式与前后缀表达式的互化
中缀表达式化后缀表达式遵循左优先，化前缀表达式遵循右优先

1. 构造后缀表达式
使用符号栈

1. 后缀表达式求值
使用符号栈与数据栈

3. 递归

1. 原理
即我自己调用我自己

1. 应用
斐波那契数列

1. 应用原理
系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储。

三、队列

1. 顺序队列

1. 存储结构

1. 初始化

1. 入队

1. 出队

1. 队列判空

1. 读队头元素

2. 循环队列

1. 存储结构

1. 初始化

1. 入队

1. 出队

1. 队列判空

1. 读队头元素

3. 链队

1. 存储结构

2. 初始化

3. 入队

4. 出队

5. 队列判空

6. 读队头元素

4. 双端队列

1. 普通双端队列
两端皆可入队出队

2. 输出受限的双端队列
队头可入队出队，队尾只能入队

3. 输入首先的双端队列
对头可入队出队，队尾只能出队

四、队列的应用

1. 层次遍历

1. 树的层次遍历
详见 《树》

2. 图的层次遍历
详见 《图》

2. 计算机中的应用

1. 任务队列
详见 《操作系统》

2. 进程队列
详见 《操作系统》

3. 流量控制窗口
详见 《计算机网络》