C++ 容器适配器与核心数据结构：栈、队列、Deque 底层实现与实战

Deque：分段连续存储的优势

相比于 vector，deque 极大缓解了扩容问题，并支持头插尾删；相比于 list，它支持下标随机访问且 CPU 缓存命中率更高。其内部维护了一个中控指针数组，指向分散的连续内存块。当某一块满了，就申请新的块，这种结构兼顾了灵活性与性能。

常用接口包括 begin/end、push_front/back、pop_front/back 等。注意 deque 的下标访问虽支持，但相比 vector 仍稍慢，高频随机访问场景下 vector 仍是首选。

优先级队列与堆结构

优先级队列本质上是堆（Heap）。大顶堆用于获取最大值，小顶堆用于获取最小值。对于 TopK 问题，堆排序往往比全排序更高效。堆的维护依赖于向上调整（AdjustUp）和向下调整（AdjustDown）算法。

优先级队列模拟

这里使用 vector 作为底层容器，配合仿函数控制排序逻辑。less 为升序，greater 为降序。建堆过程是从最后一个非叶子节点开始向下调整。

namespace demo {
template<class T, class Container = std::vector<T>, class Compare = std::less<T>>
class priority_queue {
private:
    void AdjustDown(int parent) {
        Compare com;
        size_t child = parent * 2 + 1;
        while (child < _con.size()) {
            if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
                ++child;
            }
            if (com(_con[parent], _con[child])) {
                std::swap(_con[child], _con[parent]);
                parent = child;
                child = parent * 2 + 1;
            } else break;
        }
    }

    void AdjustUp(int child) {
        Compare com;
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (com(_con[parent], _con[child])) {
                std::swap(_con[child], _con[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
    }

public:
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last) {
        while (first != last) {
            _con.push_back(*first);
            ++first;
        }
        for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
            AdjustDown(i);
        }
    }

    void push(const T& x) {
        _con.push_back(x);
        AdjustUp(_con.size() - 1);
    }

    void pop() {
        std::swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        AdjustDown(0);
    }

    const T& top() { return _con[0]; }
    bool empty() const { return _con.empty(); }
    size_t size() const { return _con.size(); }

private:
    Container _con;
};
}

反向迭代器与仿函数

反向迭代器并非简单反转指针，而是通过重载运算符实现逻辑上的倒序遍历。rbegin 对应 end 位置，rend 对应 begin 位置。其 ++ 操作实际上是底层迭代器的 -- 操作。

仿函数（函数对象）则提供了状态保持的能力，相比普通函数更灵活。例如 less 和 greater 分别用于控制堆的升序与降序排列。

实战演练

理论结合实践才能巩固理解。以下是几个经典场景的解决方案。

最小栈

利用两个栈，一个存数据，一个存历史最小值。入栈时若新值小于等于当前最小值，同步压入辅助栈；出栈时若弹出值等于辅助栈顶，同步弹出。

class MinStack {
public:
    void push(int val) {
        _st.push(val);
        if (_min.empty() || val <= _min.top()) _min.push(val);
    }
    void pop() {
        if (_st.top() == _min.top()) _min.pop();
        _st.pop();
    }
    int top() { return _st.top(); }
    int getMin() { return _min.top(); }
private:
    std::stack<int> _st;
    std::stack<int> _min;
};

二叉树层序遍历

借助队列实现广度优先搜索。注意处理根节点为空的情况。若需自底向上遍历，只需在结果集生成后执行 reverse。

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> vv;
        if (!root) return vv;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            std::vector<int> v;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front(); q.pop();
                v.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            vv.push_back(v);
        }
        return vv;
    }
};

数组中的第 K 个最大元素

维护一个大小为 K 的小顶堆。遍历数组，若元素大于堆顶则替换堆顶并调整。最终堆顶即为第 K 大元素。此方法时间复杂度优于全排序。

class Solution {
public:
    int findKthLargest(std::vector<int>& nums, int k) {
        std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
        for (auto e : nums) {
            if (pq.size() < k) {
                pq.push(e);
            } else if (e > pq.top()) {
                pq.pop();
                pq.push(e);
            }
        }
        return pq.top();
    }
};

掌握这些容器的底层机制，能让你在面对复杂问题时快速找到最优的数据结构选型。真正的编程能力，往往藏在对'为什么这样设计'的追问之中。