专题篇｜栈与队列详解

~

栈和队列是两种常见的数据结构，它们分别用于解决不同类型的问题。在程序设计中，栈和队列都是非常重要的数据结构，因为它们可以帮助我们解决很多实际的问题。

栈：

首先，让我们来讨论栈, 栈是一种后进先出（ 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("
");

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 了吗？

java学习路线
答：Java学习路线一般有以下几个阶段：第一阶段，JavaSE基础：Java环境搭建、Java流程控制语句-for循环、switch选择判断、循环嵌套、数组拷贝等。第二阶段，JavaWeb：MySQL安装、管理、创建数据库、MySQLUPDATE查询、Mysql高级操作等。第三阶段，Java高级框架-SSH：Struts2异常处理、Struts2+Log4j集成、Struts2和...

java培训要学习哪些内容?
答：如需java培训推荐选择【达内教育】，java培训要学习以下几点内容：1、Java基础：Java语言基础知识的学习和应用，Java使用技巧、集合框架与数据结构，数据库理论与应用、互联网网站及信息系统的开发与应用等。2、Java中级：企业团队项目协同开发与维护、商业项目模块化基础与应用、软件项目测试与实施和企业主流...

Oracle数据库精讲与疑难解析的图书目录
答：7.2.3 请求队列(Request Queue)/响应队列(Response Queue)7.2.4 调度进程(Dispatcher Processes,Dnnn)7.2.5 共享服务器进程(Shared Server Processes,Snnn)...17.5 参数管理 与疑难解析第6篇 Oracle高级专题第18章 全球应用——分布式数据库疑难攻略18.1 分布式数据库系统的概念18.1.1 同构分布式数据库系统18.1.2 ...

基于java jsp asp php vb安卓系统毕业设计与实现论文源码下载?
答：基于人脸识别的签到系统的设计与实现 ?智慧校园语音交互系统的设计与实现 ?基于Android的旅游车服务程序的设计与实现 ?基于Unity的2D 平台动作游戏的设计与实现 ?基于IOS平台的校园社区生活APP的设计与实现 ?点播影院运营系统的设计与实现 ?基于javaweb的任务流程辅助系统 ?基于移动端的英语口语学习软件设计实现 ?中国...

求java学习路线图?
答：学习Java推荐选择【达内教育】，该机构是引领行业的职业教育公司，致力于面向IT互联网行业培养人才。Java培训学习路线如下：1、Java基础：【Java语言基础知识】的学习和应用Java使用技巧、集合框架与数据结构、信息系统的开发与应用等。2、Java中级：企业团队项目协同开发与维护、商业项目模块化基础与应用、软件...

软件工程一般要学什么
答：软件工程 软件工程是一门研究用工程化方法构建和维护有效的、实用的和高质量的软件的学科。它涉及程序设计语言、数据库、软件开发工具、系统平台、标准、设计模式等方面。在现代社会中，软件应用于多个方面。典型的软件有电子邮件、嵌入式系统、人机界面、办公套件、操作系统、编译器、数据库、游戏等。同时，...

适合初学者的c++视频教程
答：2)链表专题,内容涉及:链表顺序存储的设计与实现,链表链式存储的设计与实现(单向链表linklist、循环链表circlelist、双向链表Dlinklist),C版本和C++两个版本。3)栈专题,内容涉及:栈顺序存储设计与实现、栈链式存储设计与实现;C版本和C++两个版本。栈的应用典型案例:中缀表达式、后缀表达式。4)队列专题,内容涉及:队列...