C++ STL 栈与队列模拟实现及容器适配器原理

1.4 栈的压入、弹出序列

牛客网址： 栈的压入、弹出序列

题目解释： 给定两个数组，第一个表示进栈的顺序，第二个数组表示出栈的顺序，判断两个数组是否为一个栈的出入栈的顺序。

思路： 只要入栈序列能模拟出出栈序列的过程，那么就是匹配的，否则不是。

1. 入栈序列先入栈（每次入一个数据）。
2. 每次入栈完后将该数据和出栈序列的数据进行比对，如果匹配则持续出数据（出栈序列指针依次往后走），不匹配则继续将入栈序列的数据入栈（入栈序列指针往后走）。
3. 入栈序列结束则结束。

代码实现：

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

1.5 二叉树的层序遍历

力扣网址： 二叉树的层序遍历

题目解释： 要求将二叉树的每一层放到二维数组的每一行上组成二维数组，这里的二维数组的每一行便不再相等（不是标准的二维数组）。

那么怎么将输入的二叉树的节点放到二维数组对应的位置上？

思路： 广度优先遍历。

1. 先将二叉树的根（3）入到队列里面，然后将其出出来，再将其的孩子入进去（9, 20）。
2. 将 9 出出来，再将 9 的孩子节点出来，因为 9 没有孩子节点，所以不用出。
3. 将 20 出出来，再将 20 的孩子节点出出来。

但是如果 9 有孩子节点，那么队列中会同时存在两层不同的数据，那么我们怎么区分？

这里我们想到可以使用最小栈的思路，定义两个队列，第一个队列存放树的节点的指针，第二个队列存该数据是第几层的：

1. 我们在 q1 队列入数的根节点（3），3 对应的是第一层，因此 q2 队列存放 1。
2. 将 3 和 1 出队列，再将 3 的孩子 9, 20 入队列，因为根节点对应的是第一层，因此其孩子节点只需 ++，即第二层。
3. 将 9 出出来，因为其没有孩子节点，所以 q2 不入数据，q1 出 20，将 20 的孩子节点 15, 7 入数据，15, 7 对应的是第三层。

但是由于定义了两个队列，有所繁琐，下面我们只使用一个队列看看如何搞定！

思路 2：定义变量 levelSize 代表当前层的数据个数，我们每一次出数据都将该层的数据全部出出来（levelSize 为 0 代表该层的数据出完了）。

1. 将根节点 3 入队列，levelSize 为 1，将 3 出队列，孩子节点 9, 20 入队列，levelSize 更新为 2。
2. 将 9 出队列 levelSize 变为 1，再将 20 出队列，levelsize 为 0，再将其孩子节点 15, 7 入队列，levelSize 更新为 2，因此队列的 size 就是下一层的数据个数。

代码实现：

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;
            while (levelsize--) {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            vv.push_back(v);
            levelsize = q.size();
        }
        return vv;
    }
};

二、模拟实现栈

2.1 容器适配器

在传统实现容器时我们都使用模板，如下：

但在这里我们便使用适配器，那么什么是适配器？

适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。

在日常生活中由于家里的供电标准是 120v，但是实际上我们手机或者电灯充电的是 3v/5v，那么为什么我们的设备没有因为电量过大导致炸了？这便是因为我们使用了充电器将电压转换成我们需要的功率。

2.2 栈的实现

在认识到适配器后，我们思考下栈的特点便是在栈顶插入删除元素这些操作，在我们已经学到的容器中 vector 和 list 支持在一段插入删除数据，因此其通过封装便可得到栈，这里我们传 Container（容器），好处便是栈的类型不再写死，而是可以传 vector/list 都可以，通过 Container 适配转换出要的 stack。

代码实现：

#include <vector>
#include <list>

namespace hxx {
    template<class T, class Container = vector<T>>
    class stack {
    public:
        void push(const T& x) { _con.push_back(x); }
        void pop() { _con.pop_back(); }
        const T& top() { return _con.back(); }
        size_t size() const { return _con.size(); }
        bool empty() const { return _con.empty(); }
    private:
        Container _con;
    };
}

三、模拟实现队列

队列的实现与栈的实现大同小异，但是我们需要注意队列的实现不能通过封装 vector 来适配出队列。

1. 队列删除队头元素对应的是 pop_front，但是在 vector 中没有该接口。
2. vector 头插和头删的效率低下。

代码实现：

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

四、总结

希望读完本文可以帮助读者更好了解栈和队列的底层逻辑。