数据结构
栈
本质
- 只能在表尾位置插入删除的线性表
存储
-
顺序栈
-
结构
- *elem|maxsize|top
-
问题
-
栈上溢
- 入栈时栈满
-
栈下溢
- 出栈时栈空
-
-
-
链式栈
特殊
-
双顺序栈
- 两个栈放在同一个数组中
- 数组的头和尾分别为两个栈的栈底
- 判断栈满：top1==top2-1
应用
-
表达式求值
- 中缀
- 前缀
-
表达式转换
-
递归
-
转化为非递归
-
循环结构
- 尾递归
- 单项递归
-
栈代替
-
-
队列
本质
- 只能在表尾位置插入元素，在表头删除元素的线性表
存储
-
顺序队列
-
结构
- *elem|front|rear
- 初始值;front=rear=0
-
入队
- 元素进入rear所指位置，rear+1
-
出队
- front所在位置元素出队，front+1
-
问题
- 假溢出
-
-
链式队列
特殊
-
循环队列
-
判断队空与队满
-
设标志位
-
少用一个元素空间
-
队空
- front==rear
-
队满
- (rear+1)%maxsize==front
-
-
-
-
受限双端队列
应用
