stack 和 queue练习

 题设：仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
 void push(int x) 将元素 x 推到队列的末尾
 int pop() 从队列的开头移除并返回元素
 int peek() 返回队列开头的元素
 bool empty() 如果队列为空，返回 true ；否则，返回 false
 要求：你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
所使用的语言如果不支持栈。可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路：一个作入数据栈 pushStack，另一个出数据栈 popStack。
 入队列 void push(int x)：直接往 pushStack 中入数据。
 出队列 int pop() ：popStack 先判空，空的就先从 pushStack 中入数据（梭哈），然后再对 popStack 取栈顶、出栈。
 取队头 int peek() ：和出队列就差一个出栈。
 判空 bool empty()：见代码。

	class MyQueue {public:MyQueue() {}void push(int x) {_pushStack.push(x);}int pop() {//_popStack 为空先将 _pushStack 的数据压入_popStackif(_popStack.empty()){while(!_pushStack.empty()){int top = _pushStack.top();_pushStack.pop();_popStack.push(top);}}//取队头，出队头int top = _popStack.top();_popStack.pop();return top;}int peek() {//_popStack 为空先将 _pushStack 的数据压入_popStackif(_popStack.empty()){while(!_pushStack.empty()){int top = _pushStack.top();_pushStack.pop();_popStack.push(top);}}//取队头，出队头int top = _popStack.top();return top;}bool empty() {return _pushStack.empty() && _popStack.empty();}private:stack<int> _pushStack;stack<int> _popStack;
};

 题设：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
 MinStack() 初始化堆栈对象。
 void push(int val) 将元素val推入堆栈。
 void pop() 删除堆栈顶部的元素。
 int top() 获取堆栈顶部的元素。
 int getMin() 获取堆栈中的最小元素。

 思路：一个普通栈 _Stack 存所有数据，一个最小栈 _minStack 存小数据，而且栈顶一定是最小的数据。
 入栈：_Stack 直接放数据； _minStack 为空或者栈顶数据比要入的数据大或相等，才把数据入栈。
 出栈：取 _Stack 的栈顶（记为 top） 然后出栈；top 与 _minStack 栈顶数据比，相等才出栈。
 取栈顶：取 _Stack 的栈顶；
 获取堆栈中的最小元素：取**_minStack** 栈顶；

	class MinStack {public://入栈void push(int val){_Stack.push(val);if(_minStack.empty() || _minStack.top() >= val){_minStack.push(val);}}//出栈void pop(){int top = _Stack.top();_Stack.pop();if(top == _minStack.top()){_minStack.pop();}}//取栈顶int top(){return _Stack.top();}//取栈中最小元素int getMin(){return _minStack.top();}private:stack<int> _Stack;stack<int> _minStack;};

 题设：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
    思路：先放进一个数据，然后循环匹配栈顶与出栈序列的数据，相同则换这个序列的下一个数据，不同再将其他数据入栈，直到入数据序列结束。
   

	class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> Stack;size_t i = 0, j = 0;while(i < pushV.size()){//1.入栈Stack.push(pushV[i++]);//2.循环匹配栈顶数据和出栈序列while(!Stack.empty() && Stack.top() == popV[j]){j++;Stack.pop();}}//栈为空就是正确顺序return Stack.empty();}
};

 题设：给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
 思路：所谓逆波兰表达式，如图。

	class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> Stack;for(auto e : tokens){//符号取数据计算，结果入栈if(e == "+" || e == "-" || e == "*" || e == "/"){int right = Stack.top();Stack.pop();int left = Stack.top();Stack.pop();switch(e[0]){case '+':Stack.push(left + right);break;case '-':Stack.push(left - right);break;case '*':Stack.push(left * right);break;case '/':Stack.push(left / right);break;}}else{//数字入栈Stack.push(stoi(e));}}return Stack.top();}
};

一定注意，碰到运算符连续两次出栈的数字，分别是右操作数和左操作数，不能弄混了！ stoi 将字符转换成数字。

 题设：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 思路： 如图，

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {//队列实现queue<TreeNode*> q;vector<vector<int>> vv;//获取当前层的结点数int levelSize = 0;//根节点入队列，获取队列大小if(root){q.push(root);levelSize = q.size();}while(!q.empty()){//用 v 出每一层的结点数据vector<int> v;//将当前层的结点出掉，它们的孩子结点入队列while(levelSize--){//取队头TreeNode* front = q.front();//出对头q.pop();//将当前结点数据放到 v 中v.push_back(front->val);//将结点的孩子结点入队列if(front->left)     q.push(front->left);if(front->right)    q.push(front->right);}//把当前层遍历的数据放到 vv 中vv.push_back(v);//获得下一层的结点数levelSize = q.size();}return vv;}
};

————————————————————
学习记录