【考試向】資料結構筆記（堆疊、佇列、環狀佇列、後序表示式）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

最後更新時間：

堆疊（Stack）

特性：後進先出（LIFO：Last In First Out）

資料只能在頂端（Top）做堆入（Push），跟移除（Pop）。

Image Source：Stack Data Structure and Implementation in Python, Java and C/C++

應用：

• Ctrl + Z 復原功能
• 函式呼叫
• 括號匹配
• DFS（Depth First Search：深度優先搜尋）

時間複雜度：

• 堆入（Push）： $O(1)$
• 移除（Pop）： $O(1)$

優點：

• 記憶體管理高效：資料只在頂端操作，記憶體配置連續可預測。在系統層級（如 Call Stack），比堆積（Heap）快很多。
• 存取速度快（$O(1)$）：無論堆疊有多大，Push 跟 Pop 的時間複雜度永遠是 $O(1)$ 。
• 防資料碎片化：資料按順序堆疊，不會像其他結構一樣在記憶體中留下零散的空隙。

缺點：

• Stack Overflow：遞迴過深或存放過多，記憶體用太多易導致程式當掉。
• 靈活性差：不支援隨機存取（Random Access），要拿中間某個資料只能一個一個把東西拿出來才能拿到。

實作方式

使用 C 語言實作。

標頭檔 #include <stdbool.h> 用於 true/false。

• 變數 int top = -1 用於追蹤 stack 目前的位置。
• top == MAX - 1 判斷 stack 滿了沒。
• top == -1 判斷 stack 是否為空。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int stack[MAX];

int top = -1;

bool empty(){
    return top == -1;
}

void push(int data){
    if (top == MAX - 1){
        printf("堆疊已滿:資料 %d 無法堆入堆疊\n", data);
    }
    else{
        top++;
        stack[top] = data;
        printf("資料 %d 堆入堆疊\n", data);
    }
}

int pop(){
    if (empty()){
        printf("堆疊為空:無法 pop\n");
        return -1;
    }
    else{
        int data = stack[top];
        top--;
        return data;
    }
}

void printStack() {
    printf("目前堆疊內容: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    for (int i = 0; i <= top; i++) printf("%d ", stack[i]);
    printf(" <- Top\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    printStack();

    int val = pop();
    printf("取出的值為:%d\n", val);
    printStack();

    push(40);
    push(50);
    push(60);
    push(70);
    printStack();

    while (!empty()) {
        pop();
    }
    pop();

    return 0;
}

佇列（Queue）

特性：先進先出（FIFO：First In First Out）

想像陣列分為兩端開口：前端（Front）跟尾端（Rear）。

可以做到加入（enqueue）、移除（dequeue）元素這兩種操作。

Image Source：What is Queue Data Structure? - GeeksforGeeks

應用：

• 作業系統層面：
  • CPU 工作排程：利用佇列管理待執行的程序（Processes），確保每個任務按順序或優先級獲得處理時間。
  • 
  • IO 緩衝區（Buffering）：當資料產生速度快於處理速度時（如印表機排隊列印、磁碟寫入等等），佇列可暫存資料避免遺失情形發生。
• BFS（Breadth First Search：廣度優先搜尋）

時間複雜度：

• Enqueue：$O(1)$
• Dequeue：$O(1)$（不移動元素，只移動指標）

優點：

• 保證公平性與順序：處理多執行緒任務排程或網路封包時很重要。
• 解耦（Decoupling）：在分散式系統中，佇列（如 RabbitMQ, Kafka）可作為生產者與消費者之間的緩衝，讓雙方不需要同時在線，增加系統穩定性。

缺點：

• 假溢位問題：若用簡單陣列實作，當前端資料 dequeue 後，後面的資料若不往前移，就會浪費前端的記憶體空間。而一旦往前移的話，就會額外耗費 $O(N)$ 時間。
• 搜尋效率低：若要確認某個特定資料是否在佇列中，必須遍歷整個佇列 ($O(n)$)。

實作方式

使用 C 語言實作。

輸出結果顯示一般佇列實作方式的問題，移除資料時，剩餘資料沒有往前移，因此導致後面要加入資料進去就加不進去，這情況差不多就像是下圖那樣：

Image Source：作者繪製。

程式實作講解：

• 雙指標法：變數 int front = -1、int rear = -1 各別追蹤前端、尾端。
  • enqueue 時 rear 增加。
  • dequeue 時 front 增加。
• rear == MAX - 1 判別一個佇列是否已滿。
• front == -1 && rear == -1 判別一個佇列是否為空。
• 在 dequeue 時做 front >= rear 判別，把兩個變數初始化成 -1 ，免得 front 越加越多。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;

bool empty(){
    return front == -1 && rear == -1;
}

void enqueue(int data){
    if (rear == MAX - 1){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        if (front == -1){
            front = 0;
        }
        rear++;
        queue[rear] = data;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        if (front >= rear){
            front = -1;
            rear = -1;
            printf("取出資料 %d [佇列已空]\n", data);
        }
        else{
            front++;
            printf("取出資料 %d\n", data);
        }
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    for (int i = front; i <= rear; i++) {
        printf("%d ", queue[i]);
    }
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printQueue();

    dequeue();
    printQueue();
    
    enqueue(40);
    enqueue(50);
    printQueue();

    enqueue(60);

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
目前佇列: Front -> 10 20 30 <- Rear
取出資料 10
目前佇列: Front -> 20 30 <- Rear
加入資料 40
加入資料 50
目前佇列: Front -> 20 30 40 50 <- Rear
佇列已滿:資料 60 無法加入

環狀佇列（Circular Queue）

環狀佇列是為了解決一般佇列的假溢位問題而誕生的，將陣列的頭尾邏輯上相連，讓 rear 可以繞回 Index 0 繼續存放資料。

環狀佇列在物理上仍然是一個線性陣列，但在邏輯上，用模運算（Modulo Operator, %）讓索引值循環。

假設 front 跟 rear 兩指標為 index，則要做指標移動時，搭配模運算動：$$index = (index + 1) % N$$

當 $index$ 為 $N-1$（最後一格）時，$(N-1+1) % N$ 會變成 $0$。

實作方式 A：空位版

這是第一種實作方式，有一個缺點，就是會有一個空位留在那邊。

程式實作講解：

• 雙指標 int front = 0、int rear = 0，注意這邊要設成 0 而不是 -1。
  • front 代表指向第一個元素
  • rear 代表指向下一個空位
• front == rear 判斷佇列是否為空。
• (rear + 1) % MAX == front 判斷佇列是否滿了。因為這裡，才會把空位留在那不能加入。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = 0;
int rear = 0;

bool empty(){
    return front == rear;
}

void enqueue(int data){
    if ((rear + 1) % MAX == front){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        queue[rear] = data;
        rear = (rear + 1) % MAX;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        front = (front + 1) % MAX;
        printf("取出資料 %d\n", data);
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    int i = front;
    while (i != rear) {
        printf("%d ", queue[i]);
        i = (i + 1) % MAX; // 移動到下一格
    }
    
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    printQueue();

    enqueue(50); 
    
    dequeue();
    dequeue();
    printQueue();

    enqueue(50);
    enqueue(60);
    printQueue();

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
加入資料 40
目前佇列: Front -> 10 20 30 40 <- Rear
佇列已滿:資料 50 無法加入
取出資料 10
取出資料 20
目前佇列: Front -> 30 40 <- Rear
加入資料 50
加入資料 60
目前佇列: Front -> 30 40 50 60 <- Rear

實作方式 B：無空位版

改進方式是在原有的程式碼中，新增 int count = 0;，去判斷目前有多少個元素，剩下邏輯不變。

基本上就是判斷目前佇列大小。

• count == 0; 判斷佇列是否為空。
• count == MAX; 判斷佇列是否滿了。

#include <stdio.h>
#include <stdbool.h>

#define MAX 5

int queue[MAX];
int front = 0;
int rear = 0;
int count = 0;

bool empty(){
    return count == 0;
}

void enqueue(int data){
    if (count == MAX){
        printf("佇列已滿:資料 %d 無法加入\n", data);
    }
    else{
        queue[rear] = data;
        rear = (rear + 1) % MAX;
        count++;
        printf("加入資料 %d\n", data);
    }
}

int dequeue(){
    if (empty()){
        printf("佇列為空:無法取出資料");
        return -1;
    }
    else{
        int data = queue[front];
        front = (front + 1) % MAX;
        count--;
        printf("取出資料 %d\n", data);
        return data;
    }
}

void printQueue() {
    printf("目前佇列: ");
    if (empty()) {
        printf("[空]\n");
        return;
    }
    printf("Front -> ");
    int temp = front;
    for (int i = 0; i < count; i++) {
        printf("%d ", queue[temp]);
        temp = (temp + 1) % MAX; // 移動臨時指標
    }
    
    printf("<- Rear\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    printQueue();

    enqueue(50);
    printQueue();
    
    dequeue();
    dequeue();
    printQueue();

    enqueue(50);
    enqueue(60);
    printQueue();

    return 0;
}

Output：

加入資料 10
加入資料 20
加入資料 30
加入資料 40
目前佇列: Front -> 10 20 30 40 <- Rear
加入資料 50
目前佇列: Front -> 10 20 30 40 50 <- Rear
取出資料 10
取出資料 20
目前佇列: Front -> 30 40 50 <- Rear
加入資料 50
加入資料 60
目前佇列: Front -> 30 40 50 50 60 <- Rear

堆疊應用：後序表示式（Postfix notation）

在談後序表示式前，需要先知道中序表示式。

中序表示式（Infix Notation）

中序表示式是人類最習慣用的寫法，就是將兩個運算元之間夾帶一個運算子，如：$$1 + 1$$

這種形式的寫法就叫做中序表示式。

格式： $Operand \ A \quad Operator \quad Operand \ B$

缺點： 對於電腦來說，這個處理起來比較複雜，因為需要處理「運算子優先順序」（如乘除先於加減）以及「括號」來改變順序。如果用這個寫法來做處理，時間複雜度可能最多會到 $O(N^2)$ ，善用演算法技巧如雙堆疊法，可減至 $O(N)$ 。

後序表示式（Postfix notation）

後序表示式又稱為逆波蘭表示式（Reverse Polish Notation, RPN）。

這種寫法是可以讓電腦看得懂的寫法，而且會比較快，原理是將運算子放在兩個運算元後面，如：$$1 \ 1 \ +$$

原本中序表示式的寫法是 $$1 + 1$$

優點：

1. 不需要括號
2. 電腦好處理：電腦只要從左讀到右，遇到數字就存起來，遇到運算子就抓最近的兩個數字運算，非常適合以堆疊（Stack）來實作。

時間複雜度： $O(N)$ ，但是因為用堆疊實作，一些操作基本上是常數時間，執行速度上來說會比中序還快。

中序轉後序（堆疊法）

用堆疊將中序轉後序，主要依照以下規則：

1. 遇到運算元（數字 or 變數）：直接輸出。
2. 遇到左括號 (：放入堆疊。
3. 遇到右括號 )：將堆疊中的運算子依序 pop 並輸出，直到 pop 左括號 ( 為止（括號不輸出）。
4. 遇到運算子（+, -, *, /）：
   • 檢查堆疊頂端的運算子。
   • 若堆疊頂端運算子優先權 $\ge$ 目前運算子：將堆疊頂端 pop 並輸出，重複此步驟直到堆疊頂端優先權較小或是遇到 (。
   • 將目前的運算子放入堆疊。
5. 讀取完畢：將堆疊中剩餘的所有運算子依序 pop 並輸出。

至於優先順序，大致上就如下表所示：

優先順序（Priority）	運算子（Operator）
5（最高）	*, /, %
4	+, -
3	<, <=, >, >=
2	&&
1（最低）	`

另外在實作「中序轉後序」演算法時，需要兩數值來決定動作，因為左括號 ( 在堆疊外和堆疊內的優先順序是完全不同的。

因此在這邊會有兩個名詞：

• ICP（Incoming Priority）：運算子在堆疊外（剛讀到，準備進去）的優先順序。
• ISP（In-Stack Priority）：運算子在堆疊內（已在內）的優先順序。

運算規則：

• 若 $ICP > ISP \rightarrow$ 堆入堆疊（push）。
• 若 $ICP \le ISP \rightarrow$ pop 並輸出，直到 $ICP > ISP$ 為止，然後再 push。

優先順序表（數字越低，優先順序越低；數字越高，優先順序越高）：

運算子（Operator）	ICP（堆疊外優先順序）	ISP（堆疊內優先順序）
)	1	N/A
*, /, %	2	2
+, -	1	1
(	4	1

右括號 ) 被讀到後需要 pop 找到 ( 才結束，且不進堆疊。

左括號 ( 在進堆疊後，優先順序變最低的原因是為了不擋住後續進來的任何 +, -, *, /，讓括號內的運算子能順利堆疊起來。

中序轉後序（堆疊法）範例

將以下中序表示式轉換成後序表示式：$$A + B * (C - D) / E$$

解法：

先求出後序表示式的結果：$$A B C D - * E / +$$

ok 之後就開始來做模擬表了（記得規則就是上節的那五條）：

讀取字元（next token）	堆疊內容（stack）	輸出（output）	說明
A	empty	A	遇到運算元直接輸出
+	+	A	堆疊為空，直接 push
B	+	A B	遇到運算元直接輸出
*	+ *	A B	* 優先順序大於堆疊頂端 +，push
(	+ * (	A B	左括號 ( 直接 push
C	+ * (	A B C	遇到運算元直接輸出
-	+ * ( -	A B C	堆疊頂端是 (，直接 Push
D	+ * ( -	A B C D	遇到運算元直接輸出
)	+ *	A B C D -	遇到右括號，不斷 pop 直到遇到 (，由於這邊 - 被 pop 掉了，所以直接輸出 -
/	+ /	A B C D - *	1. 比較 * 與 /。 2. * 優先順序 $\ge$ /，pop *。 3. 接著比較 +，+ $\le$ /，因此 / push 進去。
E	+ /	A B C D - * E	遇到運算元直接輸出
none	empty	A B C D - * E / +	字串讀完後，pop 所有剩餘項目（/ 接下來是 +）

最後得到後序表示式就是 $A B C D - * E / +$ 。

中序轉後序（括號法）

繼續以上節的範例為例子： $$A + B * (C - D) / E$$

先找到原本的括號 $(C - D)$ ，就不動他，再看到運算子優先級最高的部分，也就是乘除的地方，由於優先級相同，於是先從左邊開始算： $$B * (C - D)$$

加上括號後，接著再算 $$(B * (C - D)) / E$$

一樣加上括號後，最後做加法 $$A + ((B * (C - D)) / E)$$

最後補齊括號 $$(A + ((B * (C - D)) / E))$$

做好前處理之後，就要先從最內層的括號開始轉換，每一組 (X op Y)，轉成後序就是 X Y op。

第一個是 $$(C - D) \rightarrow C D -$$

接下來 $$(B * (C D -)) \rightarrow BCD - *$$

接下來 $$((B C D - *) / E) \rightarrow BCD - * E /$$

最後 $$(A + (BCD - * E /)) \rightarrow ABCD - * E / +$$

C 程式實作：中序轉後序

基本上在函式 infixToPostfix() 中，主要以五條規則下撰寫：

1. 遇到運算元（數字 or 變數）：直接輸出。
2. 遇到左括號 (：放入堆疊。
3. 遇到右括號 )：將堆疊中的運算子依序 pop 並輸出，直到 pop 左括號 ( 為止（括號不輸出）。
4. 遇到運算子（+, -, *, /）：
   • 檢查堆疊頂端的運算子。
   • 若堆疊頂端運算子優先權 $\ge$ 目前運算子：將堆疊頂端 pop 並輸出，重複此步驟直到堆疊頂端優先權較小或是遇到 (。
   • 將目前的運算子放入堆疊。
5. 讀取完畢：將堆疊中剩餘的所有運算子依序 pop 並輸出。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

bool isEmpty(){
    return top == -1;
}

void push(char i){
    if (top >= MAX - 1){
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = i;
}

char pop(){
    if (isEmpty()){
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

char peek(){
    if (isEmpty()) return -1;
    return stack[top];
}

int getPriority(char op){
  switch (op){
    case '*':
    case '/':
    case '%':
      return 2;
    case '+':
    case '-':
      return 1;
    case '(':
      return 0;
    default:
      return -1;
  }
}

void infixToPostfix(char* infix, char* postfix){
  int i = 0; // infix 的索引
  int j = 0; // postfix 的索引
  char token;
  
  while ((token = infix[i++]) != '\0'){
    
    // 1. 如果是運算元 (字母或數字)，直接輸出
    if (isalnum(token)){
      postfix[j++] = token;
      postfix[j++] = ' '; // 美觀用
    }
    // 2. 如果是左括號，直接 push 進堆疊
    else if (token == '('){
      push(token);
    }
    // 3. 如果是右括號，pop 直到遇到左括號
    else if (token == ')'){
      while (!isEmpty() && peek() != '('){
        postfix[j++] = pop();
        postfix[j++] = ' ';
      }
      if (!isEmpty() && peek() == '('){
        pop(); // 把左括號丟掉，不輸出
      }
    }
    // 4. 如果是運算子
    else if (token == '+' || token == '-' || token == '*' || token == '/' || token == '%'){
      // 當堆疊不為空，且堆疊頂端優先權 >= 目前運算子優先權
      // 就要把堆疊頂端踢出來 (Pop)
      while (!isEmpty() && getPriority(peek()) >= getPriority(token)){
        postfix[j++] = pop();
        postfix[j++] = ' ';
      }
      // 踢完之後，把自己放進去
      push(token);
    }
  }
  // 5. 處理剩餘的運算子
  while (!isEmpty()){
    postfix[j++] = pop();
    postfix[j++] = ' ';
  }
  
  postfix[j] = '\0'; // 記得加上字串結束符號
}

int main(){
  char infix[] = "A+B*(C-D)/E";
  char postfix[MAX];
  
  printf("中序表示式: %s\n", infix);
  
  infixToPostfix(infix, postfix);
  
  printf("後序表示式: %s\n", postfix);
  
  return 0;
}

Output：

中序表示式: A+B*(C-D)/E
後序表示式: A B C D - * E / + 

用堆疊計算後序表示式的結果

基本上只要做兩件事情：

1. 遇到運算元（Operand）：直接堆入堆疊（push）。
2. 遇到運算子（Operator）：從堆疊拿出兩個數字運算，算完把結果放回去。

當遇到運算子（例如 /）時，要從堆疊 Pop 兩次：

1. 第一次 Pop 出來的數字：是「右邊」的運算元（Right Operand）。
2. 第二次 Pop 出來的數字：是「左邊」的運算元（Left Operand）。

公式：$$Value = SecondPop \ (Op) \ FirstPop$$

Op = Operator

假設有個後序表示式是 $1 \ 2 \ 5 \ 3 \ - \ * \ 2 \ / \ +$ （其對應的中序表示式是 $1 + 2 * (5 - 3) / 2$），如何用堆疊模擬後序表示式的計算結果？

讀取字元（next token）	堆疊內容（stack）	說明
1	1	數字 $\rightarrow$ push
2	1, 2	數字 $\rightarrow$ push
5	1, 2, 5	數字 $\rightarrow$ push
3	1, 2, 5, 3	數字 $\rightarrow$ push
-	1, 2, 2	1. pop 出 3（右運算元） 2. Pop 出 5（左運算元） 3. 計算 $5 - 3 = 2$ 4. 將 2 push 回去
*	1, 4	1. pop 出 2 2. pop 出 2 3. 計算 $2 * 2 = 4$ 4. 將 4 push 回去
2	1, 4, 2	數字 $\rightarrow$ push
/	1, 2	1. pop 出 2（除數） 2. pop 出 4（被除數） 3. 計算 $4 / 2 = 2$ 4. 將 2 push 回去
+	3	1. pop 出 2 2. pop 出 1 3. 計算 $1 + 2 = 3$ 4. 將 2 push 回去
none	3	讀取完畢，堆疊內唯一的數字即為答案。

C 程式實作：計算後序表示式

註：以下程式碼僅展示後序表示式的數值計算，並未將前面的中序轉後序程式做結合。另外該版本程式碼支援多位數的計算。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int i){
  if (top >= MAX - 1){
    printf("Stack Overflow\n");
    return;
  }
  stack[++top] = i;
}

int pop(){
  if (top == -1){
    printf("Stack Underflow\n");
    exit(1);
  }
  return stack[top--];
}

int evalPostfix(char* postfix){
  int i = 0;
  
  while (postfix[i] != 0){
    if (postfix[i] == ' '){
      i++;
      continue;
    }
    
    if (isdigit(postfix[i])){
      int num = 0;
      
      while (isdigit(postfix[i])){
        num = num * 10 + (postfix[i] - '0');
        i++;
      }
      push(num);
    }
    else{
      int val2 = pop();
      int val1 = pop();
      
      switch(postfix[i]){
        case '+': push(val1 + val2); break;
        case '-': push(val1 - val2); break;
        case '*': push(val1 * val2); break;
        case '/': 
            push(val1 / val2); 
            break;
        case '%': 
            push(val1 % val2); 
            break;
        default: 
            printf("Unknown operator: %c\n", postfix[i]); 
            exit(1);
      }
      i++;
    }
  }
  return pop();
}

int main() {
    char postfix[] = "1 2 5 3 - * 2 / +";
    
    printf("後序表示式: %s\n", postfix);
    
    int result = evalPostfix(postfix);
    
    printf("計算結果: %d\n", result);
    
    return 0;
}

總整理

堆疊（Stack）

特性：

• 後進先出（LIFO）
• 僅能在頂端（Top）進行操作（Push / Pop）
• Push、Pop 皆為 O(1)

應用：

• Ctrl + Z（復原）
• 函式呼叫（Call Stack）
• 括號匹配
• DFS（深度優先搜尋）

優點：

• 操作速度快、實作簡單
• 記憶體連續、效率高（系統層面尤為重要）

缺點：

• 容易 Stack Overflow（遞迴過深）
• 不支援隨機存取

Stack 是只看最頂端的資料結構，適合處理「巢狀結構」與「反向回復」問題。

佇列（Queue）

特性：

• 先進先出（FIFO）
• 使用 Front / Rear 兩端操作
• Enqueue / Dequeue 皆為 O(1)（指標移動）

應用：

• CPU 排程
• IO Buffer
• BFS（廣度優先搜尋）
• 生產者—消費者模型（如 Kafka、RabbitMQ）

優點：

• 公平、有序，適合排隊處理任務
• 可作為系統模組間的緩衝區

缺點：

• 一般陣列實作會有「假溢位」問題
• 搜尋效率低（$O(n)$）

環狀佇列（Circular Queue）

主要用於解決一般 Queue 的「假溢位」問題。

核心技巧：

• 使用模運算 %，讓索引循環
• 邏輯上首尾相接，實體仍為陣列

兩種實作策略：

1. 空位版：
   • 判斷滿：(rear + 1) % MAX == front
   • 判斷空：front == rear
   • 缺點：浪費一格空間
2. 無空位版：
   • 使用 count 紀錄目前元素數
   • 判斷空：count == 0
   • 判斷滿：count == MAX
   • 空間利用率 100%

環狀佇列只索引循環，不搬資料。

堆疊應用：後序表示式（Postfix / RPN）

為何需要後序表示式？

中序表示式（如 1 + 2）對電腦不友善，需處理優先順序與括號。

後序表示式：

• 不需要括號
• 非常適合用 Stack 處理
• 時間複雜度 $O(N)$

中序轉後序（Infix → Postfix）

堆疊法核心規則（五條）：

1. 運算元 → 直接輸出
2. 左括號 ( → push
3. 右括號 ) → pop 直到遇到 (
4. 運算子 →
   • Stack 頂端優先權 ≥ 自己 → pop
   • 否則 push
5. 讀完後 → pop 剩餘運算子

重要觀念：左括號在 Stack 內的優先權最低。

---

括號法核心規則：

1. 前處理：從優先級最高的運算子開始補括號，已經有括號的就不用補了。
2. 拆括號：從最內層開始拆解， (x op y) 會轉成 x y op 。

計算後序表示式

演算法：

1. 運算元 → push
2. 運算子 → pop 兩次計算，再 push 回去

重要順序：

1. 第一次 pop → 右運算元
2. 第二次 pop → 左運算元

公式：$$Value = SecondPop \ (Op) \ FirstPop$$

最後 Stack 中唯一剩下的數字就是答案。