Chapter 4 Stacks and Queues
第 4 章 栈与队列
栈（stack）
限定仅在表尾进行插入和删除操作的线性表
允许插入和删除元素的一端称为栈顶(top)[表头]，另一端称为栈底(bottom)[表尾]，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表（Last In First Out），简称LIFO结构
类似网页中的后退操作，最后看的网站会最先被弹出
栈的插入：进栈（压栈（栈顶不动）[需要进行移位 O(n) 复杂度]、入栈（栈底不动）[不需要移位 O(1) 复杂度]）
栈的删除：出栈（弹栈）
进栈出栈的变化形式
保证栈顶元素先出栈，而不一定严格遵循先进后出。
栈的抽象数据类型
理论上线性表的操作特性他都具备，但其插入和删除操作会有变化。（进栈和出栈操作）
栈的顺序存储结构及实现
栈的顺序存储（顺序栈）
设置栈底（bottom/base）、栈顶（top）变量
数组下标为 0 的一端作为栈底；
栈顶 top（指针变量）的位置必须小于 StackSize，当栈存在一个元素时，top = 0;
空栈时 top = -1;
栈中元素个数 = top - base;
进栈、出栈操作
顺序栈的基本操作：进栈操作
void
Push(ElementType X,Stack S)
{
if(IsFull(S))
Error("Full stack");
else
S->Array[++S->TopOfStack] = X;
}顺序栈的基本操作：出栈操作
两者不涉及循环语句，时间复杂度为 O(1) ；
链栈：栈的链式存储结构
两栈共享空间
两个栈共用一个数组，栈底为数组的两端，增加元素时，栈顶向中间靠拢，当top1+1=top2时，两个栈顶碰头，栈满
这样的数据结构适用于两个栈的空间需求有相反关系时，一个栈增长而另一个栈在缩短时；
例如：买卖股票时，你买入，就一定会有一个人卖出；
有人赚钱，就有人赔钱；
并且这个操作也只适合两个具有相同数据类型的栈；
栈的链式存储结构及实现
简称链栈；
链栈不需要头结点，链栈的栈顶在单链表的头部；
对于链栈来说，基本不存在栈满情况，除非内存已经没有可以使用的空间；
对于空栈，链表原定义是头指针指向空，那么链栈的空就是top=NULL；
链栈的进栈、出栈操作
与单链表的链式存储结构基本相似，但有不同
链栈的进栈和出栈操作都很简单，没有任何的循环操作，时间复杂度为O(1)
对比顺序栈和链栈
时间复杂度均为O(1)；
空间性能上：顺序栈需要事先确定一个固定长度；链栈则要求每个元素都有指针域，但对栈的长度无限制
总结：如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，不能最好用链栈，反之，如果它的变化在可控范围内，建议用顺序栈会更好一些。
栈的应用——递归
例：斐波那契数列
当前项等于前两项之和
f(n)=f(n-1)+f(n-2)
递归中栈的思想：在调用递归函数时：对于每一层递归，函数的局部变量、参数值、以及返回地址都被压入栈中。在返回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的剩余部分，也就恢复了调用的状态
栈的应用——四则运算表达式求值
含有括号的运算表达
遇到左括号就进栈，遇到右括号就出栈，然后对期间进栈的数做运算。
后缀表达式，数字先进栈，遇到运算符就出栈，做运算。
而我们平时写的标准四则运算表达式称为中缀表达式
所以计算机需要将中缀表达式转化为后缀表达式，再利用栈进行运算
栈的应用——迷宫问题
队列（queue）
定义：只允许在一端进行插入操作，而在另一端进行删除操作的线性表
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行
假定：front指针变量指向队头元素，rear指针指向队尾元素的下一个位置
循环队列
普通顺序存储队列，类似线性表的顺序存储结构，先进先出，然后所有位置前移
若不前移，则会发生假溢出（数组的前面有空位，而后面无法再插入元素）
于是循环队列：解决假溢出。
循环队列：队列的头尾相接的顺序存储结构
队列满的条件是：(rear+1)%QueueSize==front
通用的计算队列长度的公式：(rear-front+QueueSize)%QueueSize
队列的链式存储结构及实现
其实就是线性表的单链表，只不过它只能尾进头出而已，我们把他简称为链队列。
循环队列与链队列
时间上：基本都是常数时间O(1)
但对于链队列，需要频繁申请和释放结点，会有一定的时间消耗
空间上：循环队列必须有一个固定长度，链队列更为灵活
循环队列可能存在溢出或者空间浪费问题
总的来说：在可以确定队列长度最大值的情况下，建议使用循环队列，如果无法预估队列的长度，则使用链队列
Last updated