Ch18 Stack與Queue

# 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) ## 什麼是Stack 想像有一疊箱子你可以一直增加新的箱子到這疊的頂端也可以從這疊的頂端拿走箱子但是你不能從中間塞箱子進去，因為這樣會弄垮也不能從中間抽箱子出來，因為這樣也會弄垮另外你也看不到中間是哪些箱子，只知道最上方是什麼這座箱子塔就稱為「Stack」 ## 程式語言的Stack 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 忘記了可以再回來看那麼接下來就來做題目吧 ## Stack的應用 【例題】 > 天上降下各種顏色的磚塊 > 每種顏色會用一個數字來表示 > 這些磚塊降到地面時會疊成一疊 > 如果相同的顏色正好相鄰，他們就會一起消失 > 請問玩完後，這座塔裡沒消掉的磚塊數字總和是多少? 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; ``` 【學生練習題】 > - [ ] [A - Parentheses Balance](https://vjudge.net/contest/273248#problem/A) > > 第一行有一個數字n，代表接下來有n個字串 > 每一個字串都有一個獨立的答案 > > 每個字串都是一堆括弧 > 其中如果有()或[]就可以互相配起來 > 也可以用括弧包括弧 > 像是[ ( [ ] [ ] ( ) ) ] > 但也是有可能配不起來的 > 像是[ [ ) ) > 或是] ] [ [ > > 對於每一個字串 > 如果它能完整配完左右括弧，就輸出Yes > 否則輸出No ## 什麼是Queue 想像有一條隊伍你可以一直增加新的人到這隊伍的尾端也可以從這隊伍的前端拿走一個人但是你不能從中間塞人進去，插隊太糟糕也不能從中間抽人出來，他排得好好的你把他踢掉幹嘛!? 另外你也看不到中間是哪些人，只知道最前面是誰這個隊伍，就稱為「Queue」 ## 程式語言的Queue 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 忘記了可以再回來看那麼接下來就來做題目吧 ## Queue的應用 【例題】 > 你有一疊撲克牌 > 原本依照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); } } ``` 【學生練習題】 > - [ ] [B - Throwing cards away I ](https://vjudge.net/contest/273248#problem/B) ## Queue的變形：Priority Queue 想像一個隊伍中每個人手上都有號碼牌每次有新的人要加入隊伍時都會檢查他的號碼如果他的號碼比隊伍中的任何人都大他就會無條件跑到隊伍的第一個另外當隊伍的第一個離開時剩下的人裡面號碼最大的就要來成為新的排頭這樣的「優先隊伍」就稱作「priority queue」 ## 程式語言的Priority Queue 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 忘記了可以再回來看那麼接下來就來做題目吧 【例題】 > 有好多隻史萊姆 > 每隻的體積都不太一樣 > 每次都要抓最小的兩隻來合併 > 合併的時候要耗費的魔力就是這兩隻的體積之和 > 請問把這些史萊姆合成一隻大史萊姆總共最少需要多少魔力? 這跟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); } } ``` 【學生練習題】 > - [ ] [C - Add All ](https://vjudge.net/contest/273248#problem/C) 【其他stack與queue的進階題】 > - [ ] [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)