【C++STL上】栈和队列模拟实现 容器适配器 力扣经典算法秘籍

class MinStack {
public:
    MinStack() {
    }
    
    void push(int val) {
       _str.push(val);
       if(_minstr.empty()||val<=_minstr.top())
           _minstr.push(val);

    }
    
    void pop() {
        if(_str.top()==_minstr.top())
        {
            _minstr.pop();
        }
        _str.pop();
    }
    
    int top() {
        return _str.top();
    }
    
    int getMin() {
        return _minstr.top();
    }

    private:
    stack<int> _str;
    stack<int> _minstr;
};

/**
 * 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) {
       size_t popi=0;
        stack<int> st;
        for(auto e:pushV)
        {
            //入栈
            st.push(e);

            //入栈序列与出栈序列匹配
            while(!st.empty()&&st.top()==popV[popi])
            {
               //将数据出栈,如果持续的出数据导致st中为空，无法取栈顶元素
                st.pop();
                //让popi走向下一个位置
                popi++;
            }
        }
            return st.empty();
    }
};

/**
 * 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;
            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);
            //当前层出完，下一层都进队列了，队列的size就是下一层的数据个数
            levelsize=q.size();
        }
        return vv;
    }
};

#include<vector>
#include<list>
//栈这个容器可以使用其他容器进行封装转换得到栈
//栈顶插入/删除即可
//vector/list都可以在一段插入和删除数据，那么我们通过封装vector/list得到栈
namespace hxx
{
	//用Contaier适配转换出要的栈
	template<class T,class Container==vector<T>>
	class stack
	{
	public:
		//栈的构造函数便不需要写，因为Container是自定义类型，会调用Container的构造函数
		//我们统一把尾部当成栈顶
		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;
	};

}

#pragma once

namespace hxx
{
	//Container适配转换出queue，队列需要在一段进，另外一端出，这里我们不能使用vector进行适配，因为队列是删除队头元素，vector中没有pop_front接口
	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;
	};
}