棧和隊列是兩種常見的數據結構，它們分別用於解決不同類型的問題。在程序設計中，棧和隊列都是非常重要的數據結構，因為它們可以幫助我們解決很多實際的問題。
棧：
首先，讓我們來討論棧, 棧是壹種後進先出（ 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 了嗎？