与线性表不同，它们都是限制存储位置的线性结构

一、栈

1. 概念

只允许在一端插入和删除的线性表

栈顶：允许插入和删除的一端

栈底：另一端

空栈：当表中没有元素时称为空栈

进栈（push）：在栈顶位置插入元素的操作

出栈（pop）：删除栈顶元素

2. 顺序栈

用数组来实现顺序栈

用一个整型变量top栈顶指针来指出栈顶。（置空时top = -1）

上溢：对满栈进行push

下溢：对空栈进行pop

3. 共享栈

两个栈共享一个数组空间num[maxSize]

空间的两端分别设置为两个栈的栈底

栈满条件：

t[0] + 1 = t[1]

栈空条件：

t[0] == b[0] == num[0]

t[1] == b[1] == num[maxSize]

3. 链式栈

无栈满问题、插入与删除仅在栈顶处执行

4. 中缀表达式求值

设置两个栈：运算符栈（optr）和操作数栈（opnd）

外部优先级小于等于内部优先级，则弹出optr的运算符，进行计算

否则入栈

5. 后缀表达式求值

遇到符号就把前面两个操作数用来计算

二、栈与递归

用到递归的三种情况：

• 定义是递归的
• 数据结构是递归的
• 问题的解法是递归的

1. 汉诺塔问题

出口是怎么出的，入口怎么入，怎么回去

2. 递归工作栈

每一次递归调用的时候，需要为过程中使用的参数、局部变量等另外分配内存空间

• 返回地址（下一条指令）
• 局部变量
• 参数

3. 递归的优化

• 单项递归用迭代法优化
• 尾递归用迭代法优化

三、队列

只允许在一端删除，在另一端插入的顺序表

队头：允许删除的一端

队尾：允许插入的一端

1. 队列的进队和出队

• 数组形式

  • front和rear指向同一个节点的时候表示空队列
  • rear始终不指着元素，front始终指着头元素
  • 队空：front == rear
  • 队满：rear == maxSize - 1（假溢出）

• 循环队列

  队列存放数组被当做首尾相接的表处理

  • 指针进一：point = (point + 1) % maxSize
  • 队满条件：(rear + 1) % maxSize == front
  • 存储元素数量：(maxSize + rear - front) % maxSize

• 链式队列

  rear指着的格子有东西了

  • 队空：front == NULL

四、优先级队列

每次从队列中取出具有最高优先权的队列

出现相同的优先级的元素时，按$FIFO$的方式处理