【C++STL ：stack && queue (一) 】STL：stack与queue全解析｜深入使用（附高频算法题详解）

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        // 不用管，甚至可以直接删掉这个函数
        // 留着也可以，会调用默认构造
    }
    
    void push(int val) {
        _st.push(val);

        if(_minst.empty() || val <= _minst.top())
            _minst.push(val);
    }
    
    void pop() {
        if(_st.top() == _minst.top())
            _minst.pop();

        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
    private:
    stack<int> _st;
    stack<int> _minst;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str : tokens)
        {
            // 判断四种运算符
            if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                // 运算符
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch(str[0]) // 大坑：switch...case语句只能是int类型
                {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;
                }
            }
            else
            {
                // 运算数
                st.push(stoi(str)); // 字符串转整型，to_string
            }
        }
        return st.top();
    }
};

#include <iterator>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // 定义两个下标，分别指向入栈和出栈序列
        size_t pushi = 0,popi = 0;
        stack<int> st; // 定义一个栈
        while(pushi < pushV.size())
        {
            st.push(pushV[pushi]);

            while(!st.empty() && st.top() == popV[popi])  
            {
                st.pop();
                popi++; // 弹出一次，popi往后走
            }
            // pushi往后走
            pushi++;
        }
        // 是返回true，否返回false
        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) {
        queue<TreeNode*> q;
        // 创建一个新变量levelSize，记录层数,一层一层出
        int levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }

        // 设计很精妙
        vector<vector<int>> vv; 
        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;
    }
};

#define  _CRT_SECURE_NO_WARNINGS  1

// stack 和 queue的使用：构造、增删
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

int main()
{
	// 栈(stack)的使用演示
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.emplace(4); // emplace是C++11的高效插入

	// 遍历并清空栈 (LIFO: 后进先出)
	while (!st.empty())
	{
		cout << st.top() << " "; // 输出栈顶元素：4 3 2 1
		st.pop(); // 弹出栈顶元素
	}
	cout << endl;

	// 队列(queue)的使用演示
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.emplace(4); // emplace是C++11的高效插入

	while (!q.empty())
	{
		cout << q.front() << " "; // 输出队头元素
		q.pop();				// 出队
	}

	return 0;
}