進階STL：stack queue deque

# 進階STL： # stack queue deque ### 2021/11/26 電算社第十堂社課 --- ## Stack & Queue ---- ## Stack ---- ![](https://i.imgur.com/ge8G2ws.png =35%x) ![](https://i.imgur.com/34G1zoM.png =35%x) ---- 使用Stack的時候就像是疊盤子每一個丟進stack的資料都是一個盤子越早丟的資料會在越下面並且要娶的時候只能取最上面那一個資料 --> 先進後出隊列(FILO) ---- ## Queue ---- ![](https://i.imgur.com/a6lO7s6.jpg =40%x) ![](https://i.imgur.com/WAsC9Ev.png =35%x) ---- Queue就像一個排隊的人龍每一個你丟進去的資料就是一個排隊的人越早丟的資料會在越前面先排進隊伍的人會最先出來 --> 先進先出隊列(FIFO) --- 標頭檔： ```cpp= #include<stack> // stack ``` ```cpp= #include<queue> // queue ``` ---- 宣告 ```cpp= #include<iostream> #include<stack> #include<queue> using namespace std; int main() { queue<int> q; // 沒有初始化和 size stack<int> s; // 沒有初始化和 size } ``` --- ### 一些功能 stack： `s.push()` `s.top()` `s.pop()` `s.empty()` `s.size()` ---- queue: `q.push()` `q.front()` `q.back()` `q.pop()` `q.empty()` `q.size()` ---- size empty和 vector 的邏輯一樣 stack 的 top 和 pop 分別是對最晚進的元素取值和刪除 queue 的 front 和 pop 分別是對最早進的元素取值和刪除 ---- ```cpp #include<iostream> #include<stack> #include<queue> using namespace std; int main() { queue<int> q; stack<int> s; q.push(1); q.push(2); q.push(3) ; q.push(4); // 前{1, 2, 3, 4}後 s.push(1); s.push(2); s.push(3) ; s.push(4); // 上面{4, 3, 2, 1}下方 cout << q.front() << endl; // 1 cout << s.top() << endl; // 4 q.pop(); s.pop(); cout << q.front() << endl; // 2 cout << s.top() << endl; // 3 cout << q.size() << " " << s.size(); // 3 3 } ``` --- ### 慣用法 ---- 清空stack or queue ```cpp= while(not s.empty()) s.pop(); while(not q.empty()) q.pop(); ``` ---- 遍歷stack or queue ```cpp= while(!s.empty()) { cout << s.top(); s.pop(); } while(!q.empty()) { cout << q.front(); q.pop(); } ``` ---- 特點：不能用`[]`取值(不支援random access) --- ## Deque：兩頭的Queue ## (Double-ended Queue) ---- 兩頭的queue 可以從前面來也可以從後面來 ---- 標頭檔 ```cpp= #include <deque> ``` ---- 宣告 ```cpp= deque<int> dq; ``` ---- 功能 `dq.front()` `dq.back()` `dq.push_front()` `dq.push_back()` `dq.pop_front()` `dq.pop_back()` `dq.empty()` `dq.size()` `dq[]` ---- ```cpp= #include <iostream> #include <deque> using namespace std; int main() { deque<int> dq; dq.push_front(1); dq.push_front(2); // 2 1 dq.push_back(3); dq.push_back(4); // 2 1 3 4 cout << dq.front() << ' ' << dq.back(); // 2 4 dq.pop_front(); // 1 3 4 dq.pop_back(); // 1 3 cout << dq[1]; // 3 } ``` ---- 缺點：時間複雜度常數太大 (會運行得比較慢) --- ### OJ練習 [zerojudge b923 stack](https://zerojudge.tw/ShowProblem?problemid=b923) [zerojudge e447 queue練習](https://zerojudge.tw/ShowProblem?problemid=e447) [zerojudge c123 Rails](https://zerojudge.tw/ShowProblem?problemid=c123) [zerojudge e924 括號配對](https://zerojudge.tw/ShowProblem?problemid=e924)