📚 堆疊與佇列學習指南

什麼是堆疊（Stack）？

堆疊是一種後進先出（LIFO）的資料結構，類似於生活中的一疊盤子，只能從頂部加入或取出元素。

基本操作

• push()：將元素推入堆疊頂部
• pop()：從堆疊頂部彈出元素
• peek() / top()：取得頂部元素（不移除）
• isEmpty()：檢查堆疊是否為空
• size()：取得堆疊大小

什麼是佇列（Queue）？

佇列是一種先進先出（FIFO）的資料結構，類似於排隊買票，先到的人先服務。

基本操作

• enqueue() / push()：將元素加入佇列尾部
• dequeue() / pop()：從佇列頭部取出元素
• front() / peek()：取得頭部元素（不移除）
• rear()：取得尾部元素
• isEmpty()：檢查佇列是否為空
• size()：取得佇列大小

時間複雜度

程式碼範例

C++ 堆疊實作

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> s;
    
    // push - 推入元素
    s.push(10);
    s.push(20);
    s.push(30);
    
    cout << "堆疊大小: " << s.size() << endl;  // 3
    
    // top - 查看頂部元素
    cout << "頂部元素: " << s.top() << endl;  // 30
    
    // pop - 彈出元素
    s.pop();
    cout << "彈出後頂部: " << s.top() << endl;  // 20
    
    // 判斷是否為空
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;  // 20 10
    
    return 0;
}

C++ 佇列實作

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    
    // enqueue - 加入元素
    q.push(10);
    q.push(20);
    q.push(30);
    
    cout << "佇列大小: " << q.size() << endl;  // 3
    
    // front - 查看頭部元素
    cout << "頭部元素: " << q.front() << endl;  // 10
    
    // back - 查看尾部元素
    cout << "尾部元素: " << q.back() << endl;  // 30
    
    // dequeue - 取出元素
    q.pop();
    cout << "取出後頭部: " << q.front() << endl;  // 20
    
    return 0;
}

Java 優先權佇列

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 預設是最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        minHeap.add(50);
        minHeap.add(10);
        minHeap.add(30);
        minHeap.add(20);
        
        System.out.println("peek: " + minHeap.peek());  // 10
        
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");  // 10 20 30 50
        }
        
        // 最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(50);
        maxHeap.add(10);
        maxHeap.add(30);
        
        System.out.println("\\n最大堆 peek: " + maxHeap.peek());  // 50
    }
}

常見應用場景

堆疊應用

• 函數呼叫堆疊（Call Stack）
• 括號匹配
• 運算式求值（中序轉後序）
• 網頁瀏覽器的「上一頁」
• 深度優先搜尋（DFS）

佇列應用

• 廣度優先搜尋（BFS）
• 任務排程
• 緩衝區管理
• 印表機工作佇列
• 訊息傳遞