-
栈
-
定义
- 是只允许在一端进行插入或删除操作的线性表
-
重要术语
-
栈顶
- 允许插入和删除的一端
-
栈底
- 不允许插入和删除的一端
- 空栈
-
常考
- 出栈顺序
- 卡特兰数:C n 2n /(1+n)
-
不同物理存储
-
顺序栈
-
共享栈
- 两个栈共享同一片内存空间,两个栈从两边往中间增长
- 链式栈
-
应用
- 括号匹配
-
表达式求值
- 中缀表达式
-
后缀表达式(逆波兰式)
- 中缀转后缀
- 后缀转中缀
- 求值
-
前缀表达式(波兰式)
- 中缀转前缀
- 求值
- 递归
-
队列
-
基本概念
-
定义
- 只允许在一端进行插入,另一端进行删除
-
重要术语
- 队头
- 允许删除的一端
- 队尾
- 允许插入的一端
-
基本操作
- 创销、增删查
-
实现
-
顺序实现
-
重要考点
- 初始化、入队出队、判空判满、计算队列长度
-
链表实现
- 带头结点
- 不带头结点
-
双端队列
- 允许从两端插入、两端删除的线性表
-
类型
- 双端队列
- 输入受限的双端队列
- 输出受限的双端队列
- 考点:判断输出序列合法性
-
应用
- 树的层次遍历
- 图的广度优先遍历
- 操作系统中的先来先服务