专题篇|栈与队列详解
发布网友
发布时间：2023-09-12 17:01
共1个回答
热心网友
时间：2023-09-20 04:08
栈和队列是两种常见的数据结构，它们分别用于解决不同类型的问题。在程序设计中，栈和队列都是非常重要的数据结构，因为它们可以帮助我们解决很多实际的问题。
栈：
首先，让我们来讨论栈, 栈是一种后进先出（ LIFO ）的数据结构，它是一种线性的、有序的数据结构。栈的基本操作有两个，即入栈和出栈。
入栈指将元素放入栈顶，出栈指将栈顶元素取出。栈的本质是一个容器，它可以存储任何类型的数据，但是栈的大小是固定的，因为它的元素只能在栈顶添加或删除。
栈有许多应用场景，比如我们在浏览网页时，可以使用浏览器的 “返回” 功能，这就是栈的应用之一。
当我们浏览网页时，每次点击链接都会将新的页面加入到栈中，而当我们点击 “返回” 按钮时，就会将栈顶的页面弹出，这样就可以回到之前的页面了。另外，栈还可以用于括号匹配、表达式求值等问题的解决。
队列：
接下来，我们来介绍队列。队列是一种先进先出（ FIFO ）的数据结构，它与栈相似，也是一种线性的、有序的数据结构。队列的基本操作有三个，即入队、出队和查看队首元素。
入队指将元素放入队尾，出队指将队首元素取出。队列的本质也是一个容器，它可以存储任何类型的数据，但是队列的大小也是固定的。
队列也有很多应用场景，比如操作系统中的进程调度。操作系统中有很多进程需要运行，操作系统通过队列来管理这些进程。
当一个进程需要运行时，就将它加入到队列的队尾，当操作系统分配到一个 CPU 时，就将队首的进程取出来运行，这样就可以保证每个进程都能得到运行的机会。
除了以上应用场景外，栈和队列还有很多其他的应用，比如栈还可以用于实现递归算法，队列用于广度优先搜索等。下面就让我们通过几个经典问题深入了解栈和队列吧！
经典问题 （一）
题目描述：验证栈序列
给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true ；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5] , popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：push(1) , push(2) , push(3) , push(4) , pop() -> 4 , push(5) , pop() -> 5 , pop() -> 3, pop() -> 2 , pop() -> 1 。
示例 2：
输入：
pushed = [1,2,3,4,5] , popped = [4,3,5,1,2]
输出：
false
解释：
1 不能在 2 之前弹出。
提示：
1 <= pushed.length <= 1000 0 <= pushed[i] <= 1000 pushed 的所有元素互不相同 popped.length == pushed.length popped 是 pushed 的一个排列。
解析：
只要模拟入栈和出栈的过程，将一个数进行入栈操作的时候检查该数是否为下一个要出栈的数，如果是就弹出该数，并继续检查栈中的数。如果能扫描完所有要出栈的数，就是一个合法的栈序列。
Java 代码实现：（使用 ArrayList 模拟栈）
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
List<Integer> S=new ArrayList<>();
int j=0;
for(int i=0;i<pushed.length;i++){
S.add(pushed[i]);
while(S.size()>0&&j<popped.length&&S.get(S.size()-1)==popped[j]){
S.remove(S.size()-1);
j++;
}
}
return j==popped.length;
}
}
C++ 代码实现：（直接用 STL stack ）
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int>S;
int n=pushed.size();
int j=0;
for(int i=0;i<n;i++){
S.push(pushed[i]);
while(S.size()>0&&j<n&&S.top()==popped[j]){
S.pop();
j++;
}
}
return j==n;
}
};
经典问题（二）
题目描述：堆宝塔
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小，按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下：
首先准备两根柱子，一根 A 柱串宝塔，一根 B 柱用于临时叠放。把第 1 块彩虹圈作为第 1 座宝塔的基座，在 A 柱放好。将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下，如果比最上面的小，就直接放上去；
否则把 C 跟 B 柱最上面的彩虹圈比一下：如果 B 柱是空的，或者 C 大，就在 B 柱上放好；否则把 A 柱上串好的宝塔取下来作为一件成品；
然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上，最后把 C 也放到 A 柱上。重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。
问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？
重复此步骤，直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品，B 柱上剩下的彩虹圈被逐一取下，堆成另一座宝塔。
问：宝宝一共堆出了几个宝塔？最高的宝塔有多少层？
输入格式：
输入第一行给出一个正整数 N ，为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N 个不超过 100 的正整数，对应每个彩虹圈的直径。
输出格式：
在一行中输出宝宝堆出的宝塔个数，和最高的宝塔的层数。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
11
10 8 9 5 12 11 4 3 1 9 15
输出样例：
4 5
样例解释：
宝宝堆成的宝塔顺次为：
10、8、5
12、11、4、3、1
9
15、9
解析：
根据题意，使用两个栈进行模拟操作即可。
#include<bits/stdc++.h>
using namespace std;
stack<int>a,b;
int n,x,maxx,sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(a.empty()){
a.push(x);
continue;
}
if(x<a.top()){
a.push(x);
}
else{
if(b.empty()||x>b.top()){
b.push(x);
}
else{
sum++;
if(a.size()>maxx)
maxx=a.size();
while(a.size()>0){
a.pop();
}
while(b.size()>0&&b.top()>x){
int h=b.top();
b.pop();
a.push(h);
}
a.push(x);
}
}
}if(!a.empty()){
sum++;
if(a.size()>maxx)
maxx=a.size();
}
if(!b.empty()){
sum++;
if(a.size()>maxx)
maxx=b.size();
}
cout<<sum<<' '<<maxx;
}
经典问题（三）
题目描述：银行业务队列简单模拟
设某银行有 A 、B 两个业务窗口，且处理业务的速度不一样，其中 A 窗口处理速度是 B 窗口的 2 倍 —— 即当 A 窗口每处理完 2 个顾客时，B 窗口处理完 1 个顾客。
给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完 2 个顾客时，A 窗口顾客优先输出。
输入格式 :
输入为一行正整数，其中第 1 个数字 N (≤1000) 为顾客总数，后面跟着 N 位顾客的编号。编号为奇数的顾客需要到 A 窗口办理业务，为偶数的顾客则去 B 窗口，数字间以空格分隔。
输出格式 :
按业务处理完成的顺序输出顾客的编号，数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例 :
8 2 1 3 9 4 11 13 15
输出样例：
1 3 2 9 11 4 13 15
解析：
根据题意，用两个队列模拟银行窗口处理业务，输出顺序总是按照 A 先 B 后，即 A 窗口先处理最多 2 个顾客，B 窗口再处理最多 1 个顾客。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int first=1;
void print(int x){
if(first){
first=0;
printf("%d",x);
}
else
printf(" %d",x);
}
int main(){
queue<int> p1,p2;
int n,x,w;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
if(x%2)
p1.push(x);
else
p2.push(x);
}
while(1){
if(p1.empty()||p2.empty())
break;
if(!p1.empty()){
w=p1.front();
p1.pop();
print(w);
}
if(!p1.empty()){
w=p1.front();
p1.pop();
print(w);
}
if(!p2.empty()){
w=p2.front();
p2.pop();
print(w);
}
}
while(!p1.empty()){
w=p1.front();
p1.pop();
print(w);
}
while(!p2.empty()){
w=p2.front();
p2.pop();
print(w);
}
}
还有一种比较特殊的队列称为双端队列，在入队或出队操作时的位置可以是队头也可以是队尾，经常和 BFS 结合起来，解决一些常见的算法问题。
经典问题（四）
题目描述：拖拉机
干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地*了。他的奶牛非常调皮，决定对约翰来场恶作剧。她们在田地的不同地方放了 N 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。拖拉机的位置以及 N 捆干草的位置都是二维平面上的整数坐标点。
拖拉机的初始位置上没有干草捆。当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（ 北，南，东和西 ）移动拖拉机，并且拖拉机必须每次移动整数距离。
例如：驾驶拖拉机先向北移动 2 单位长度，然后向东移动 3 单位长度。
拖拉机无法移动到干草捆占据的位置。请帮助约翰确定他需要移除的干草捆的最小数量，以便他能够将拖拉机开到二维平面的原点。
输入格式 ：
第一行包含三个整数：N ，以及拖拉机的初始位置 ( x , y ) 。接下 N 行，每行包含一个干草捆的位置坐标 ( x , y ) 。
输出格式 ：
输出约翰需要移除的干草捆的最小数量。
数据范围 ：
1 ≤ N ≤ 50000
1 ≤ x , y ≤ 1000
输入样例：
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4
输出样例：
1
还有一种比较特殊的队列称为双端队列，在入队或出队操作时的位置可以是队头也可以是队尾，经常和 BFS 结合起来，解决一些常见的算法问题。
#include<bits/stdc++.h>
using namespace std;
bool vis[1010][1010];
int G[1010][1010];
int x,y,sx,sy,n;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int res,tx,ty;
int dist[1010][1010];
struct node{
int x;
int y;
int dis;
};
deque<node>Q;
node t;
int main(){
scanf("%d%d%d",&n,&sx,&sy);
res=n;
while(n--){
scanf("%d%d",&x,&y);
G[x][y]=1;
}
node S;
S.x=sx,S.y=sy,S.dis=0;
Q.push_back(S);
vis[sx][sy]=1;
while(!Q.empty()){
node h=Q.front();
Q.pop_front();
if(h.x==0&&h.y==0){
printf("%d",h.dis);
return 0;
}
for(int i=0;i<4;i++){
tx=h.x+dir[i][0];
ty=h.y+dir[i][1];
if(tx<0||tx>=1005||ty<0||ty>=1005||vis[tx][ty])
continue;
vis[tx][ty]=1;
t.x=tx,t.y=ty;
if(G[tx][ty]){
t.dis=h.dis+1;
Q.push_back(t);
}
else{
t.dis=h.dis;
Q.push_front(t);
}
}
}
}
如果栈 / 队列的数满足一定的单调性，则叫做单调栈 / 单调队列。在处理某些算法问题时还可能需要用到单调性，例如面试中常常遇到的滑动窗口求最大 / 最小值问题。使用单调栈 / 单调队列需要时刻保证其中所有数的单调性，一旦不满足单调性就要执行弹出操作。
单调栈例题：单调栈
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1 。
输入格式：
第一行包含整数 N ，表示数列长度。第二行包含 N 个整数，表示整数数列。
输出格式：
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1 。
数据范围 ：
1 ≤ N ≤ 10^5
1 ≤ 数列中的元素 ≤ 10^9
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
解题代码：
#include<bits/stdc++.h>
using namespace std;
int a[100010],res[100010],n;
stack<int>S;
stack<int>id;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(res,-1,sizeof(res));
for(int i=n;i>=1;i--){
while(!S.empty()&&a[i]<S.top()){
res[id.top()]=a[i];
S.pop();
id.pop();
}
S.push(a[i]);
id.push(i);
}
for(int i=1;i<=n;i++){
printf("%d ",res[i]);
}
}
经典问题（五）
题目描述 ：滑动窗口
给定一个大小为 n ≤ 10^6 数组。有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。你只能在窗口中看到 k 个数字。每次滑动窗口向右移动一个位置。
以下是一个例子：该数组为 [1 3 -1 -3 5 3 6 7] ，k 为 3 。你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式：
输入包含两行。第一行包含两个整数 n 和 k ，分别代表数组长度和滑动窗口的长度。第二行有 n 个整数，代表数组的具体数值。同行数据之间用空格隔开。
输出格式：
输出包含两个。第一行输出，从左至右，每个位置滑动窗口中的最小值。第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
解题代码：
#include <bits/stdc++.h>
using namespace std;
int n,k,a[500010];
deque<int>q;
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
if(!q.empty()&&i-q.front()>=k)
q.pop_front();
while(!q.empty()&&a[i]<=a[q.back()])
q.pop_back();
q.push_back(i);
if(i>=k)
printf("%d ",a[q.front()]);
}
printf("\n");
while(!q.empty())
q.pop_back();
for(int i=1;i<=n;i++){
if(!q.empty()&&i-q.front()>=k)
q.pop_front();
while(!q.empty()&&a[i]>=a[q.back()])
q.pop_back();
q.push_back(i);
if(i>=k)
printf("%d ",a[q.front()]);
}
}
单调栈 / 单调队列还有更加广泛的运用，例如某些动态规划问题需要使用单调队列进行优化，这类问题将在动态规划专题中再展开介绍。
总结：
不管是刚接触计算机的大学生还是准备求职面试的程序员，栈和队列的概念和应用是一定要掌握的，它们最基础的数据结构，理解了这些数据结构的用法，就能在各种编程问题中加以应用。
总之，栈和队列是非常重要的数据结构，它们可以帮助我们解决很多实际的问题。在程序设计中，如果能熟练地使用栈和队列，对于提高程序的效率和可读性都会有很大的帮助。本期栈与队列专题你 Get 了吗？
