Skip to content

0x03 栈与队列

一、栈

栈是只允许在一端进行插入或删除操作的线性表.

栈的基本操作：

  • 初始化
  • 销毁
  • 进栈
  • 出栈
  • 读栈顶元素
  • 判空

1.1 顺序栈

typedef struct{
    ElemType data[MaxSize];
    int top;
} sqStack;

共享栈：两个栈共享同一片内存空间，入栈方向相对。如有地址空间0~9，则栈1的栈顶指针指向0，从0开始增长；栈2的栈顶指针指向9，从9开始减少；判断栈满（内存空间已经全部占满）时，判断top1+1==top2即可。

1.2 链栈

typedef struct{
    ElemType data;
    linkStack* head;
} linkStack;

二、队列

队列是只允许在一端插入数据，在另一端删除数据的线性表。

2.1 队列的顺序实现

typedef struct{
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

循环队列

约定：循环队列的front指向队头元素，而rear指向队尾元素的下一个位置。

循环队列的判空判满设计有不同的方案，有些方案会导致一小块内存空间的浪费，而有些能全部利用。以下入队出队代码是基于其中一种方案的，仅供参考。

  • 入队
bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front){ //队满
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}
  • 出队
bool DeQueue(SqQueue &Q, ElemType &x){
  if(Q.rear==Q.front){ //队空
      return false;
  }
  x = Q.data[Q.front];
  Q.front = (Q.front+1)%MaxSize;
  return true;
}

  • 判断队列已满/已空

  • 方案一

    注意：rear指针指向队尾元素的下一个位置，而不是直接指向队尾元素。

    判空：front==rear

    判满：(rear+1)%MaxSize==front，由于rear指向的是队尾元素的下一个位置，所以判满为True时内存空间中实际还有一块地方没有用上。

    队列元素个数计算：(rear+MaxSize-front)%MaxSize

    故当MaxSize为10时，队列中最多只能有9个元素

  • 方案二

    判空判满不依赖于队头指针和队尾指针的关系，而仅根据队列元素的个数判断。

    队列多一个属性int size，代表队列当前元素个数，初始化时size=0

    判空：size==0

    判满：size==MaxSize

    如此当MaxSize为10时，队列中最多能有10个元素。

  • 方案三

    在方案一的基础上改进。方案一之所以会浪费一小块空间，是因为当元素全部占满空间时会出现rear和front指向同一个元素的情况，此时无法区分究竟是队满还是队空。

    针对这个问题，队列多一个属性int tag，每次出队都令tag=0，每次入队都令tag=1，则：

    判空：front==rear && tag = 0

    判满：front==rear && tag = 1

2.2 队列的链式实现

  • 带头结点的链表

队头指针front指向头结点，队尾指针rear指向队尾元素

初始时队空，front=rear=head，元素进队则rear->next=x; rear=x，

元素出队则把p = front->next释放掉，front->next = p->next；当队列中只有一个元素时是特殊情况，此时rear=front->next，释放掉之后要令rear=front从而设置为队空状态。

即入队只需要修改头指针，出队则头尾指针可能都要修改

  • 不带头结点的链表

队头指针front指向链表的第一个结点，也是实际存储元素的结点。

初始时front=rear=NULL（判队空条件），进了第一个元素后是front=rear=x。

2.3 双端队列

双端队列：只允许从两端插入、两端删除的线性表

栈中合法的输出序列，在双端队列中也一定合法

三、栈与队列的应用

3.1 括号匹配问题

遇到左括号就入栈，遇到右括号就弹出一个左括号；若弹出的左括号类型不匹配或已经栈空，说明括号匹配失败；若所有的右括号都已经处理完而栈非空，则括号匹配也失败。

3.2 表达式求值

中缀表达式 后缀表达式 前缀表达式
a+b ab+ +ab
a+b-c（先算b-c） abc-+ +a-bc
a+b-c*d（先算a+b，再算c*d） ab+cd*- -+ab*cd
((15/(7-(1+1)))*3)-(2+(1+1)) 15 7 1 1 + - / 3 * 2 1 1 + + -

手算

  • 中缀转后缀

中缀表达式中符号生效的次序与后缀表达式中符号从左到右排列的次序一致。

（其实不一致也不一定不对，但计算机只计算这一种情况，因为遵循左优先原则，只要左边还有运算符能先生效，就一定先生效左边的）

左优先原则保证中缀转后缀所得到的后缀表达式唯一。

  • 中缀转前缀

遵循右优先原则。

中缀表达式中符号生效的次序与前缀表达式中符号从右到左排列的次序一致。

后缀表达式计算 算法实现

算法中用到的栈只存放操作数。

  1. 从左往右扫描所有元素
  2. 遇到操作数就入栈，继续扫描
  3. 遇到运算符不入栈，弹出两个栈顶元素，执行运算（注意后弹出的元素在运算符左边，先弹出的元素在运算符右边），运算结果入栈，继续扫描

中缀转后缀 算法实现

算法中用到的栈只存放运算符和界限符。

  1. 从左往右扫描中缀表达式中各元素
  2. 扫描到操作数，直接加入到后缀表达式
  3. 扫描到界限符，若为左括号，直接入栈；若为右括号则依次弹出栈内运算符并加入后缀表达式，直到弹出左括号（左括号不加入后缀表达式）
  4. 扫描到运算符，若栈为空，入栈；若栈非空，则弹出栈顶运算符直到栈顶运算符优先级低于当前运算符。弹出的运算符加入到后缀表达式。最后再把当前运算符入栈。

中缀表达式计算 算法实现

初始化2个栈，一个为运算符栈，另一个为操作数栈。

  1. 从左往右扫描中缀表达式中各元素
  2. 扫描到操作数，入操作数栈
  3. 扫描到界限符，若为左括号，入运算符栈；若为右括号则依次弹出栈内运算符，每弹出一个运算符，操作数栈都弹出两个操作数进行运算后再将结果入栈，直到运算符栈内弹出左括号
  4. 扫描到运算符，若运算符栈空，入栈；若运算符栈非空，则弹出栈顶运算符，每弹出一个运算符，操作数栈都弹出两个操作数进行运算后再将结果入栈，直到栈顶运算符优先级低于当前运算符。最后将当前运算符入栈。
  5. 中缀表达式扫描完毕，若运算符栈非空（一般来说只剩一个运算符），则弹出它做相应运算。
  6. 最后运算符栈空、操作数栈仅有一个元素。

3.3 递归

函数调用栈

当发生一次函数调用时，需要入栈的信息有：函数调用结束后应继续执行的指令的地址（即返回到哪里）、当前函数实参和局部变量（即上下文）。

当函数调用结束后将栈顶信息出栈，从而可以返回到先前的函数、恢复相关数据，继续往下执行。

3.4 特殊矩阵的压缩存储

通用计算方法

若数组下标从0开始，则元素下标是几，就代表它的前面有几个元素。

  • 一维数组B[i]，下标从[0]开始，则元素B[k]前面共有k个元素。
  • 二维数组A[i][j]，下标从[0][0]开始，则元素A[n][m]的前面共有n行m列。

反之亦然。前面有几个元素，元素的下标就是几。

例题：将三对角矩阵A[1...100][1...100]按行优先存入一维数组B[1...298]中，则A中元素A[66][65]在数组B中的位置k为：

解：二维数组A下标从1开始，所以对于A[66][65]，它的前面共有65个整行，这65个整行里，只计算带中元素，则第1行有2个元素；剩下的第2行到第65行，每行都有3个元素。在第66行里它的前面有4个元素。故位于A[66][65]前面的元素总个数为： $$ (2+65\times3)+4=194 $$ 若数组B下标从0开始，那么k正好就是194；而题中数组B下标从1开始，对应加1，所以本题答案k为195。

对称矩阵

只存储主对角线+下三角区，存入一维数组

分为列优先和行优先两种顺序

三角矩阵

只存储存在不同元素的三角区，并在最后一个位置存储常数。存入一维数组。

行优先

三对角矩阵

即线代中的“异爪形”矩阵，但爪子以外的地方都是0

行优先/列优先

稀疏矩阵

非零元素的个数占元素总数的比例很小的矩阵为稀疏矩阵

压缩存储：

  • 顺序存储——三元组<行，列，值>

  • 十字链表法——next指针具有两个方向的链表，分为行next和列next，分别指向同一行上的下一个非零元素、同一列上的下一个非零元素的链表结点。每个十字链表结点的属性除了两个next指针外还有非零元素的值、所在行和所在列。

image-20220920173148649