C++ 資料結構 Stack & Queue

作者:

Stack，又稱作堆疊，顧名思義就是從上面(也可以說前面)放入與取出的資料結構。 Queue，稱為佇列，是從前面放後面取出的資料結構。

實作程式碼如下

#include<bits/stdc++.h>
using namespace std;

template<class T>
class Stack{
    private:
        int t=-1;
        vector<T> dt;
    public:
        T top(){
            if(t!=-1){
                return dt[t];
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void pop(){
            if(t!=-1){
                t--;
                dt.pop_back();
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void push(T p){
            t++;
            dt.push_back(p);
        }
};

template<class T>
class Queue{
    private:
        deque<T> dt;
    public:
        T front(){
            if(!dt.empty()){
                return dt.front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void pop(){
            if(!dt.empty()){
                dt.pop_front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void push(T p){
            dt.push_back(p);
        }
};

C++已經幫你將這兩個資料結構實做好了，以下示範例程式碼

#include<iostream>
#include<stack>
#include<queue>
#include<deque>

using namespace std;

int main(){
    stack<int> st;
    for(int i=0;i<10;++i){
        st.push(i);
    }
    cout<<st.size()<<"\n";
    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<"\n\n";

    queue<int> q;
    for(int i=0;i<10;++i){
        q.push(i);
    }
    cout<<q.size()<<"\n";
    while(!q.empty()){
        cout<<q.front()<<" "<<q.back()<<"\n";
        q.pop();
    }
    cout<<"\n";
}

光聽這兩個介紹以及大部分的分享，相信你還是不知道這兩個東西要用在哪裡。以下會有幾個應用的範例，都是用 STL 。

1.在 O(N) 的複雜度下做單調對列 Ex : 洛谷

題目敘述：
對於每個元素，從後面找出第一個比他大的元素的位置

這題就是要透過 stack 保持裡面所存位置對應的元素的單調遞減性。實際做法就是，遇到比他大的就丟掉，反正已經確認現在這個元素已經比他大了，後面也不會用到。否則他就還沒遇到還沒遇到比他大的。

以下為程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;++i) cin>>v[i];

    vector<int> ans(n,0);
    stack<int,vector<int>> st;
    for(int i=0;i<n;++i){
        while(!st.empty() && v[st.top()]<v[i]){
            ans[st.top()]=i+1;
            st.pop();
        }
        st.push(i);
    }

    for(int a:ans)
        cout<<a<<" ";
}

2.以 O(N) 在滑動窗口中找最大以及最小值 Ex : 洛谷

題目敘述：
在所有長度為k的窗口中找到最大以及最小值

這題要用deque(double-ended-queue)，也就是雙向佇列，是一個從前後方都可以加入以及刪除值的queue。用以維持內部元素既在範圍以內，又保持單調遞增或遞減。

以下為程式碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int nm[1000010]={0},rmax[1000010],rmin[1000010];

int main(){
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>nm[i];

    deque<int> mx,mn;

    for(int i=0;i<k;i++){
        while(!mx.empty() && nm[mx.front()]<nm[i])
            mx.pop_front();
        mx.push_front(i);

        while(!mn.empty() && nm[mn.front()]>nm[i])
            mn.pop_front();
        mn.push_front(i);
    }

    rmax[0]=mx.back();
    rmin[0]=mn.back();

    for(int i=1,j=k;j<n;i++){

        while(!mx.empty() && mx.back()<i)
            mx.pop_back();
        while(!mn.empty() && mn.back()<i)
            mn.pop_back();

        while(!mx.empty() && nm[mx.front()]<nm[j])
            mx.pop_front();
        mx.push_front(j);
        while(!mn.empty() && nm[mn.front()]>nm[j])
            mn.pop_front();
        mn.push_front(j);

        rmax[i]=mx.back();
        rmin[i]=mn.back();

        j++;
    }

    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmin[i]]<<" ";
    cout<<"\n";
    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmax[i]]<<" ";
    return 0;
}

發佈留言