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

Queue

队列的话是先进先出

常见接口

• empty()
• size()
• front()
• back()
• push(val)
• pop()

也没有迭代器

Queue 的模拟实现

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;
    };
    // 引申：vector 和 list 都有 front 和 back
}

Deque

相比于 vector:

1. deque极大缓解了扩容问题和能头插头删
2. deque的 [] 不太行，随机访问太慢了

相比于 list:

1. deque支持下标随机访问
2. dequecpu 高速缓存的效率不错
3. list的中间插入比 deque好很多

总结:deque适合高频头插头删，尾插尾删；并且需要少量下标随机访问

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 问题的话用堆排序好些，全排序的话还是 sort 时间复杂度是 nlogn

常用接口

empty size top push(push进去自动排) pop(pop的最顶上那个) --没有迭代器--遍历的话只能逐项走过去 

Priority Queue 模拟实现

namespace renshen {
    template<class T, class Container = vector<T>, class Comapre = less<T>>
    class priority_queue {
    private:
        void AdjustDown(int parent) {
            Comapre 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) {
            Comapre 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;
        }
    };
}

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

仿函数 (又叫函数对象)

这个类对象可以像函数一样使用

引申：库里面的 less是用来搞升序的，greater是用来搞降序的

作业部分

力扣 155. 最小栈

// 力扣 最小栈 注意：那个题能用容器来做！做法：搞两个栈，有一个用来存最小值 (_min) --插入比当前<=的就放进去--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:
    stack<int> _st;
    stack<int> _min;
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

牛客网 栈的弹出压入序列

// 牛客网 栈的弹出压入序列 做法：栈没跟出栈序列的元素匹配就入数据，匹配了的话就出数据--全入完了栈里面还有数据就说明不对 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pushV int 整型 vector
     * @param popV int 整型 vector
     * @return bool 布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        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;
    }
};

力扣 102. 二叉树的层序遍历
107. 二叉树的层序遍历 II

力扣 102. 二叉树的层序遍历 做法：用 queue 但是要注意 root 为空的情况

二叉树的层序遍历 II 做法：就是在上一题的答案的基础上，reverse一下就行 (因为这个题要求自底向上遍历)

// 力扣 102. 二叉树的层序遍历的代码展示:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
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;
    }
};

// 107. 二叉树的层序遍历 II 的代码展示:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(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);
        }
        reverse(vv.begin(), vv.end());
        return vv;
    }
};

力扣 215. 数组中的第 K 个最大元素

力扣 215. 数组中的第 K 个最大元素 做法 1:建大堆 (把数组所有的数全放进去)，把前 k-1 个堆顶都踢了 做法二：建 k 个元素的小堆，先放 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();
    }
};

仿函数比起一般函数具有很多优点，以下描述错误的是 (C) A.在同一时间里，由某个仿函数所代表的单一函数，可能有不同的状态 B.仿函数即使定义相同，也可能有不同的类型 C.仿函数通常比一般函数速度快 D.仿函数使程序代码变简单

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

// 假设 cont 是一个 Container 的示例，里面包含数个元素，那么当 CONTAINER 为：1.vector 2.list 3.deque 会导致下面的代码片段崩溃的 Container 类型是（C）
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,2 B.2,3 C.1,3 D.1,2,3 原因：vector 和 deque 底层是连续空间，删除会挪动数据，最终导致 iter 意义变了

逆波兰表达式

引申：逆波兰表达式也叫做后缀表达式–也就是操作数顺序不变，操作符按优先级重排 举例如下:

中缀表达式 (平时的写法就是这个) 转化为后缀表达式的方法: 一。遇到操作数就输出 二。操作符: a.栈为空或当前操作符比栈顶的优先级高，这个操作符就入栈 b.栈不为空或当前操作符比栈顶的优先级低或者相等，就输出栈顶操作符 表达式结束后，依次出栈里面的操作符 注意：遇到左括号的话就递归，遇到右括号停止递归 这里的递归是: 遇到左括号时，把左括号当做新的起点，遇到右括号时就一直出栈，直到出到左括号为止

引申

自己搞的头文件里面没展开命名空间的话，在.cpp 里面要在自己头文件之前展开命名空间才行，不然会报错

在堆上开辟的空间的地址是随机的，没有地址先开就在前面的这些规定，栈就不一样