stack和queue专题

stack

stack和queue都是空间适配器

最小栈

最小栈的题目链接

题目解析

• minst是空就进栈，或者是val <= minst.top()就进栈
  

代码

class MinStack {
public:
    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;
};

栈的压入弹出序列

栈的压入弹出序列

题目解析

1.入栈序列入栈一个值（一个一个地入栈）
2.栈顶元素跟出栈序列是否匹配，持续出
3.不匹配看入栈是否已经入完了，没有入完继续入，入完了就结束了

代码

class Solution 
{
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        size_t popi = 0;
        stack<int> st;
        for(auto& ch : pushV)
        {
            // 入栈
            st.push(ch);
            
            // 入栈和出栈元素匹配
            // 栈不为空取栈顶元素，一种特殊情况
            // 1,2,3,4,5  4,3,2,1,5
            // 栈会为空，不加!st.empty(),会崩溃
            // 持续出栈
            while(!st.empty() && st.top() == popV[popi])
            {
                st.pop();
                ++popi;
            }
        }
        // 如果栈为空就返回true,都出完了
        // 如果栈为假就返回false,popV出不了了，就不匹配
        return st.empty();
    }
};

queue

二叉树的层序遍历

二叉树的层序遍历

题目解析

根节点出队列，把根节点的孩子入队列
1.设置一个变量记录当前层的节点个数
2.一层一层出，队列的size就是当前层的size
因为出一个节点就把它的孩子带入，只有它的孩子在队列中，所以队列的size就是当前层的levelSize

代码

class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> vv;
        queue<TreeNode*> q;
        size_t levelSize = 0;
        if(root)
        {
            q.push(root);
            levelSize = 1;
        }

        while(!q.empty())
        {
            vector<int> v;
            while(levelSize--)
            {
                TreeNode* front = q.front();
                v.push_back(front->val);
                q.pop();

                if(front->left)
                q.push(front->left);

                if(front->right)
                q.push(front->right);
            }            
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
};