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;}
};