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

队列 (Queue)

队列遵循先进先出（FIFO）原则。

常用接口一览

• empty(), size(): 状态查询
• front(), back(): 访问队头/队尾
• push(val): 队尾入队
• pop(): 队头出队

同样没有迭代器支持直接遍历。

模拟实现

namespace renshen {
template<class T, class Container = deque<T>>
class queue {
public:
    void push(const T& x) { _con.push_back(x); }
    void pop() { _con.pop_front(); }
    T& front() { return _con.front(); }
    T& back() { return _con.back(); }
    size_t size() { return _con.size(); }
    bool empty() { return _con.empty(); }
private:
    Container _con;
};
}

双端队列 (Deque)

相比于 vector，deque 极大缓解了扩容问题并支持头插头删；相比于 list，它支持下标随机访问且 CPU 高速缓存效率不错。

总结： deque 适合高频头插头删、尾插尾删，并且需要少量下标随机访问的场景。

其模拟实现通常采用中控指针数组（控制分散的一片一片区域），当中控指针数组满了再扩容即可。

常见接口

begin, end, rbegin, rend, size, empty, resize, [], front, back, erase, clear, push_front, push_back, pop_front, pop_back, insert

容器适配器概览

命名上通常沿用 container 作为模板参数名，让模板更具通用性。

优先级队列 (Priority Queue)

优先级队列本质上是堆，堆顶即为优先级最高的元素。处理 TopK 问题时用堆排序效果较好，全排序则建议直接使用 std::sort（时间复杂度 O(NlogN)）。

常用接口

• empty, size, top, push, pop
• 无迭代器，遍历需逐项取出

模拟实现

这里展示了基于向量构建大堆的核心逻辑，包含向上调整和向下调整算法。

namespace renshen {
template<class T, class Container = vector<T>, class Compare = 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])) {
                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])) {
                swap(_con[child], _con[parent]);
                child = parent;
                parent = (child - 1) / 2;
            } else break;
        }
    }

public:
    priority_queue() {}

    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 pop() {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        AdjustDown(0);
    }

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

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

private:
    Container _con;
};
}

反向迭代器

rbegin 其实指向 end 位置，rend 指向 begin 位置（注意 rbegin 并不是最后一个有元素的位置，而是逻辑上的起始）。

namespace renshen {
template<class Iterator, class Ref, class Ptr>
struct ReverseIterator {
    typedef ReverseIterator<Iterator, Ref, Ptr> Self;
    Iterator _it;

    ReverseIterator(Iterator it) : _it(it) {}

    Ref operator*() {
        Iterator tmp = _it;
        return *(--tmp);
    }

    Ptr operator->() { return &(operator*()); }

    Self& operator++() {
        --_it;
        return *this;
    }

    Self& operator--() {
        ++_it;
        return *this;
    }

    bool operator!=(const Self& s) const {
        return _it != s._it;
    }
};
}

引申：重载运算符的结合性和优先级是跟本身的运算符一样的。

仿函数 (Function Object)

仿函数即函数对象，类对象可以像函数一样使用。库里面的 less<T> 用来搞升序，greater<T> 用来搞降序。

相比普通函数，仿函数具有状态保持等优势，但需注意其类型可能因状态不同而不同。

实战演练

理论之外，实战更能检验掌握程度。以下精选了几道经典题目，展示容器的妙用。

最小栈 (Min Stack)

思路： 维护两个栈，一个存数据 _st，另一个存最小值 _min。插入时若比当前最小值小或为空则压入 _min；弹出时若与 _min 栈顶相同则同步弹出。

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:
    stack<int> _st;
    stack<int> _min;
};

栈的弹出压入序列

思路： 利用辅助栈模拟入栈过程。栈没跟出栈序列的元素匹配就入数据，匹配了就出数据。全入完了栈里还有数据说明不对。

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st;
        int pushi = 0;
        int popi = 0;
        while (pushi <= pushV.size() - 1) {
            st.push(pushV[pushi++]);
            while (!st.empty() && st.top() == popV[popi]) {
                popi++;
                st.pop();
            }
        }
        return popi == pushi;
    }
};

二叉树的层序遍历

思路： 使用 queue 进行广度优先搜索。注意处理 root 为空的情况。对于自底向上的版本，只需在结果基础上 reverse 即可。

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

数组中的第 K 个最大元素

思路：

1. 建大堆，把前 k-1 个堆顶踢了。
2. 建 k 个元素的小堆，遍历数组，比堆顶大则替换。最终堆顶即为第 K 大。 注意：建小堆要用 greater<T>。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for (auto e : nums) {
            pq.push(e);
        }
        while (k > 1) {
            pq.pop();
            k--;
        }
        return pq.top();
    }
};

知识点辨析

• 仿函数特性： 仿函数在同一时间里可代表单一函数但有不同状态；定义相同也可能类型不同；使代码变简单。关于速度，通常认为与普通函数相当或略慢（因虚函数开销），但在特定优化下表现优异。
• 容器选择： 如果需要高效的随机存取，还要大量的首尾插入删除，建议使用 deque。
• 迭代器失效： vector 和 deque 底层是连续空间，删除元素会挪动数据，可能导致原有迭代器失效；list 是链表，删除节点不影响其他节点迭代器。

补充说明

• 逆波兰表达式： 后缀表达式，操作数顺序不变，操作符按优先级重排。转换时遇到左括号视为新起点，右括号停止递归出栈。
• 内存分配： 堆上开辟的空间地址随机；栈空间则遵循固定规则。
• 命名空间： 自定义头文件若未展开命名空间，需在.cpp 文件中显式展开，避免编译错误。