【算法基礎課】數組模拟棧、隊列

文章目錄

• 一、數組模拟棧
• • 1.思路
  • 2.代碼模闆
  • 3.進階：單調棧
• 二、數組模拟隊列
• • 1.思路
  • 2.代碼模闆
  • 3.進階：單調隊列

一、數組模拟棧

1.思路

用數組模拟棧，可以幫助我們了解棧的本質。

模拟棧的關鍵點就是“棧頂指針”！這比連結清單簡單多了，連結清單需要知道頭尾、每個節點的前後指針，而棧隻有一個指針！

随着不斷地push和pop，棧頂指針會不斷向後移動，前面的空間就浪費了。這對于算法題來說是可以忍受的，畢竟更看重時間效率。

2.代碼模闆

#include<iostream>
#include<string>
using namespace std;

const int N=1e6+10;
int m;
int stk[N],tt;//stk模拟棧，tt模拟棧頂指針

void clear(){
    tt=-1;//初始化，棧頂指針指向空
}
void push(int x){
    stk[++tt]=x;//棧頂指針+1，指派新的棧頂元素
}
void pop(){
    tt--;//棧頂指針-1
}
bool empty(){
    if(tt>=0)cout<<"NO"<<endl;//棧頂指針不為空，棧就不為空
    else cout<<"YES"<<endl;
}
void query(){
    cout<<stk[tt]<<endl;//每次查詢隻能找到棧頂元素
}

int main(){
    scanf("%d",&m);
    clear();
    while(m--){
        string str;int x;
        cin>>str;
        if(str=="push"){
            cin>>x;
            push(x);
        }else if(str=="pop"){
            pop();
        }else if(str=="query"){
            query();
        }else if(str=="empty"){
            empty();
        }
    }
    //【周遊/依次彈出棧】
    while(tt>-1){
       cout<<stk[tt--]<<endl;
    }
    return 0;
}
           

3.進階：單調棧

要求： 輸出每個數字左邊第一個比它小的數字。

思路： 暴力解法是，對于第i個數，從第i-1個數開始向左周遊，直到遇到一個比它小的數。我們可以這樣一個性質，如果第i個數左邊某個數比它大，那這個數永遠不會被輸出。對于i來說當然不能輸出，對于i以後的數，也不會輸出，是以可以直接删掉。

基于此，我們可以把數組中的每個數放入棧裡面，對于新的數，如果棧頂比它大，就彈出。這樣最後得到的就是一個單調遞增的棧。當然，我們的答案也很容易就出來了。

代碼模闆

#include<iostream>
using namespace std;

const int N=1e5+10;
int tt=-1,stk[N];

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        //檢視棧，如果不為空，看棧頂元素是不是比它大，如果是，就彈出棧頂元素
        while(tt!=-1&&stk[tt]>=x)tt--;
        if(tt!=-1){//如果此時棧不為空，棧頂元素就是我們要找的最近的比x小的數
            cout<<stk[tt]<<" ";
        }else cout<<-1<<" ";
        stk[++tt]=x;
    }
    return 0;
}
           

二、數組模拟隊列

1.思路

用數組模拟隊列，關鍵是“隊頭指針”和“隊尾指針”。隊尾初始化為-1，随着不斷添加元素，隊尾指針不斷向後移動，就像棧頂指針一樣。而隊頭呢，在添加新元素的時候是不變的，是以一開始就要指向index為0的位置。

如果直接取隊頭的元素，此時隊列可能為空。那怎麼判斷隊列為空呢？直接判斷隊尾指針是否為-1嗎？錯了！要判斷隊尾指針和隊頭指針的關系，隊列為空的時候隊尾>隊頭。

随着不斷地push、pop，隊尾和隊頭的指針會不斷地後移，前面的空間就浪費了。這對于算法題來說，是可以忍受的。當然還有循環隊列這種解決方式。

2.代碼模闆

#include<iostream>
#include<string>
using namespace std;

const int N=1e6+10;
int q[N],hh=0,tt=-1;

void clear(){
    hh=0,tt=-1;
}
void push(int x){
    q[++tt]=x;//向隊尾插入一個元素
}
void pop(){
    hh++;//初始時，設定隊頭>隊尾。元素為1時，hh=tt=0。元素為2時，hh=0，tt=1；
}
void empty(){
    if(hh<=tt)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
}
bool isEmpty(){
    if(hh<=tt)return false;
    else return true;
}
void query(){
    if(!isEmpty())cout<<q[hh]<<endl;
}
int main(){
    int m;
    scanf("%d",&m);
    clear();
    while(m--){
        string str;int x;
        cin>>str;
        if(str=="push"){
            cin>>x;
            push(x);
        }else if(str=="pop"){
            pop();
        }else if(str=="query"){
            query();
        }else if(str=="empty"){
            empty();
        }
    }
    //【周遊/依次彈出隊頭元素】
    // while(!isEmpty()){
    //   cout<<q[hh]<<endl;
    // }
    return 0;
}
           

3.進階：單調隊列

要求： 給定一個大小為n≤106的數組。有一個大小為k的滑動視窗，它從數組的最左邊移動到最右邊。您隻能在視窗中看到k個數字。每次滑動視窗向右移動一個位置。您的任務是确定滑動視窗位于每個位置時，視窗中的最大值和最小值。

思路： 暴力解法是，維護滑動視窗為一個普通隊列，每次添加和删除一個數，并線性周遊，得到k個數中的最大值和最小值。然而我們可以這樣一個性質，如果将一個新的數添加到滑動視窗中，若這個數左邊某個數比它大，那該數永遠不會被輸出。是以我們可以把滑動視窗中比新的數大的數字都删掉。

基于此，滑動視窗就變成了一個單調遞增的隊列。隊頭是最小值，隊尾是最大值。

代碼模闆

【注意】為什麼要進行兩次呢？因為每次隻能得到該視窗的一種最值。比如，[1,3,-1],-3。當i==2，指向-1時，我們要求最小值，此時，我們已經把隊列删的隻剩下{-1}了。正确的最大值早就被删掉啦！

#include<iostream>
using namespace std;

const int N=1e6+10;
int n,k;
int a[N],q[N];//原數組和滑動視窗隊列

int main(){
    //【1】讀入原數組的值
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    //【2】輸出最小值
    //<1>定義單調隊列的頭和尾指針
    int hh=0,tt=-1;
    
    //<2>周遊元素組中的每個元素
    for(int i=0;i<n;i++){
        
        //<3>去掉隊頭元素
        if(hh<=tt&&(q[hh]<i-k+1))hh++;//隊列不為空，且，隊頭元素的index已經小于目前的index減去k的長度了。
        //比如，k=3.當i==3時，視窗為(1,2,3),i=0已經不在視窗中了。
        
        //<4>去掉隊中的備援元素
        while(hh<=tt&&a[q[tt]]>a[i]) tt--;//單調遞增序列，左邊的值應該小于等于右邊的值才對
        
        //<5>添加隊尾元素
        q[++tt]=i;
        
        //<6>到達第一個視窗時，輸出最小值
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");
    
    //【3】輸出最大值
    hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&(q[hh]<i-k+1))hh++;
        while(hh<=tt&&a[q[tt]]<a[i]) tt--;//單調遞減序列
        q[++tt]=i;
        if(i>=k-1)printf("%d ",a[q[hh]]);//隊頭是最大值
    }
    puts("");
    
    return 0;
}