232.用栈实现队列

题目链接
状态：
文档：programmercarl.com

思路：
用栈实现队列。要先明白两者的区别。
栈：单开门，先进后出，只有一端能进出。
队列：双开门，先进先出，一端进一端出。

既然想用单开门实现双开门，那么一个单开门肯定是不够的，因为单开门进出的顺序已经不满足双开门的顺序了，所以我们需要设置两个单开门，让其中一个单开门是进栈状态，另一个单开门是出栈状态。

在push数据的时候，只要数据放进输入栈（进栈）就好。
但在pop的时候，操作就复杂一些。输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再在出栈里弹出数据；如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

代码：

class MyQueue {
public://先设置两个栈 进栈和出栈stack<int> stIn;stack<int> stOut;MyQueue() {}//输入void push(int x) {//进栈也输入stIn.push(x);}//输出的时候分两种情况//一种是出栈中有元素 那么直接pop即可//一种是出栈中无元素，要先把进栈中的所以元素都导入，再popint pop() {//如果出栈为空if(stOut.empty()){//把stIn中的ele全部导入进来while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}//出栈中有东西 直接popint result = stOut.top();stOut.pop();return result;}//返回队列开头元素//和上面的stOut.top()是一个东西//复用一下int peek() {int result = this->pop();//上面的函数中把result pop出来了，所以还需要再push回去stOut.push(result);return result;}bool empty() {//两个栈都空了 才能说明队列空了return stIn.empty() && stOut.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

225. 用队列实现栈

题目链接
状态：
文档：programmercarl.com

思路：
队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的

代码：

class MyStack {
public:queue<int> que1;queue<int> que2; // 辅助队列，用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size = que1.size();size--;while (size--) { // 将que1 导入que2，但要留下最后一个元素que2.push(que1.front());que1.pop();}int result = que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 = que2;            // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};