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)

但对于链队列，需要频繁申请和释放结点，会有一定的时间消耗

空间上：循环队列必须有一个固定长度，链队列更为灵活

循环队列可能存在溢出或者空间浪费问题

总的来说：在可以确定队列长度最大值的情况下，建议使用循环队列，如果无法预估队列的长度，则使用链队列