232.用栈实现队列

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

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

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

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

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

代码：

class MyQueue {
public:
    //先设置两个栈 进栈和出栈
    stack<int> stIn;
    stack<int> stOut;

    MyQueue() {

    }
    //输入
    void push(int x) {
        //进栈也输入
        stIn.push(x);
    }
    //输出的时候分两种情况
    //一种是出栈中有元素 那么直接pop即可
    //一种是出栈中无元素，要先把进栈中的所以元素都导入，再pop
    int pop() {
        //如果出栈为空
        if(stOut.empty())
        {
            //把stIn中的ele全部导入进来
            while(!stIn.empty())
            {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        //出栈中有东西 直接pop
        int 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赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};