232. Implement queue with stack

Please use only two stacks to implement the FIFO queue . The queue should support all operations supported by the general queue （push、pop、peek、empty）：

Realization MyQueue class ：

void push(int x) Put the element x Push to the end of the queue
int pop() Remove from the beginning of the queue and return the element
int peek() Returns the element at the beginning of the queue
boolean empty() If the queue is empty , return true ; otherwise , return false
explain ：

you Can only Use standard stack operations —— It's just push to top, peek/pop from top, size, and is empty Operation is legal .
The language you use may not support stacks . You can use list perhaps deque（ deque ） To simulate a stack , As long as it's a standard stack operation .

Example 1：

Input ：

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output ：

[null, null, null, 1, 1, false]

explain ：

MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Tips ：

1 <= x <= 9
Call at most 100 Time push、pop、peek and empty
Suppose all operations are valid （ for example , An empty queue will not call pop perhaps peek operation ）

Advanced ：

Can you realize the time sharing of each operation? The complexity is O(1) Queues ？ let me put it another way , perform n The total time complexity of operations is O(n) , Even if one of the operations may take a long time .

class MyQueue {
    
public:
    stack<int> stIn;
    stack<int> stOut;
    MyQueue() {
    
        
    }
    
    void push(int x) {
    
        stIn.push(x);
    }
    
    int pop() {
    
        if (stOut.empty()){
    
             while (!stIn.empty()) {
    
                stOut.push(stIn.top());
                stIn.pop();
             }
        }
         int front = stOut.top();
         stOut.pop();
         return front;
    }
    
    int peek() {
    
         if (stOut.empty()){
    
             while (!stIn.empty()) {
    
                stOut.push(stIn.top());
                stIn.pop();
             }
        }
         int front = stOut.top();
         return front;
    }
    
    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(); */