考研数据结构与算法（三）栈和队列¶
一、栈¶
栈是一种 后进先出（LIFO） 的线性结构，只允许在一端进行插入和删除等操作的线性结构
这个结构最重要的两个操作便是：push 和pop 因为其分别对应的是往结构中加入新元素以及删除结构中的元素，又由于栈的这个结构，这两个操作一般都是在栈顶做的操作，也如上图所示
也正是由于这两个操作，使得栈有一个出栈排列顺序的数据结构：
\(n\) 个不同元素进栈，出栈元素不同排列的个数为 \(\frac{C^n_{2n}}{n+1}\) 这个公式也被称为卡特兰数
说完了最重要的两个操作，我们接着来说栈的一些基本的操作（以严蔚敏老师的教材为例）
| 函数名 | 操作 |
|---|---|
InitStack(&S) |
初始化栈 |
StackEmpty(S) |
判断栈是否为空 |
Push(&S,x) |
入栈、若栈未满往栈 \(S\) 中放入元素 \(x\) |
Pop(&S,x) |
出栈、若栈未空将栈顶元素弹出 |
GetTop(&S,&x) |
若栈为空则将栈顶元素的值赋给 \(x\) |
DestroyStack(&S) |
销毁栈，并释放栈所用的空间 |
1.1 顺序栈¶
采用顺序存储的栈称为顺序栈（简单理解为用数组实现的），它通过一组地址连续的空间实现了栈这种先进后出的数据结构，一般这样的数据结构可以描述为：
#define MaxSize 100
struct Stack{
Elemtype data[MaxSize];
int top;
}S;
其中 data 数组表示的是栈的空间，而 top 表示的是栈顶的位置，通常来说栈顶的位置初始时（栈为空的时候）设置为 \(-1\) ，当然也有设置为 \(0\) 的，我们来讲若栈空设置为 \(-1\) 的情况：
- 进栈：若栈不满，则先将栈顶指针
top加 \(1\) 再将元素放入当前的位置 - 出栈：若栈不空，则当前元素指向的就是栈顶位置，先将当前元素赋给其他变量，再将栈顶指针
top减 \(1\) - 栈空：若栈为空，则栈顶指针
top的值为 \(-1\)
同理不难得到若栈空设置为 \(0\) 的情况：
- 进栈：若栈不满，则先将元素放入当前的位置再将栈顶指针
top加 \(1\) - 出栈：若栈不空，则当前元素指向的就是栈顶的下一个位置，先将栈顶指针
top减 \(1\) ，再将当前元素赋给其他变量 - 栈空：若栈为空，则栈顶元素指针
top的值为 \(0\)
其实当栈顶指针初始化为 \(-1\) 则
top代表的含义就是当前指向的位置就是栈顶的位置，而初始化为 \(0\) 则代表的含义是当前位置是栈顶位置的下一个位置。
1.1.1 顺序栈代码实现¶
1.1.1.1 初始化¶
将 top 指针归位即可，即置为 \(-1\)
void InitStack(struct Stack &S) {
S.top = -1;
}
1.1.1.2 判栈空¶
只需要判断 top 指针是否指向 \(-1\)
bool StackEmpty(struct Stack S) {
return S.top == -1;
}
1.1.1.3 进栈¶
按照上面分析的，如果栈未满，则先将指针往后移动一位，然后将新元素放入
bool Push(struct Stack &S,Elemtype x) {
if(S.top == MaxSize - 1) return false;//如果栈未满
S.data[++S.top] = x;
return true;
}
1.1.1.4 出栈¶
按照上面分析的，如果栈未空，先取出当前栈顶的元素，然后 top 指针往前移动一位
bool Pop(struct Stack &S,Elemtype &x) {
if(S.top == -1) return false;//如果栈未空
x = S.data[S.top--];
return true;
}
1.1.1.5 读栈顶元素¶
如果栈没空，则将栈顶元素复制给元素 \(x\)
bool GetTop(struct Stack &S,&x) {
if(S.top == -1) return false;
x = S.data[S.top];
return true;
}
1.2 链栈¶
由于顺序结构这种数据结构在空间的拓展上非常的麻烦或者有限，不好分配栈的大小，那么链栈则成为了便于扩展空间的结构，那么其实和链表的操作并无太大差别，若我们用 头插法 ，则栈顶元素就是头结点元素，而其他具体的操作如下：
- 进栈：将新的元素通过头插法插入链表中即可，此时头结点元素即为栈顶元素
- 出栈：如果栈不为空，将头节点元素删除即为出栈操作
- 栈空：我们只需要判断头指针的
next直至，如果指向NULL则表示栈为空，否则表示栈中有元素
1.2.1 链栈的代码实现¶
由于我们之前学习过链表的基本操作，那么我这里就直接使用之前实现的函数了
typedef struct Stack_Node{
ElemType data;//数据域
struct Stack_Node *next;//指针域
}Node;
1.2.1.1 初始化¶
从前往后遍历链表，并且将链表空间释放，最后将链表的头指针指向 NULL
void InitStack(Node *S) {
Node *p = S;
while(p->next) {
Node *t = p->next;
p = t->next;
free(t);
}
S->next = NULL
}
1.2.1.2 判栈空¶
看头指针指向的结点是否为空
void InitStack(Node *S) {
return S->next == NULL;
}
1.2.1.3 进栈¶
头部插入元素即可
bool Push(Node *S,Elemtype x) {
Node *t = (Node *)malloc(sizeof(Node));
t->data = x;
t->next = S->next;
S->next = t;
return true;
}
1.2.1.4 出栈¶
将头节点删除即可
bool Pop(Node *S) {
if(S->next == NULL) return false;
Node *t = S->next;
S->next = t->next;
free(t);
return true;
}
1.2.1.5 读取栈顶元素¶
如果栈不为空，那么就将栈顶元素赋值给 x
bool GetTop(Node *S,&x) {
if(S->next == NULL) return false;
x = S->next->data;
return true;
}
1.3 共享栈¶
因为栈底的位置不会发生改变，那么对于一个线性结构又是有两个方向的，那么我们两个方向分别作为栈底往中心靠齐则能提高一块空间的利用率，这其实就是共享栈，此时的共享栈需要设置top0 和 top1 分别表示两个方向的栈顶，那么此时的一些满栈和空栈的判断就发生了改变
当栈满时，即为：top1 - top0 == 1
当左栈空时，即为： top0 == -1
当右栈空时，即为： top1 == Maxsize
那么入栈和出栈的操作就不列举啦，和之前顺序栈一样的
具体结构如下图所示：
1.4 实际应用¶
1.4.1 进制转化¶
例如十进制转 \(x\) 进制，我们需要对当前的十进制不断取余，最后将这些余数倒序连接则成为了转换后的位数，这里为了方便简单实现一下
void conversion(int k,int x) {
stack<int> S;
while(k) {
S.push(k % x);
k /= x;
}
while(!S.empty()) {
printf("%d",S.top());
S.pop();
}
}
1.4.2 括号匹配¶
如果栈不为空，那么我们就将当前的元素和栈顶元素进行判断是否构成一个匹配，如果不构成那么就将当前元素放入栈中，继续等待下一个，如果发现匹配则将当前的栈顶元素出栈操作，并且不讲当前的元素放入栈中，因为其构成了一个匹配，最后如果我们发现栈中还有元素则说明括号不能匹配，假设这里只有一种括号( 和)
bool check(string str) {
stack<char> S;
for(int i = 0,l = str.size();i < l; ++i) {
if(S.empty()) continue;
if(S.top == '(' && str[i] == ')'){
S.pop();
continue;
}
S.push(str[i]);
}
return S.size() == 0;
}
1.4.3 表达式求值¶
这个是一个经典问题了，给定一个只有加减乘除中缀表达式，或者后缀表达式，然后我们计算这个表达式的值
- 对于中缀来说：
例题：Problem - 1237 (hdu.edu.cn)
代码：
#include<bits/stdc++.h>
using namespace std;
char ch[205];
int main(void) {
stack<double>a;
stack<char>b;
while (gets(ch) != nullptr) {
int flag = 0;
int len = strlen(ch);
if (len == 1 && ch[0] == '0')
return 0;
for (int i = 0; i < len; i++) {
if (ch[i] == ' ')
continue;
if (isdigit(ch[i])) {
double kk = 0;
while (isdigit(ch[i]))
kk = kk * 10 + ch[i++] - '0';
i--;
if (flag == 1)
a.top() *= kk;
else if (flag == 2)
a.top() /= kk;
else if (flag == 3)
a.push(-kk);
else
a.push(kk);
flag = 0;
} else {
if (ch[i] == '+' || ch[i] == '-') {
b.push('+');
if (ch[i] == '-')
flag = 3;
} else {
if (ch[i] == '*')
flag = 1;
else if (ch[i] == '/')
flag = 2;
}
}
}
while (b.size() && a.size() > 1) {
if (b.top() == '+') {
double x = a.top();
a.pop();
a.top() += x;
}
b.pop();
}
printf("%.2lf\n", a.top());
a.pop();
memset(ch, 0, sizeof(ch));
}
return 0;
}
- 对于后缀来说
例题：P1449 后缀表达式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
代码：
#include <cstring>
#include <iostream>
#include <stack>
using namespace std;
string str;
stack<int> p;
int t, times;
int get(int i) { //获取字符串中数字的函数
int j = i;
int key = str[i] - '0';
for (i++; i < str.length(); ++i) { //模拟取值
if (str[i] >= '0' && str[i] <= '9') {
key = key * 10 + str[i] - '0';
} else
break;
}
times = i - j;//主串中要跳过的字符数
return key;
}
int main(void) {
ios::sync_with_stdio(false);
int sum = 0;
cin >> str;
for (int i = 0; i < str.length(); ++i) {
if (str[i] >= '0' && str[i] <= '9') {
t = get(i);
p.push(t);//把结果push进去
i += times;//跳过无用字符
} else if (str[i] == '+') {
sum = p.top();
p.pop();
sum += p.top();
p.pop();
p.push(sum);
} else if (str[i] == '-') {
sum = p.top();
p.pop();
sum = p.top() - sum;
p.pop();
p.push(sum);
} else if (str[i] == '*') {
sum = p.top();
p.pop();
sum *= p.top();
p.pop();
p.push(sum);
} else if (str[i] == '/') {
sum = p.top();
p.pop();
sum = p.top() / sum;
p.pop();
p.push(sum);
} else if (str[i] == '@')
break;
}
cout << p.top() << endl;//栈中必定只有一个元素
return 0;
}
1.4.4 递归¶
递归算是栈的一个非常重要的应用，我们通过递归可以实现函数调用自己本身，这样可以让我们通过分治来完成一些底层重复性的操作，或者说是一些子问题，只不过子问题的规模没有原问题那么大，但是原问题能拆成若干个 有限的子问题
最出名的一个问题便是 Fibonacci数列 ，即 \(f(n) = f(n-1) + f(n-2)\) 假设我们求 \(f(4)\) 那么我们就得求 \(f(3)\) 和 \(f(2)\) 而 \(f(3)\) 又是由 \(f(2)\) 和 \(f(1)\) 推来的于是我们将一个问题划分成了一系列小的问题，但是只不过是数值变小了，这就叫子问题，当然 \(f(1)\) 和 \(f(2)\) 是我们预先知道的，即小范围的数据我们是已经求出的，那么递的过程就是我们的入栈操作，而归的过程就是出栈操作，对于上述问题我们用递归函数求解如下：
int Fib(int n) {
if(n == 0 || n == 1) return 1;//递归的出口
return Fib(n-1) + Fib(n-2);
}
1.5 单调栈¶
顾名思义，单调栈即满足单调性的栈结构。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈，就满足后进先出的特点。与之相对应的是单调队列。
更多信息请参考：https://acmer.blog.csdn.net/article/details/118891706
二、队列¶
队列是一种 先进先出（FIFO） 的线性结构，只允许在一端进行插入和删除等操作的线性结构
和栈类似，也是有 push 和 pop 两个重要的操作，不同的是栈是一个方向进同样是那一个方向出，但是队列有一个队首和队尾的概念（和我们平时的概念一样）对于队首是我们允许删除的一端，而队尾则是允许插入的一段，如上图所示，左边则是队尾，右边是队首
队列的常用函数
| 函数名 | 操作 |
|---|---|
InitQueue(&Q) |
初始化队列 |
QueueEmpty(Q) |
判断队列是否为空 |
Push(&Q,x) |
入队、若队列未满则往栈 \(S\) 中放入元素 \(x\) |
Pop(&Q,x) |
出队、若队列未空将队首元素弹出 |
GetHead(&Q,&x) |
若队列为空则将队首元素的值赋给 \(x\) |
2.1 顺序队列¶
使用顺序存储结构的队列即为顺序队列，结构和顺序栈类似：
#define MaxSize 100
struct Queue {
ElemType data[MaxSize];
int front,rear;
}
如果是普通的队列的话我们很容易遇到溢出的问题，因为当我们不断的入队和出队的操作的过程中会使得 front 和 rear 指针往后移动，显然当移动到 \(MaxSize - 1\) 的时候我们就得停下来了，而前面空出来的空间我们不能使用，使得这个队列变成一次性的队列，所以我们在处理的时候一般是按照循环队列的方式处理
2.1.1 代码实现¶
2.1.1.1 初始化¶
初始化将头尾指针都置为0
void InitQueue(struct Queue &Q) {
Q.front = Q.rear = 0;
}
2.1.1.2 判队列空¶
只需要判断 front 和 rear 的位置是否相同即可
bool isEmpty(struct Queue &Q) {
return Q.front == Q.rear;
}
2.1.1.3 入队¶
先判断队首和队尾的位置关系是否造成队列空间占满，如果未占满则需要将元素放入队列，并将 rear 指针后移
bool EnQueue(struct Queue &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;
}
2.1.1.4 出队¶
出队则需先判断队列是否为空，若为不空则将 front 指针往前移动
bool DeQueue(struct Queue &Q, ElemType x) {
if(Q.front == Q.rear) return false;
x = Q.data[Q.front];
Q.front = (Q.front - 1) % MaxSize;
return true;
}
2.2 链式队列¶
链式队列的话和普通链表并无差别，只不过可以新增一个尾指针方便我们对出队进行操作，对于 入队操作我们可以看作是尾插法 ，对于出队操作我们可以看作将头节点删除 这样的话我们就将链表的右边作为了队尾，左边则作为了队首，这样其实是方便我们进行操作的
具体的操作方法我也就不在赘述，就是链表的基础操作
2.3 循环队列¶
循环队列和循环链表相对应，不过稍有不同的是，对于循环队列而言只是元素的扩张往一个方向移动，因为随着我们入队出队操作，我们的队列区间位置是会发生改变的，那么此时我们就能将这段连续的空间利用起来，而不会出现到达边界就不能进行操作的情况，当然这样也会使得队首和队尾这个区间可能出现在这个连续空间的任何位置，那么我们怎么判断 队空 和 队满 的状态呢？其实这里有两种处理方式
2.3.1 牺牲单元¶
牺牲一个单元来区分队空和队满，入队时才少用一个队列单元，这是一种较为普遍的做法，约定以 队头指针在队尾指针的下一位置作为队满的标志 如下图所示
队满条件： (Q.rear + 1) % MaxSize == Q.front
队空条件：Q.front == Q.rear
队列中元素个数： (Q.rear - Q.front + MaxSize) % MaxSize
2.3.2 新增元素¶
类型中增设表示元素个数的数据成员
size
队满的条件为 size==MaxSize
队空的条件为 Q.size == 0，或者 Q.front==Q.rear
2.4 双端队列¶
和上面的共享栈思路类似，既然对于一个线性结构左边可以当队首，右边当队尾，那么新来的元素只能从右边进去，获取元素也只能从队首即左边获取，假设我们需要将新来的元素放在队首，或者说我们想取出队尾的元素，这个时候就需要用到双端队列了，让两边都同时成为队首和队尾，方便我们对两头进行操作，这个其实可以和我们之前学的双向链表连接起来，具体结构如下图：
2.5 实际应用¶
2.5.1 层序遍历¶
当我们想实现树或图层序遍历的时候，我们可以通过队列将当前这一层先加入队列，然后不断的出队，并且将出队元素的所有未访问的临近结点放入队尾，这样我们就能得到一个图的层序遍历结果，这个层序遍历的基础数据结构就是队列，因此有了 \(BFS\) 算法
2.5.2 系统应用¶
队列在计算机系统中的应用非常广泛，以下仅从两个方面来简述队列在计算机系统中的作用：
- 第一个方面是解决主机与外部设备之间速度不匹配的问题
由于输出数据的速度比打印数据的速度要快得多，于是需要一个缓冲的过程来加快速度，这个缓存的数据结构就是队列
- 第二个方面是解决由多用户引起的资源竞争问题
操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把 \(CPU\) 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把 \(CPU\) 分配给新的队首请求的用户使用 。这样既能满足每 个用户的请求，又使 \(CPU\) 能够正常运行。