堆疊，顧名思義就是一堆資料疊成一堆，每次都只能從最上面存取資料，否則整個堆疊就會倒塌，這正是所謂先進後出（first in last out, FILO）原則。

假設我想要疊盤子，將盤子疊在一起，每次拿到的就是最上面的盤子，放盤子也是最上面，那就正好就是 stack 的用武之地。

以上就是 stack 的示意圖：只能從最上面拿和放（此處原本最上面是 $y$，可以拿走；或者可以從最上面放$x$進去）。就讓我們直接來看一道例題：

實作時，我們通常會宣告一個足夠大的陣列用來當作 stack 的儲存空間，並用一個變數當作「目前 stack 最上方的位置」，透過 C++ 方便的 ++ 和 -- 運算子，就可以達成簡潔的實作。讀者可以從下面這段程式碼自行理解。

int Stack[maxn], tot = 0;
void PUSH(int x) {
    Stack[tot++] = x;
}
void POP(){
    if(tot == 0)
        cout << "stack is empty!\n";
    else
        cout << Stack[--tot] << endl;
}

STL 也有內建的 stack 容器適配器，有新增、刪除、查詢最頂部元素的功能。以下是宣告一個 stack 的方法。

stack<int> stk; // 宣告一個儲存 int 型別的 stack

stack 是放在 <stack> 標頭檔內，使用前記得引入。

• push() 可以將資料放入堆疊的頂部；
• pop() 將頂端元素刪除；
• top() 查詢堆疊頂端元素；
• size() 查詢目前還位於堆疊中的資料數；
• empty() 回傳堆疊是否為空。

stk.push(3); // [3]
stk.push(2); // [3, 2]
stk.push(5); // [3, 2, 5]
stk.pop(); // [3, 2]
cout << stk.size() << endl; // 2
cout << stk.empty() << endl; // 0 (表示非空)
cout << stk.top() << endl; // 2

讀者可以發現，基本上 STL 中 stack 能做到的事情 vector 都能做到，而 vector 又支援 operator[] 這種查找操作，所以其實大多數競賽選手都習慣直接使用 vector 而不是 stack。

Stack 的概念較為簡單，但其應用可是非常可觀。在未來我們會介紹不少 Stack 的應用，這裡就先放上兩題簡單的 Stack 應用題，供讀者先行思考看看。

習題

Rails

Source:TIOJ 1012

在一個叫「堆疊市」的城市中有一個著名的火車站。由於地形限制以及經費關係，火車站及唯一的鐵路的樣子如下圖：

現在火車從 A 方向來，預定從 B 方向離開。火車共有 $N$ 節車廂，並且各車廂依次以 $1$ 到 $N$ 來編號。你可以假設各車廂在進站之前可以單獨與其他車廂分離，也可以單獨離開車站到往 B 方向的鐵軌或是車站北方的「維修鐵路」上。維修鐵路是一小段至多只能容納 $M$ 節車廂的鐵軌，可以從車站依照順序將車廂移至維修鐵路，或者將車廂從維修鐵路（如果有的話）駛進車站，但是在把車廂從A開進車站的時候，維修鐵路不能有任何車廂。你可以假設在任何時間火車站都可以容納所有的車廂。但是一旦一節車廂進站後，就不能再回到 A 方向的鐵軌上了，並且一旦離開車站往 B 方向後，也不能再回到車站。

現在你的任務是寫一個程式，判斷火車能否以一特定的排列方式在 B 方向的鐵軌上。

條件限制

• $1\leq N\leq 1000$
• $0\leq M\leq 9$

佇列，顧名思義就是一堆人在排隊，先進去排隊的人先享有辛苦排隊的成果，這是所謂先進先出（first in first out, FIFO）原則。

想像一家熱門的蛋糕店，有很多人在排隊，而每一個人都不會插隊，那要怎麼模擬呢？當最前面的人拿到了夢寐以求的蛋糕的時候，就會從最前面離開隊伍，而當有一個人聞香而來，就會從最後面加入隊伍。這就是 queue 的精神！以下為蛋糕店排隊的模擬圖：

和stack不同的是：一個是拿、放同側，而這個是異側，是FIFO（First In Last Out）資料結構。

queue 的實作方法比 stack 難一點，得在陣列維持兩個變數（也就是頭和尾），插入的時候動尾，而離開的時候動頭。

int Queue[maxn], Front = 0, Back = 0;
void PUSH(int x) {
    Queue[Back++] = x;
}
void POP() {
    if (Front == Back)
        cout << "empty!\n";
    else {
        cout << Queue[Front++] << endl;
    }
}

不過像前面那樣寫的話有一個問題，只要插入的元素數量超過了 maxn，這個陣列就存不下了。為了更有效率的利用前面的空間，我們可以使用循環的實作方式，陣列大小不再和操作數量有關，而是和任一時間在佇列中的元素數量有關。

int Queue[maxn], Front = 0, Back = 0;
void PUSH(int x) {
    Queue[Back] = x;
    if (++Back >= maxn) Back -= maxn;
}
void POP() {
    if (Front == Back)
        cout << "empty!\n";
    else {
        cout << Queue[Front] << endl;
        if (++Front >= maxn) Front -= maxn;
    }
}

假設這個佇列最多只能存 $N$ 個元素，當下一個元素要被放進第 $N+1$ 格時，因為有 pop 操作的存在，所以這個佇列不一定是滿的狀態。通常為了有效節省實作佇列時所需的空間，我們都會用循環的方式來實作 queue，意即假設原本存在第 $1$ 格的元素已經被 pop 掉，我們就可以將原本要儲存在 $N+1$ 格的元素儲存在第 $1$ 格，重複利用能用的空間。這樣的實作方法又被稱為「環狀佇列」，偶爾可以用來省空間。

STL 也為佇列設計了一個容器適配器，它支援從後面插入資料，但是資料是從前面取出。以下是 queue 的宣告方法。

queue<int> que; // 宣告一個儲存 int 型別的 queue

queue 是放在 <queue> 標頭檔內，使用前必須引入。

• push() 可以將資料排入佇列的尾端；
• pop() 將前端元素刪除；
• front() 查詢佇列前端元素；
• size() 查詢目前還位於佇列內的資料數；
• empty() 回傳佇列是否為空。

que.push(3); // [3]
que.push(2); // [3, 2]
que.push(5); // [3, 2, 5]
que.pop(); // [2, 5]
cout << que.front() << endl; // 2

在介紹這個資料結構之前，要先決定這個資料結構的唸法。

這個東西感覺像是 queue 和 stack 的進化版，可以從頭尾拿，也可以從頭尾放東西，所以會支援四個操作：兩邊（front, back）各有放和拿（push, pop）：push_back、push_front、pop_back、pop_front。為什麼要用 stack 和 queue，而不直接用 deque 呢？因為不需要那麼多的功能，還會影響程式的可讀性。

那麼要怎麼實作呢？和 Queue 的概念一樣，需要維護頭尾在哪裡，所以我們能用 Front, Back 紀錄兩端的位置。不過若直接貿然將 Front 初始為 0 的話，一個 push_front 操作就會讓 Front 變成 -1 造成問題，一種解決方法是宣告一個兩倍大的陣列，並把 Front 跟 Back 的初始值定位在中間；另一個作法則是像以下這樣，使用環狀佇列的概念實作：

int deq[maxn], Front = 0, Back = 0;
void PUSH_FRONT(int x) {
    if (--Front < 0) Front += maxn;
    deq[Front] = x;
}
void PUSH_BACK(int x) {
    if (++Back >= maxn) Back -= maxn;
    deq[Back] = x;
}
void POP_FRONT(){
    if (Front == Back)
        cout << "empty!\n";
    else {
        if (++Front >= maxn) Front -= maxn;
        cout << deq[Front] << endl;
    }
}
void POP_BACK(){
    if (Front == Back)
        cout << "empty!\n";
    else {
        if (--Back < 0) Back += maxn;
        cout << deq[Back] << endl;
    }
}

STL 裡面的 deque 也有雙端佇列的功能，可以在首端或尾端存取資料。以下是 deque 的宣告。

deque<int> dq; // 宣告一個儲存 int 型別的 deque

deque 是放在 <deque> 標頭檔內，使用前記得引入。

• push_back() 可以將資料排入雙端佇列的尾端；
• pop_back() 將雙端佇列尾端元素刪除；
• push_front() 可以將資料排入雙端佇列的首端；
• pop_front() 將雙端佇列首端元素刪除；
• front() 查詢雙端佇列首端元素；
• back() 查詢雙端佇列尾端元素；
• size() 查詢目前還位於佇列內的資料數；
• empty() 回傳佇列是否為空；
• operator[] 可以查找元素。

dq.push_back(3); // [3]
dq.push_back(1); // [3, 1]
dq.push_front(2); // [2, 3, 1]
dq.pop_back(); // [2, 3]
dq.pop_front(); // [3]
dq.push_front(1); // [1, 3]
cout << dq.front() << endl; // 1
cout << dq.back() << endl; // 3
cout << dq[1] << endl; // 3

值得注意的是，與 stack 和 queue 不同，deque 還可以使用 operator[] 來隨機存取元素！

儘管 deque 看起來功能方便、又支援陣列操作，但能用一般陣列或 vector 解決的問題就盡量避免用 deque。這是因為 deque 的時間和空間常數都不小。

那 stack 跟 queue 呢？這就有趣了，實際上在 STL 中，這兩個資料結構預設是呼叫 deque 來當作內部容器的！正是因為 deque 涵蓋了這兩個資料結構的功能，所以他們直接擷取 deque 的一小部分功能下來變成一個可讀性比較好的語法。

沒錯！也就是說使用 stack 跟 queue，就等價於使用了擁有巨大常數的 deque！

當然，大多數情況下若不是真的沒必要用到 stack 或著 queue 的功能，正常的使用這兩個 STL 並不是真的那麼容易被「卡常數」，但若真的遇到了，除了乖乖自己實作之外，也可以試試看以下方法：

stack<int, vector<int>> stk;
queue<int, list<int>> que;

上述兩行程式碼是在宣告 stack 和 queue 的時候「更改」他們的內部容器，而被我們用來更換的 vector 和 list 恰好都同時包含了 stack 和 queue 的功能，才能直接做使用。

不過 list 是什麼呢？歡迎瀏覽下一個章節……