Try   HackMD

Ch18 Stack與Queue

搭配 virtual judge解題系統

上一章：二分搜尋法
下一章：BFS 廣度優先搜尋
回目錄：國立科學園區實驗中學C++程式語言自學講義

什麼是Stack

想像有一疊箱子
你可以一直增加新的箱子到這疊的頂端
也可以從這疊的頂端拿走箱子

但是你不能從中間塞箱子進去，因為這樣會弄垮
也不能從中間抽箱子出來，因為這樣也會弄垮
另外你也看不到中間是哪些箱子，只知道最上方是什麼

這座箱子塔就稱為「Stack」

程式語言的Stack

stack是一種「資料結構」
專門處理這種「愈晚放進來的要愈先拿走」的問題

宣告一個stack




#include<stack>

stack<int> st;

想要使用stack時
記得先include<stack>這個函式庫

尖括號內的<int>代表這個stack裡面放的都是整數
如果想要在stack裡面放其他型態的資料的話
也可以宣告成這樣




stack<float> st;
stack<string> st;
stack<char> st;

放東西進去

現在你有了一個名為「st」的空塔了
你可以放東西進去




st.push(3);
st.push(5);
st.push(-10);

這樣一來這個塔就有了三個數字
由底到頂分別是3、5、-10
-10會在最上面

看看最上面是甚麼

這個塔只有最上面的數字是你看得到的
其他你都看不到了

int a = st.top();

這樣一來a就會是-10

移除最頂端的一個

塔當然不是只有一直蓋而已
還可以把頂端丟掉

通常會在你把最頂端的物件拿來用完之後
就可以把它丟掉

st.pop();

pop這個字用得真不錯
有一種把他擠掉的感覺

檢查塔是不是空的



if(st.empty()) cout << "it is empty" << endl;
else cout << "it contains something" << endl;

記起來了嗎
會常用到的總共有四個功能
push、top、pop、empty
忘記了可以再回來看

那麼接下來就來做題目吧

Stack的應用

【例題】

天上降下各種顏色的磚塊
每種顏色會用一個數字來表示
這些磚塊降到地面時會疊成一疊
如果相同的顏色正好相鄰，他們就會一起消失
請問玩完後，這座塔裡沒消掉的磚塊數字總和是多少?

sample input:
7
3 1 2 2 4 4 1

sample output:
3

每次拿到一個新磚塊時
先檢查它和塔頂的磚塊是否相同
如果塔原本就是空的，或是和塔頂不同：把這個新磚塊疊上去
如果和塔頂相同：把塔頂除掉








for(int i=0;i<n;i++){
    cin >> new_tile;
    if(st.empty()||st.top()!=new_tile)
        st.push(new_tile);
    else
        st.pop();
}

最後再來看看塔中所有的數字和是多少
由於我們只看得到塔頂的數字
因此我們要不斷地看塔頂、丟掉塔頂
直到塔被清空為止







ans=0;
while(!st.empty()){
    ans+=st.top();
    st.pop();
}
cout<<ans<<endl;

【學生練習題】

第一行有一個數字n，代表接下來有n個字串
每一個字串都有一個獨立的答案

每個字串都是一堆括弧
其中如果有()或[]就可以互相配起來
也可以用括弧包括弧
像是[ ( [ ] [ ] ( ) ) ]
但也是有可能配不起來的
像是[ [ ) )
或是] ] [ [

對於每一個字串
如果它能完整配完左右括弧，就輸出Yes
否則輸出No

什麼是Queue

想像有一條隊伍
你可以一直增加新的人到這隊伍的尾端
也可以從這隊伍的前端拿走一個人

但是你不能從中間塞人進去，插隊太糟糕
也不能從中間抽人出來，他排得好好的你把他踢掉幹嘛!?
另外你也看不到中間是哪些人，只知道最前面是誰

這個隊伍，就稱為「Queue」

程式語言的Queue

queue是一種「資料結構」
專門處理這種「愈早放進來的要愈先拿走」的問題

宣告一個queue




#include<queue>

queue<int> q;

想要使用queue時
記得先include<queue>這個函示庫

尖括號內的<int>代表這個queue裡面放的都是整數
如果想要在queue裡面放其他型態的資料的話
也可以宣告成這樣




queue<float> q;
queue<string> q;
queue<char> q;

放東西進去

現在你有了一個名為「q」的空隊伍了
你可以放東西進去




q.push(3);
q.puah(5);
q.push(-10);

這樣一來這個隊伍就有了三個數字
由頭到尾分別是3、5、-10
3會在最前面

看看最前面是甚麼

這個塔只有最前面的數字是你看得到的
其他你都看不到了

int a = q.front();

這樣一來a就會是3

移除最前面的一個

隊伍當然不是只有一直變長而已
還可以把最前面丟掉

通常會在你把最前面的物件拿來用完之後
就可以把它丟掉

q.pop();

pop這個字用得真不錯
有一種把他擠掉的感覺

檢查隊伍是不是空的



if(q.empty()) cout << "it is empty" << endl;
else cout << "it contains something" << endl;

記起來了嗎
會常用到的總共有四個功能
push、front、pop、empty
忘記了可以再回來看

那麼接下來就來做題目吧

Queue的應用

【例題】

你有一疊撲克牌
原本依照1在最上面、接下來是2…這樣的順序排好
每次你都會念出最上面一張的數字，並把那張丟掉
然後再把第二章塞到牌的最下面
一直到整疊牌都被你丟完為止
請問你念出的這些數字依序是哪些?

首先先將這些牌依序塞進queue裡




for(int i=1;i<=n;i++){
    q.push(i);
}

接下來，利用迴圈將這些牌丟光光












while(!q.empty()){
    //念出第一張牌並丟掉
    cout<<q.top()<<" ";
    q.pop();
    //把第二張放到最後面(如果有的話)
    if(!q.empty()){
        int last=q.top();
        q.pop();
        q.push(last);
    }
}

【學生練習題】

Queue的變形：Priority Queue

想像一個隊伍中
每個人手上都有號碼牌
每次有新的人要加入隊伍時
都會檢查他的號碼
如果他的號碼比隊伍中的任何人都大
他就會無條件跑到隊伍的第一個

另外
當隊伍的第一個離開時
剩下的人裡面號碼最大的就要來成為新的排頭

這樣的「優先隊伍」
就稱作「priority queue」

程式語言的Priority Queue

priority_queue是一種「資料結構」
專門處理這種「號碼愈大的要愈先拿走」的問題

宣告一個priority_queue




#include<queue>

priority_queue<int> pq;

想要使用queue時
記得先include<queue>這個函示庫

尖括號內的<int>代表這個queue裡面放的都是整數
如果想要在queue裡面放其他型態的資料的話
也可以宣告成這樣




priority_queue<float> pq;
priority_queue<string> pq;
priority_queue<char> pq;

放東西進去

現在你有了一個名為「pq」的優先隊伍了
你可以放東西進去




pq.push(3);
pq.push(5);
pq.push(-10);

這樣一來這個隊伍就有了三個數字
5會在最前面

看看最前面是甚麼

這個塔只有最前面的數字是你看得到的
其他你都看不到了

int a = pq.top();

這樣一來a就會是5

移除最前面的一個

隊伍當然不是只有一直變長而已
還可以把最前面丟掉

通常會在你把最前面的物件拿來用完之後
就可以把它丟掉

pq.pop();

pop這個字用得真不錯
有一種把他擠掉的感覺

檢查隊伍是不是空的



if(pq.empty()) cout << "it is empty" << endl;
else cout << "it contains something" << endl;

記起來了嗎
會用到的總共有四個功能
push、top、pop、empty
忘記了可以再回來看

那麼接下來就來做題目吧

【例題】

有好多隻史萊姆
每隻的體積都不太一樣
每次都要抓最小的兩隻來合併
合併的時候要耗費的魔力就是這兩隻的體積之和
請問把這些史萊姆合成一隻大史萊姆總共最少需要多少魔力?

這跟Green Judge的某題一模一樣呢

首先先把這些史萊姆都放進priority_queue裡





for(int i=0;i<n;i++){
    cin>>slime;
    pq.push(slime);
}

這時體積最大的史萊姆會跑到priority_queue的頂端
但是你其實想要讓小的在頂端
所以要稍微修改一下priority_queue宣告

priority_queue<int, vector<int>, greater<int> > pq;

這樣一來愈小的史萊姆會在愈上面
所以你不需要特意去找最小的
只要拿priority_queue的頂端就好了















all_magic=0;
while(!pq.empty())
{
    int a=pq.top();
    pq.pop();
    if(!pq.empty()){
        int b=pq.top();
        pq.pop();
        int new_slime=a+b;
        all_magic+=new_slime;
        pq.push(new_slime);
    }
}

【學生練習題】

【其他stack與queue的進階題】

上一章：二分搜尋法
下一章：BFS 廣度優先搜尋
回目錄：國立科學園區實驗中學C++程式語言自學講義

Last changed by 
 
Chu-Ling Ko
5
2
5429
Published on HackMD