Chapter 03 栈和队列
1. 栈¶
后进先出, Last-In First-Out
1.1 顺序栈¶
使用向量实现
上溢（Overflow）
当栈中已经有maxsize个元素时，如果再做进栈操作，所产生的“无空间可用”现象
下溢（Underflow）
空栈进行出栈所产生的“无元素可删”现象
1.2 链式栈¶
用单链表实现
1.3 顺序栈与链式栈的比较¶
时间效率:
- 所有操作都只需常数时间
- 顺序栈和链式栈在时间效率上难分伯仲
空间效率:
- 顺序栈须说明一个固定的长度
- 链式栈的长度可变，但增加结构性开销
实际应用中，顺序栈比链式栈用得更广泛些
2. 队列¶
队列是只允许在一端删除，在另一端插入的线性表
允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)
特性: 先进先出(FIFO, First In First Out)
2.1 顺序队列¶
使用顺序表实现
用向量存储队列元素，用两个变量分别指向队列的前端(front)和尾端(rear)
front：指向当前待出队的元素位置（地址）
rear： 指向当前待入队的元素位置（地址）
上溢
当队列满时，再做进队操作，所出现的现象
下溢
当队列空时，再做删除操作，所出现的现象
假溢出
当 rear = mSize-1 时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空位置，这种现象称为假溢出
2.2 循环队列¶
若简单使用 front == rear 判断, 无法区分队空与队满两种状态.
解决方法: 浪费一个存储空间, 以区别队空与队满. 即使用 size+1 个空间, 若 (rear+1) % maxsize == front 说明队满. (也可以使用计数器法, 统计当前入队的元素个数)
2.3 链式队列¶
单链表队列：链接指针的方向是从队头指向队尾
队头在链头，队尾在链尾
链式队列在进队时无队满问题，但有队空问题
队空条件： front == rear ==NULL