owned this note changed 4 years ago
Linked with GitHub

進階STL:

stack queue deque

2021/11/26 電算社第十堂社課


Stack & Queue


Stack




使用Stack的時候就像是疊盤子

每一個丟進stack的資料都是一個盤子

越早丟的資料會在越下面

並且要娶的時候只能取最上面那一個資料

> 先進後出隊列(FILO)


Queue




Queue就像一個排隊的人龍

每一個你丟進去的資料就是一個排隊的人

越早丟的資料會在越前面

先排進隊伍的人會最先出來

> 先進先出隊列(FIFO)


標頭檔:

#include<stack> // stack
#include<queue> // queue

宣告

#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 的 toppop 分別是對最進的元素取值刪除

queue 的 frontpop 分別是對最進的元素取值刪除


#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

while(not s.empty()) s.pop(); while(not q.empty()) q.pop();

遍歷stack or queue

while(!s.empty()) { cout << s.top(); s.pop(); } while(!q.empty()) { cout << q.front(); q.pop(); }

特點:

不能用[]取值(不支援random access)


Deque:兩頭的Queue

(Double-ended Queue)


兩頭的queue
可以從前面來也可以從後面來


標頭檔

#include <deque>

宣告

deque<int> dq;

功能
dq.front()
dq.back()
dq.push_front()
dq.push_back()
dq.pop_front()
dq.pop_back()
dq.empty()
dq.size()
dq[]


#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
zerojudge e447 queue練習
zerojudge c123 Rails
zerojudge e924 括號配對

Select a repo