Stack

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

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

越早丟的資料會在越下面

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

–> 先進後出隊列(FILO)

Queue

Queue就像一個排隊的人龍

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

越早丟的資料會在越前面

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

–> 先進先出隊列(FIFO)

宣告

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int main()
{
    queue<int> q; // 沒有初始化 和 size 
    stack<int> s; // 沒有初始化 和 size 
}

queue:

q.push()
q.front()
q.back()
q.pop()
q.empty()
q.size()

size empty和 vector 的邏輯一樣

stack 的 top 和 pop 分別是對最晚進的元素取值和刪除

queue 的 front 和 pop 分別是對最早進的元素取值和刪除

#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)

兩頭的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
    
}

缺點：

時間複雜度常數太大 (會運行得比較慢)