栈和队列

• 栈和队列
  • 定义
  • 顺序栈
    • 顺序栈-进栈
    • 顺序表-出栈
    • 顺序栈-读栈
    • 顺序栈-共享栈
    • 栈的链式实现
  • 队列
    • 队列-顺序存储
    • 队列-入队
    • 队列-出队
    • 队列的链式实现
    • 双端队列
  • 栈-括号匹配
  • 栈-表达式求值
    • 原理
    • 代码
  • 栈的应用-递归
  • 队列的应用
  • 特殊矩阵的压缩存储
    • 对称矩阵
    • 三角矩阵
    • 三对角矩阵
    • 稀疏矩阵

定义

栈(stack) 是只允许一端进行插入或删除操作的线性表（是同一端）.

重要术语

• 栈顶
• 栈底
• 空栈

特点：LIFO（Last In First Out）后进的先出

基本操作

• InitStack(& S)：初始化栈。构造一个空栈S，分配内存空间。
• DestroyStack(& S)：销毁栈。销毁并释放栈S所占的内存空间。
• Push(&S, x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
• Pop(&S, &x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回
• GetTop(S, &x)：读栈顶元素。若栈S非空，则用x返回栈顶元素
  • 栈的差一般只访问栈顶元素
• StackEmpty(S)：判断一个栈S是否为空，若为空，则返回true，否则返回false。

常考题型：判断合法的出栈的顺序（要满足先进后出，后进先出）

n个不同元素进栈，出栈元素不同排列的个数为 $\dfrac{1}{n+1}C_{2n}^{n}$。
上述公式成为卡特兰(Catalan)数，可用数学归纳法法证明。
例如：有3个数据元素abc，有 $\dfrac{1}{4}\cdot\dfrac{6*5*4}{1*2*3}=5$ 种可能
a进a出b进b出c进c出
ab进b出c进c出
abc进cba出
a进a出bc进cb出
ab进ba出c进c出

顺序栈

定义

#define MaxSize 10 // 定义栈中元素的最大个数
typedef struct{
  ElemType data[MaxSize]; // 静态数组存放栈中元素
  int top; // 栈顶指针
}SqStack;

初始化栈：

void InitStack(SqStack &S){
  S.top = -1; // 初始化栈顶指针 
}

判断栈空

bool StackEmpty(SqStack S){
  if(S.top == -1)
    return true;
  else
    return false;
}

顺序栈-进栈

bool Push(SqStack &S, ElemType x){
  if(S.top == MaxSize -1)
    return false;
  S.top++; // 指针加一
  S.data[S.top]=x;
  // 上面这两句可以合成一句
  // S.data[++S.top] = x;
  return true;
}

顺序表-出栈

返回了pop出来的元素

bool Pop(SqStack &S, ElemType &x){
  if(S.top == -1)
    return false;
  x = S.data[S.top];
  S.top--;
  // 上面这两句可以合成一句
  // x = S.data[S.top--];
  return true;
}

顺序栈-读栈

获得栈顶元素

bool GetTop(SqStack S, ElemType &x){
  if(S.top == -1)
    return fasle;
  x = S.data[S.top];
  return true;
}

top如果一开始设计为-1，那么top表示指向的栈顶元素，top一开始如果设计为零，那么top指向的位置是栈顶元素的下一个，也表示当前栈的元素个数

顺序栈-共享栈

提高内存空间的利用率

#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int top0; // 0号栈栈顶指针
  int top1; // 1号栈栈顶指针
}ShStack;

初始化栈

void InitStack(ShStack &S){
  S.top0=-1; // 初始化栈顶指针
  S.top1=MaxSize;
}

相当于一个空间，两个栈分别把内容推到两头

栈的链式实现

感觉和头插法差不多，单链表只能操作头下一个结点

链头就是栈顶

typedef struct Linknode{
  ElemType data;
  struct Linknode *next;
}*LiStack;

比较简单

队列

队列(Queue) 是只允许在一端进行插入，在另一端删除的线性表

特点：先进队列的元素先出FIFO(First In First Out)
重要术语

• 队头：允许删除的一端
• 队尾：允许插入的一端
• 空队列

基本操作

• InitQueue(&Q)：初始化队列，构造一个空队列Q
• DestroyQueue(&Q)：销毁队列，销毁并释放队列Q所占的内存空间
• EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾
• DeQueue(&Q, &x)：出队，若队列Q非空，删除对头元素，并用x返回
• GetHead(Q, &x)：读队头元素，若队列Q非空，则将对头元素赋值给x
• QueueEmpty(Q)：判断队列是否为空，若队列Q为空返回true，否则返回false

DeQueue 和 GetHead 的区别在于GetHead不删除对头元素

队列和栈都是操作受限的线性表

队列-顺序存储

#define MaxiSize 10
typedef struct{
  ElemType data[MaxSize]; // 用静态数组存放队列元素
  int front, rear; // 队头指针和队尾指针
}SqQueue;

顺序存储是指物理空间上的连续
队尾指针是指向下一个存储的位置

初始化队列

void InitQueue(SqQueue &Q){
  // 初始时 对头、队尾指针指向0
  Q.rear = Q.front = 0;
}

判断队列是否为空

bool QueueEmpty(SqQueue Q){
  if(Q.rear == Q.front)
      return true;
  else
      return false;
}

队列-入队

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;
}

用这种方式实现的队列成为循环队列，用模运算将存储空间在逻辑上变成了“环状”，这样会浪费一个空间位置，可以通过给SqQueue增加一个size元素，来存储队列中元素的个数，来判断队列已满还是为空
或者增加一个tag元素，用来表示最近一次的操作是插入还是删除，因为判空是通过front == rear 判断的，因此存了MaxSize个数据后，front会等于rear，因此有三种方法

• 只存MaxSize-1个数据，这样只有为空的时候才会front==rear
• 队列结构里增加一个size元素表示队列里元素的个数
• 队列结构里增加一个tag元素表示最近一次操作，如果front== rear，那么tag表示删除则为空，tag表示插入则为满

队列-出队

删除一个对头元素，并用x返回

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;
}

获得对头元素的值，用x返回

bool GetHead(SqQueue Q, ElemType &x){
  if(Q.rear == Q.front)
    return false;
  x = Q.data[Q.front];
  return true;
}

队列元素个数

int Length(SqQueue Q){
  return (Q.rear+MaxSize-front)%MaxSize;
}

之前讲的都是队尾指针指向下一个存储的地址，也可以队尾指针指向队尾元素，此时的判空方法

(rear+1)%MaxSize == front

但是同样的需要牺牲一个存储单元来避免两种状态（满，空）都会识别为空，解决方法和之前相同

• 牺牲一个存储单元
• 增加辅助变量

队列的链式实现

// 链式队列结点 
typedef struct LinkNode{
  ElemType data;
  struct LinkNode *next;
}LinkNode;

// 链式队列
typedef struct{
  LinkNode *front, *rear;
}LinkQueue;

同样分为带头结点和不带头结点

初始化（带头结点）

void InitQueue(LinkQueue &Q){
  // 初始化时 front、rear都指向头结点
  Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
  Q.front->next = NULL;
}

判断队列是否为空

bool IsEmpty(LinkQueue Q){
  if(Q.front == Q.rear)
    return true;
  else
    return false;
}

入队（带头结点）

void EnQueue(LinkQueue &Q, ElemType x){
  LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
  if(s == NULL)
    return false;
  s->data = x;
  s->next= NULL;
  Q.rear->next = s; // 新节点插入到rear之后
  Q.rear = s;       // 修改表尾指针
}

出队（带头结点）

bool DeQueue(LinkQueue &Q, ElemType &x){
  if(Q.front == Q.rear)
    return false;
  LinkNode *p = Q.front->next;
  x = p->data; // 用变量x返回队头元素
  Q.front->next = p->next;
  if(Q.rear == p){ // 如果此次时最后一个结点出队
    Q.rear = Q.front; // 修改rear指针
  }
  free(p);  // 释放结点空间
  return true;
}

初始化（不带头结点）

void InitQueue(LinkQueue &Q){
  // 初始化时 front、rear 都指向NULL
  Q.front = NULL;
  Q.rear = NULL;
}

判断队列是否为空（不带头结点）

bool IsEmpty(LinkQueue Q){
  if(Q.front == NULL)
    return true;
  else
    return false;
}

入队（不带头结点）

void EnQueue(LinkQueue &Q, ElemType x){
  LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
  s->data = x;
  s->next =NULL;
  if(Q.front == NULL){// 对第一个元素特殊处理
    Q.front = s;
    Q.rear=s;
  } else {
    Q.rear->next = s;
    Q.rear = s;
  }
}

出队（不带头结点）

bool DeQueue(LinkQueue &Q, ElemType &x){
  if(Q.front == NULL)
    return false; // 空队
  LinkNode *p = Q.front;
  x = p->data;
  Q.front = p->next;
  if(Q.rear == p){
    Q.front = NULL;
    Q.rear = NULL;
  }
  free(p);
  return true;
}

双端队列

双端队列是允许从两端插入、两端删除的线性表。
输入受限的双端队列是只允许从一段插入，两端删除的线性表。
输出受限的双端队列是只允许两端插入，一端删除的线性表。

常考输出序列的合法性，主要是自己分析orz

栈-括号匹配

// 初始化栈
void InitStack(SqStack &S)

// 判断栈是否为空
bool StackEmpty(SqStack S)

// 新元素入栈
bool Push(SqStack &S, char x)

// 栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)

bool brancketCheck(char str[], int length){
  SqStack S;
  InitStack(S);
  for (int i =0; i<length; i++){
    if(str[i] == '(' || str[i] == '[' || str[i] = '{'){
      Push(S, str[i]); // 扫描到左括号，入栈
    } else {
      if(StackEmpty(S))
        return false;
      char topElem;
      Pop(S, topElem);
      // 这边我觉得前后交换一下可能会更好，以为按下面这种方式比较如果输入中有不是括号的就检测不出来了
      if(str[i] == ")" && topElem!= '(')
        return false;
      if(str[i] == "]" && topElem!= '[')
        return false;
      if(str[i] == "}" && topElem!= '{')
        return false;
    }
    return StackEmpty(S); // 检索完全部括号后，说明匹配成功
  }
}

栈-表达式求值

原理

Reverse Polish notation 逆波兰表达式=后缀表达式
Polish notation 波兰表达式=前缀表达式

中缀表达式就是操作符在两个操作数中间，比如1 + 1
后缀表达式就是操作符在两个操作数后面，比如1 1 + 前缀表达式就是操作符在两个操作数前面，比如+ 1 1

a+b-c 的后缀表达式是 a b + c -
a+b-c 的前缀表达式是 - + a b c
一个表达式的后缀表达式和前缀表达式是不唯一的
a+b-c*d 的后缀表达式是 a b+ c d* -
a+b-c*d 的前缀缀表达式是 -+a b * c d

中缀表达式转后缀表达式的方法：

• 确定中缀表达式中各个运算符的运算顺序
• 确定下一个运算符，按照【左操作数 右操作数 运算符】 的方式组成一个新的操作数
• 如果还有运算符没被处理，就继续上一步

因为运算顺序不唯一，因此对应的后缀表达式也不唯一

“左优先”原则：只要左边的运算符能计算，那就优先计算最左边的，这样可以保证运算顺序的唯一性

比如：

A+B-C*D/E+F 转化为
A B + C D * E / - F +

我们要怎么样计算这样一个后缀表达式呢？
以上面的例子为例：
先将A，B压入栈中，读到一个操作符，则弹出两次栈顶元素，进行计算，再压入栈中，即：

• 压入A
• 压入B
• 读到+号
• 弹出B
• 弹出A
• 计算A+B，并压入栈中
• 压入C
• 压入D
• 读到*号
• 弹出D
• 弹出C
• 计算C*D，并压入栈中
• 压入E
• 读到/号
• 弹出E
• 弹出C*D
• 计算C*D/E，并压入栈中
• 读到-号
• 弹出C*D/E
• 弹出A+B
• 计算(A+B)-(C*D/E)，并压入栈中
• 压入F
• 读到+号
• 弹出F
• 弹出(A+B)-(C*D/E)
• 计算(A+B)-(C*D/E)+F并压入栈中
• 扫描结束，得到最后结果(A+B)-(C*D/E)+F

中缀表达式转换成前缀表达式：

• 确定中缀表达式中各个运算符的运算顺序
• 选择下一个运算符，按照【运算符 左操作数 右操作数】 的方式组合成一个新的操作数
• 如果还有运算符没有被处理，就继续上一步

“右优先”原则：只要右边的运算符能先计算，就优先计算右边的

比如

A+B*(C-D)-E/F 转化为

• A - * B- C D / E F

• 从右往左扫描，直到处理完所有的元素
• 若扫描到操作数则压入栈，并回到上一步，否则执行下一步
• 若扫描到运算符，则弹出两个栈顶元素，指向相应运算，运算结果压会栈中，返回第一步

基本和后缀表达式一致

代码

中缀表达式转后缀表达式

• 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符
• 从左到右处理各个元素，直到末尾，可能遇到三种情况
  • 遇到操作数，直接加入后缀表达式
  • 遇到界限夫。遇到“(” 直接入栈；遇到")" 则依次弹出栈内运算符并加入后缀表达式，直到弹出"(".注意 “(” 不加入后缀表达式
  • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(” 或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

例子：

A+B-C*D/E+F
开始扫描
A 加入后缀表达式
 后缀表达式：A
 栈：空
扫描到+号，由于栈空，于是把+号压入栈中
 后缀表达式：A
 栈：+
扫描到B，加入后缀表达式
 后缀表达式：A B
 栈：+
扫描到-号，弹出+号加入后缀表达式，压入-号
 后缀表达式：A B +
 栈：-
扫描到C，压入栈中
 后缀表达式：A B + C
 栈：-
扫描到 * 号，-号比、*号优先级低，*直接压入栈中
 后缀表达式：A B + C
 栈：- *
扫描到D，加入后缀表达式
 后缀表达式：A B + C D
 栈：- *
扫描到/，弹出*，弹出-，把、压入栈中
 后缀表达式：A B + C D *
 栈：- /
扫描到E，加入后缀表达式
 后缀表达式：A B + C D * E
 栈：- /
扫描到+，弹出/，弹出-，压入 +
 后缀表达式：A B + C D * E / -  栈：+
扫描到F，加入后缀表达式
 后缀表达式：A B + C D * E / - F  栈：+
扫描结束，弹出+，加入后缀表达式
 后缀表达式：A B + C D * E / - F +  栈：空

大概这样一个过程，得到后缀表达式

带有括号的例子

A + B*(C-D)-E/F
跳过前面类似的几步
扫描到(，压入栈中
 后缀表达式：A B
 栈：+ * (
扫描到C，加入后缀表达式
 后缀表达式：A B C
 栈：+ * (
扫描到-，压入栈中，遇到(，直接压入栈
 后缀表达式：A B C
 栈：+ * ( -
扫描到D，加入后缀表达式
 后缀表达式：A B C D
 栈：+ * ( -
扫描到)，弹出-，加入后缀表达式。弹出(
 后缀表达式：A B C D -
 栈：+ *
扫描到-，弹出*，弹出-，压入-
 后缀表达式：A B C D - * +
 栈：-
扫描到E，加入后缀表达式
 后缀表达式：A B C D - E
 栈：-
扫描到/，压入栈中
 后缀表达式：A B C D - E
 栈：- /
扫描到F，加入后缀表达式
 后缀表达式：A B C D - E F
 栈：- /
扫描结束，弹出/， 弹出-
 后缀表达式：A B C D - E F / -
 栈：空

这样我们就通过栈得到了由中缀表达式得到后缀表达式的算法

在生成后缀表达式的同时可以计算值

栈的应用-递归

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

函数调用时，需要用一个栈存储：

• 调用返回地址
• 实参
• 局部变量

适合用“递归”算法解决的：可以把原问题转换为属性相同，但规模较小的问题：

• 计算正整数的阶乘
• 计算斐波那契数列

递归调用时，函数调用栈可称为“递归工作栈”
没进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息

太多层递归可能会导致栈溢出，可能会包含很多的重复运算

队列的应用

• 树的层次遍历
  到“树”之后还会再提到，这里只做了解
• 图的广度优先遍历
• 在操作系统中的应用

多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先进来先服务）是一种常用策略。

特殊矩阵的压缩存储

特殊矩阵：

• 对称矩阵
• 三角矩阵
• 三对角矩阵
• 稀疏矩阵

二维数组的存储策略：行优先存储、列优先存储

一个2×2的矩阵 行优先存储：（0，0）、（0，1）、（1，0）、（1，1）
列优先存储：（0，0）、（1，0）、（0，1）、（1，1）

对称矩阵

对称矩阵的压缩存储，由于对阵矩阵的特殊性，因此只需要存储上三角区域即可，按行优先原则将各元素存入一维数组B中即可
基于行优先：

这样只需要存n(n+1)/2个元素即可，具体访问的时候可以做一个映射

三角矩阵

三角矩阵是下三角矩阵为任意数，上三角区域除去对角线为相同的常数，因此我们可以在对称矩阵的基础上加一个位置，存放这个常量，其他都一样

三对角矩阵

三对角矩阵又被叫做带状矩阵，除了主对角线左边和右边以外的元素都为0。按行优先原则，只存储带状部分

稀疏矩阵

非零元素远远小于矩阵的元素的个数
顺序存储：通过三元组存储<行，列，值>，

链式存储：十字链表法
存了五个数据：行、列、值、指向同列下一个元素、下指向同行下一个元素