232-用栈实现队列

LeetCode 232. Implement Queue using Stacks

LeetCode-232

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

method

用两个栈模拟队列，需要pop()和top()的时候就把一个栈里面的输出来放到另一个栈里，在这过程中顺序就反了

注意：
如果out非空，那top()和pop()的操作都可以在out中实现，不需要用到in里面的元素，只有当out里面没元素了，才需要把in里的元素搞过来

class MyQueue {
public:
    stack<int> in;
    stack<int> out;
    MyQueue() {}

    void push(int x) {
        in.push(x);
    }

    int pop() {
        in2out();
        int x = out.top();
        out.pop();
        return x;
    }
    
    int peek() {
        in2out();
        return out.top();
    }

    void in2out() {
        if (out.empty()) {  // out是空才需要移动
            while (!in.empty()) {   // 把in的所有元素都移到out
                int x = in.top();
                in.pop();
                out.push(x);
            }
        }
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};