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

同样没有迭代器。

模拟实现

template<class T, class Container = std::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，deque 支持下标随机访问且 CPU 高速缓存效率不错。

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

注：deque 的模拟实现通常使用中控指针数组（控制的是分散的一片一片区域），当中控指针数组满了时再进行扩容。

常见接口

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

priority_queue

优先级队列其实就是堆，堆顶即为最上面的元素。对于 TopK 问题，用堆排序效果较好；全排序的话还是 sort 时间复杂度为 O(nlogn)。

常用接口

• empty, size, top, push (自动排序), pop (弹出堆顶)
• 没有迭代器，遍历只能逐项走过去

模拟实现

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:
    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() {
        std::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 并不是最后一个有元素的那个位置！）。

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; }
};

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

仿函数（函数对象）

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

实战演练

最小栈

题目要求设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。

做法：搞两个栈，有一个用来存最小值（_min）。插入比当前 _min.top() 小的就放进去，pop 出的值跟 _min 栈顶一样的话 _min 也 pop。

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;
};

栈的压入弹出序列

给定两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

做法：栈没跟出栈序列的元素匹配就入数据，匹配了的话就出数据。全入完了栈里面还有数据就说明不对。

class Solution {
public:
    bool IsPopOrder(std::vector<int>& pushV, std::vector<int>& popV) {
        std::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 为空的情况。

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> vv;
        std::queue<TreeNode*> q;
        int levelsize = 0;
        if (root) {
            q.push(root);
            levelsize = 1;
        }
        while (!q.empty()) {
            std::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;
    }
};

题目二： 自底向上的层序遍历。 做法：就是在上一题的答案的基础上，reverse 一下就行。

class Solution {
public:
    std::vector<std::vector<int>> levelOrderBottom(TreeNode* root) {
        std::vector<std::vector<int>> vv;
        std::queue<TreeNode*> q;
        int levelsize = 0;
        if (root) {
            q.push(root);
            levelsize = 1;
        }
        while (!q.empty()) {
            std::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);
        }
        std::reverse(vv.begin(), vv.end());
        return vv;
    }
};

数组中的第 K 个最大元素

做法一：建大堆（把数组所有的数全放进去），把前 k-1 个堆顶都踢了。 做法二：建 k 个元素的小堆，先放 k 个进去，数组的其他数遍历；如果比堆顶大，就放进去。遍历完后，堆顶就是第 k 大的数。 注意：建小堆要用 std::greater<T>。

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

选择题解析

1. 关于仿函数：以下描述错误的是？

   • A. 在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态
   • B. 仿函数即使定义相同，也可能有不同的类型
   • C. 仿函数通常比一般函数速度快
   • D. 仿函数使程序代码变简单
   • 答案：C（仿函数通常比一般函数慢，因为涉及虚函数或模板实例化开销，但在某些优化场景下可内联）

2. 关于容器特性：以下说法正确的是？

   • A. deque 的存储空间为连续空间
   • B. list 迭代器支持随机访问
   • C. 如果需要高效的随机存取，还要大量的首尾的插入删除则建议使用 deque
   • D. vector 容量满时，那么插入元素时只需增加当前元素个数的内存即可
   • 答案：C

3. 关于迭代器失效：假设 cont 是一个 Container 的示例，里面包含数个元素，那么当 CONTAINER 为：1.vector 2.list 3.deque 会导致下面的代码片段崩溃的 Container 类型是？

   int main() {
       Container cont = {1, 2, 3, 4, 5};
       Container::iterator iter, tempIt;
       for (iter = cont.begin(); iter != cont.end();) {
           tempIt = iter;
           ++iter;
           cont.erase(tempIt);
       }
   }
   

   • 答案：A (1, 3)
   • 原因：vector 和 deque 底层是连续空间，删除会挪动数据，最终导致 iter 意义变了（失效）。list 是链表，删除节点不影响其他节点的地址。

逆波兰表达式

逆波兰表达式也叫后缀表达式，即操作数顺序不变，操作符按优先级重排。

中缀表达式转化为后缀表达式的方法：

1. 遇到操作数就输出
2. 操作符：
   • a. 栈为空或当前操作符比栈顶的优先级高，这个操作符就入栈
   • b. 栈不为空或当前操作符比栈顶的优先级低或者相等，就输出栈顶操作符
3. 表达式结束后，依次出栈里面的操作符

注意：遇到左括号的话就递归，遇到右括号停止递归。这里的递归是指遇到左括号时，把左括号当做新的起点，遇到右括号时就一直出栈，直到出到左括号为止。

补充说明

• 自己搞的头文件里面没展开命名空间的话，在 .cpp 里面要在自己头文件之前展开命名空间才行，不然会报错。
• 在堆上开辟的空间的地址是随机的，没有地址先开就在前面的这些规定，栈就不一样。