# Ch18 Stack與Queue > 搭配 [virtual judge解題系統](https://vjudge.net/contest/273248) ## > 上一章：[二分搜尋法](https://hackmd.io/s/ByCZ5Yoa7) > 下一章：[BFS 廣度優先搜尋](https://hackmd.io/s/BkxmExS8J4) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z) ## <font color='darkblue'>什麼是Stack</font> 想像有一疊箱子 你可以一直增加新的箱子到這疊的頂端 也可以從這疊的頂端拿走箱子 但是你不能從中間塞箱子進去，因為這樣會弄垮 也不能從中間抽箱子出來，因為這樣也會弄垮 另外你也看不到中間是哪些箱子，只知道最上方是什麼 這座箱子塔就稱為「Stack」 ## <font color='darkblue'>程式語言的Stack</font> stack是一種「資料結構」 專門處理這種「愈晚放進來的要愈先拿走」的問題 ### 宣告一個stack ```cpp= #include<stack> stack<int> st; ``` 想要使用stack時 記得先include<stack>這個函式庫 尖括號內的`<int>`代表這個stack裡面放的都是整數 如果想要在stack裡面放其他型態的資料的話 也可以宣告成這樣 ```cpp= stack<float> st; stack<string> st; stack<char> st; ``` ### 放東西進去 現在你有了一個名為「st」的空塔了 你可以放東西進去 ```cpp= st.push(3); st.push(5); st.push(-10); ``` 這樣一來這個塔就有了三個數字 由底到頂分別是3、5、-10 -10會在最上面 ### 看看最上面是甚麼 這個塔只有最上面的數字是你看得到的 其他你都看不到了 ```cpp= int a = st.top(); ``` 這樣一來a就會是-10 ### 移除最頂端的一個 塔當然不是只有一直蓋而已 還可以把頂端丟掉 通常會在你把最頂端的物件拿來用完之後 就可以把它丟掉 ```cpp= st.pop(); ``` pop這個字用得真不錯 有一種把他擠掉的感覺 ### 檢查塔是不是空的 ```cpp= if(st.empty()) cout << "it is empty" << endl; else cout << "it contains something" << endl; ``` 記起來了嗎 會常用到的總共有四個功能 push、top、pop、empty 忘記了可以再回來看 那麼接下來就來做題目吧 ## <font color='darkblue'>Stack的應用</font> <font color='darkorange'>【例題】</font> > 天上降下各種顏色的磚塊 > 每種顏色會用一個數字來表示 > 這些磚塊降到地面時會疊成一疊 > 如果相同的顏色正好相鄰，他們就會一起消失 > 請問玩完後，這座塔裡沒消掉的磚塊數字總和是多少? sample input: 7 3 1 2 2 4 4 1 sample output: 3 每次拿到一個新磚塊時 先檢查它和塔頂的磚塊是否相同 如果塔原本就是空的，或是和塔頂不同：把這個新磚塊疊上去 如果和塔頂相同：把塔頂除掉 ```cpp= for(int i=0;i<n;i++){ cin >> new_tile; if(st.empty()||st.top()!=new_tile) st.push(new_tile); else st.pop(); } ``` 最後再來看看塔中所有的數字和是多少 由於我們只看得到塔頂的數字 因此我們要不斷地看塔頂、丟掉塔頂 直到塔被清空為止 ```cpp=9 ans=0; while(!st.empty()){ ans+=st.top(); st.pop(); } cout<<ans<<endl; ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [A - Parentheses Balance](https://vjudge.net/contest/273248#problem/A) > > 第一行有一個數字n，代表接下來有n個字串 > 每一個字串都有一個獨立的答案 > > 每個字串都是一堆括弧 > 其中如果有()或[]就可以互相配起來 > 也可以用括弧包括弧 > 像是[ ( [ ] [ ] ( ) ) ] > 但也是有可能配不起來的 > 像是[ [ ) ) > 或是] ] [ [ > > 對於每一個字串 > 如果它能完整配完左右括弧，就輸出Yes > 否則輸出No ## <font color='darkblue'>什麼是Queue</font> 想像有一條隊伍 你可以一直增加新的人到這隊伍的尾端 也可以從這隊伍的前端拿走一個人 但是你不能從中間塞人進去，插隊太糟糕 也不能從中間抽人出來，他排得好好的你把他踢掉幹嘛!? 另外你也看不到中間是哪些人，只知道最前面是誰 這個隊伍，就稱為「Queue」 ## <font color='darkblue'>程式語言的Queue</font> queue是一種「資料結構」 專門處理這種「愈早放進來的要愈先拿走」的問題 ### 宣告一個queue ```cpp= #include<queue> queue<int> q; ``` 想要使用queue時 記得先include<queue>這個函示庫 尖括號內的`<int>`代表這個queue裡面放的都是整數 如果想要在queue裡面放其他型態的資料的話 也可以宣告成這樣 ```cpp= queue<float> q; queue<string> q; queue<char> q; ``` ### 放東西進去 現在你有了一個名為「q」的空隊伍了 你可以放東西進去 ```cpp= q.push(3); q.puah(5); q.push(-10); ``` 這樣一來這個隊伍就有了三個數字 由頭到尾分別是3、5、-10 3會在最前面 ### 看看最前面是甚麼 這個塔只有最前面的數字是你看得到的 其他你都看不到了 ```cpp= int a = q.front(); ``` 這樣一來a就會是3 ### 移除最前面的一個 隊伍當然不是只有一直變長而已 還可以把最前面丟掉 通常會在你把最前面的物件拿來用完之後 就可以把它丟掉 ```cpp= q.pop(); ``` pop這個字用得真不錯 有一種把他擠掉的感覺 ### 檢查隊伍是不是空的 ```cpp= if(q.empty()) cout << "it is empty" << endl; else cout << "it contains something" << endl; ``` 記起來了嗎 會常用到的總共有四個功能 push、front、pop、empty 忘記了可以再回來看 那麼接下來就來做題目吧 ## <font color='darkblue'>Queue的應用</font> <font color='darkorange'>【例題】</font> > 你有一疊撲克牌 > 原本依照1在最上面、接下來是2...這樣的順序排好 > 每次你都會念出最上面一張的數字，並把那張丟掉 > 然後再把第二章塞到牌的最下面 > 一直到整疊牌都被你丟完為止 > 請問你念出的這些數字依序是哪些? 首先先將這些牌依序塞進queue裡 ```cpp= for(int i=1;i<=n;i++){ q.push(i); } ``` 接下來，利用迴圈將這些牌丟光光 ```cpp=4 while(!q.empty()){ //念出第一張牌並丟掉 cout<<q.top()<<" "; q.pop(); //把第二張放到最後面(如果有的話) if(!q.empty()){ int last=q.top(); q.pop(); q.push(last); } } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [B - Throwing cards away I ](https://vjudge.net/contest/273248#problem/B) ## <font color='darkblue'>Queue的變形：Priority Queue</font> 想像一個隊伍中 每個人手上都有號碼牌 每次有新的人要加入隊伍時 都會檢查他的號碼 如果他的號碼比隊伍中的任何人都大 他就會無條件跑到隊伍的第一個 另外 當隊伍的第一個離開時 剩下的人裡面號碼最大的就要來成為新的排頭 這樣的「優先隊伍」 就稱作「priority queue」 ## <font color='darkblue'>程式語言的Priority Queue</font> priority_queue是一種「資料結構」 專門處理這種「號碼愈大的要愈先拿走」的問題 ### 宣告一個priority_queue ```cpp= #include<queue> priority_queue<int> pq; ``` 想要使用queue時 記得先include<queue>這個函示庫 尖括號內的`<int>`代表這個queue裡面放的都是整數 如果想要在queue裡面放其他型態的資料的話 也可以宣告成這樣 ```cpp= priority_queue<float> pq; priority_queue<string> pq; priority_queue<char> pq; ``` ### 放東西進去 現在你有了一個名為「pq」的優先隊伍了 你可以放東西進去 ```cpp= pq.push(3); pq.push(5); pq.push(-10); ``` 這樣一來這個隊伍就有了三個數字 5會在最前面 ### 看看最前面是甚麼 這個塔只有最前面的數字是你看得到的 其他你都看不到了 ```cpp= int a = pq.top(); ``` 這樣一來a就會是5 ### 移除最前面的一個 隊伍當然不是只有一直變長而已 還可以把最前面丟掉 通常會在你把最前面的物件拿來用完之後 就可以把它丟掉 ```cpp= pq.pop(); ``` pop這個字用得真不錯 有一種把他擠掉的感覺 ### 檢查隊伍是不是空的 ```cpp= if(pq.empty()) cout << "it is empty" << endl; else cout << "it contains something" << endl; ``` 記起來了嗎 會用到的總共有四個功能 push、top、pop、empty 忘記了可以再回來看 那麼接下來就來做題目吧 <font color='darkorange'>【例題】</font> > 有好多隻史萊姆 > 每隻的體積都不太一樣 > 每次都要抓最小的兩隻來合併 > 合併的時候要耗費的魔力就是這兩隻的體積之和 > 請問把這些史萊姆合成一隻大史萊姆總共最少需要多少魔力? 這跟Green Judge的某題一模一樣呢 首先先把這些史萊姆都放進priority_queue裡 ```cpp= for(int i=0;i<n;i++){ cin>>slime; pq.push(slime); } ``` 這時體積最大的史萊姆會跑到priority_queue的頂端 但是你其實想要讓小的在頂端 所以要稍微修改一下priority_queue宣告 ```cpp= priority_queue<int, vector<int>, greater<int> > pq; ``` 這樣一來愈小的史萊姆會在愈上面 所以你不需要特意去找最小的 只要拿priority_queue的頂端就好了 ```cpp= 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); } } ``` <font color="darkgreen"> 【學生練習題】</font> > - [ ] [C - Add All ](https://vjudge.net/contest/273248#problem/C) <font color="darkgreen"> 【其他stack與queue的進階題】</font> > - [ ] [D - Rails ](https://vjudge.net/contest/273248#problem/D) > - [ ] [E - Printer Queue ](https://vjudge.net/contest/273248#problem/E) ## > 上一章：[二分搜尋法](https://hackmd.io/s/ByCZ5Yoa7) > 下一章：[BFS 廣度優先搜尋](https://hackmd.io/s/BkxmExS8J4) > 回目錄：[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)