E. 佇列與堆疊
考卷用 C（A 節），沒有 queue、stack 這種現成容器，取而代之的是一個陣列配一兩個索引變數。看懂那幾個索引指著哪一格，題目就解掉一半。
先分清楚兩者的差別：
- 佇列（queue）：先進先出（FIFO），像排隊買票，先排的先走。
- 堆疊（stack）：後進先出（LIFO），像一疊盤子，最後放上去的最先被拿走。
¶佇列：head 與 tail
head 指著下一個要出去的位置，tail 指著下一個要放進去的空位：
q[tail++] = x; // 放進來
x = q[head++]; // 拿出去
tail++ 是後置遞增：先拿舊的值當索引，再把索引加一——一行同時做完「放在現在這格」與「把位置往後推」。兩個索引都只往後跑，head == tail 就代表空了。
#include <iostream>
using namespace std;
int q[100]; // 佇列本體
int head = 0; // 下一個要出去的位置
int tail = 0; // 下一個要放進去的空位
int main() {
q[tail++] = 3; // 3 排進來
q[tail++] = 1; // 1 排進來
cout << q[head++] << '\n'; // 最前面的先出去
q[tail++] = 4; // 4 排進來
while (head < tail) { // 還有人就繼續叫號
cout << q[head++] << '\n';
}
return 0;
}
執行結果：
3
1
4| 執行的敘述 | q[0] |
q[1] |
q[2] |
head |
tail |
輸出 |
|---|---|---|---|---|---|---|
| （開始） | 0 | 0 | ||||
q[tail++] = 3; |
3 | 0 | 1 | |||
q[tail++] = 1; |
3 | 1 | 0 | 2 | ||
cout << q[head++]; |
3 | 1 | 1 | 2 | 3 |
|
q[tail++] = 4; |
3 | 1 | 4 | 1 | 3 | |
| 迴圈第一圈 | 3 | 1 | 4 | 2 | 3 | 1 |
| 迴圈第二圈 | 3 | 1 | 4 | 3 | 3 | 4 |
出去的元素其實還留在陣列裡，只是 head 走過去了——「已經出去」的意思就是 head 超過了它。
¶堆疊：只要一個 top
top 指著下一個要放進去的空位，同時也就是目前的元素個數：
st[top++] = x; // 疊上去
x = st[--top]; // 拿下來
拿的時候是前置遞減：先退一格，再把那一格的值取走。進與出動到的是同一個索引，所以拿到的一定是最後放進去的那個。top == 0 就是空的。
#include <iostream>
using namespace std;
int st[100]; // 堆疊本體
int top = 0; // 下一個要放進去的空位，也就是目前的元素個數
int main() {
st[top++] = 3; // 3 疊上去
st[top++] = 1; // 1 疊上去
cout << st[--top] << '\n'; // 最上面的先拿走
st[top++] = 4; // 4 疊上去
while (top > 0) { // 還有東西就一直拿
cout << st[--top] << '\n';
}
return 0;
}
執行結果：
1
4
3| 執行的敘述 | st[0] |
st[1] |
top |
輸出 |
|---|---|---|---|---|
| （開始） | 0 | |||
st[top++] = 3; |
3 | 1 | ||
st[top++] = 1; |
3 | 1 | 2 | |
cout << st[--top]; |
3 | 1 | 1 | 1 |
st[top++] = 4; |
3 | 4 | 2 | |
| 迴圈第一圈 | 3 | 4 | 1 | 4 |
| 迴圈第二圈 | 3 | 4 | 0 | 3 |
注意倒數第三列：4 直接蓋掉了 st[1] 原本的 1——那一格已經被拿走，蓋掉無妨。
¶兩個堆疊做出一個佇列
考古題出現過這個組合，觀念只有一句：每倒一次，順序就翻面一次。
資料先一個一個推進堆疊 A。要取用時，等 B 空了，再把 A 裡的東西全部拿出來、依序推進堆疊 B：從 A 拿出來的順序已經跟進去時相反（翻了一次面），推進 B 之後再拿出來，又相反一次（第二次翻面）。翻兩次就翻回原樣，所以從 B 拿到的是最早進 A 的那一個，正是佇列的行為。
「等 B 空了」不能省——B 裡還有東西時就把 A 倒過去，後到的會疊在舊的上面先被拿走，順序就亂了。
追蹤這種題目時不必想「為什麼要這樣繞」，只要盯著兩個 top，記得每次整批搬家都會把順序反過來。