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