STL容器適配器詳解：stack、queue、priority_queue

適配器概念

適配器基於順序容器（vector/list/deque）封裝特定接口，**不提供迭代器**，不支持批量插入刪除。

1. queue（隊列，FIFO）

底層容器

默認`deque`，可選`list`。頭文件``

常用操作

queue q;
q.push(x);      // 入隊
q.pop();        // 出隊（無返回值）
q.front();      // 隊首元素（引用）
q.back();       // 隊尾元素（引用）
q.empty();      // 是否為空
q.size();       // 元素個數

2. stack（棧，LIFO）

底層容器

可用`vector`/`deque`/`list`，默認`deque`。頭文件``

常用操作

stack s;
s.push(x);      // 入棧
s.pop();        // 出棧（無返回值）
s.top();        // 棧頂元素（引用）
s.empty();
s.size();

3. priority_queue（優先隊列，堆）

內部實現

最大堆（默認`<`比較），`push/pop` O(log n)，`top` O(1)。頭文件``

模板參數

priority_queue
// T: 元素類型
// Container: 底層容器（默認vector）
// Compare: 比較函數（默認less，即最大堆）

常見用法

// 最大堆（默認）
priority_queue maxHeap;

// 最小堆
priority_queue, greater> minHeap;

// 自定義結構體比較
struct Node { int val, id; };
struct Cmp {
    bool operator()(const Node& a, const Node& b) {
        return a.val < b.val; // 最大堆：val大者優先
    }
};
priority_queue, Cmp> pq;

比較函數深度解析

情況1：結構體內重載operator<

struct Task {
    int pri, id;
    bool operator<(const Task& other) const {
        return pri < other.pri; // pri大者優先（最大堆）
    }
};
priority_queue pq; // 直接使用

情況2：外部比較器引用外部數據

int dist[100];
struct CmpDist {
    bool operator()(int a, int b) {
        return dist[a] > dist[b]; // dist小者優先（最小堆）
    }
};
priority_queue, CmpDist> pq;

總結對比

注意事項

• 無迭代器，不能遍歷
• priority_queue默認最大堆，最小堆需`greater`或自定義比較
• 自定義比較器邏輯**相反於直覺**：`return a < b` 表示 b 優先級更高（最大堆）