stack和queue专题

stack

   stack和queue都是空间适配器
  

最小栈

   最小栈的题目链接
  

题目剖析

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

代码

1. class MinStack {
2. public:
3.     MinStack() {
4.         
5.     }
6.    
7.     void push(int val)
8.     {
9.         st.push(val);
10.         if(minst.empty() || val <= minst.top())
11.         {
12.             minst.push(val);
13.         }
14.     }
15.    
16.     void pop()
17.     {
18.         if(st.top() == minst.top())
19.         {
20.             minst.pop();
21.         }   
22.         st.pop();
23.     }
24.    
25.     int top()
26.     {
27.         return st.top();   
28.     }
29.    
30.     int getMin()
31.     {
32.        return minst.top();   
33.     }
34. private:
35.     stack<int> st;
36.     stack<int> minst;
37. };

复制代码

栈的压入弹出序列

   栈的压入弹出序列
  

题目剖析

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

代码

1. class Solution
2. {
3. public:
4.     bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
5.     {
6.         size_t popi = 0;
7.         stack<int> st;
8.         for(auto& ch : pushV)
9.         {
10.             // 入栈
11.             st.push(ch);
12.             
13.             // 入栈和出栈元素匹配
14.             // 栈不为空取栈顶元素，一种特殊情况
15.             // 1,2,3,4,5  4,3,2,1,5
16.             // 栈会为空，不加!st.empty(),会崩溃
17.             // 持续出栈
18.             while(!st.empty() && st.top() == popV[popi])
19.             {
20.                 st.pop();
21.                 ++popi;
22.             }
23.         }
24.         // 如果栈为空就返回true,都出完了
25.         // 如果栈为假就返回false,popV出不了了，就不匹配
26.         return st.empty();
27.     }
28. };

复制代码

queue

二叉树的层序遍历

   二叉树的层序遍历
  

题目剖析

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

代码

1. class Solution
2. {
3. public:
4.     vector<vector<int>> levelOrder(TreeNode* root)
5.     {
6.         vector<vector<int>> vv;
7.         queue<TreeNode*> q;
8.         size_t levelSize = 0;
9.         if(root)
10.         {
11.             q.push(root);
12.             levelSize = 1;
13.         }
15.         while(!q.empty())
16.         {
17.             vector<int> v;
18.             while(levelSize--)
19.             {
20.                 TreeNode* front = q.front();
21.                 v.push_back(front->val);
22.                 q.pop();
24.                 if(front->left)
25.                 q.push(front->left);
27.                 if(front->right)
28.                 q.push(front->right);
29.             }            
30.             vv.push_back(v);
31.             levelSize = q.size();
32.         }
33.         return vv;
34.     }
35. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。