C++ Primer STL 剖析：容器適配器 stack/queue/priority_queue 源碼與實戰

容器適配器本質

stack、queue、priority_queue 不提供迭代器，封裝底層容器（deque/vector/list）提供特定語義：

• stack：LIFO，底層需 push_back/pop_back/back → vector/deque/list 皆可。
• queue：FIFO，底層需 push_back/pop_front/front/back → deque/list（vector 無 pop_front）。
• priority_queue：最大堆（默認），底層需隨機訪問迭代器 → vector/deque（list 不支持）。

stack 源碼精簡

template <class T, class Container = deque<T> >
class stack {
    Container c; // 底層容器
public:
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    T& top() { return c.back(); }
    const T& top() const { return c.back(); }
    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};

所有操作直接轉發到底層容器，零開銷抽象。

queue 源碼精簡

template <class T, class Container = deque<T> >
class queue {
    Container c;
public:
    T& front() { return c.front(); }
    T& back() { return c.back(); }
    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_front(); } // 關鍵差異
};

priority_queue 核心實現

template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue {
    Container c;
    Compare comp; // 比較函數對象
public:
    // 構造時 make_heap
    template <class Iter>
    priority_queue(Iter first, Iter last, const Compare& cmp = Compare())
        : c(first, last), comp(cmp) {
        make_heap(c.begin(), c.end(), comp);
    }
    void push(const T& x) {
        c.push_back(x);
        push_heap(c.begin(), c.end(), comp);
    }
    void pop() {
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }
    const T& top() const { return c.front(); } // 堆頂
};

關鍵點：

• 默認 less<T> → 最大堆（頂端最大）。
• 傳 greater<T> → 最小堆（頂端最小），需三參數聲明：priority_queue<int, vector<int>, greater<int>> q;
• 底層調用 make_heap/push_heap/pop_heap 維護堆性質。

實戰示例

stack：十進制轉二進制

stack<int> s;
while (n) { s.push(n%2); n/=2; }
while (!s.empty()) { cout << s.top(); s.pop(); }

queue：BFS 樹層序遍歷

queue<TreeNode*> q; q.push(root);
while (!q.empty()) {
    auto node = q.front(); q.pop();
    // process
    if (node->left) q.push(node->left);
    if (node->right) q.push(node->right);
}

priority_queue：Top K / 最小堆

// 維護大小為 k 的最小堆，堆頂為第 k 大
priority_queue<int, vector<int>, greater<int>>> minHeap;
for (int x : nums) {
    if (minHeap.size() < k) minHeap.push(x);
    else if (x > minHeap.top()) { minHeap.pop(); minHeap.push(x); }
}

make_heap 直觀演示

int a[] = {5,1,2,4,3};
make_heap(a, a+5, less<int>()); // 最大堆
// 輸出層序: 5 4 2 1 3  (非完全排序)
sort(a, a+5); // 或 sort_heap(a, a+5, less<int>())
// 輸出: 1 2 3 4 5

選擇建議