The classic dual stack implementation queue, pay attention to the modification of the judgment conditions of traversing the stack.

Topic content

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 ）

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/implement-queue-using-stacks
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

The stack is forward and out , Two stacks can naturally realize FIFO , We just need to input on a stack , Output on another stack , Only when the output stack is empty , We send all the elements of the input stack to the output stack , You can realize the first in, first out function of the queue . However, it should be noted here that all input stacks must be put into the output stack , Otherwise, it will be nothing .
The concrete implementation is really very simple , Just pay attention to one small point , That is, the traversal of the stack cannot be used in the determination of recycling a.size() In this format , Because this variable is variable in the loop , Easy to walk .

Code

class MyQueue {
    
public:
    stack<int> a;
    stack<int> b;
    MyQueue() {
    
    }
    
    void push(int x) {
    
        a.push(x);
    }
    
    int pop() {
    
        if(b.size()==0){
    
            int l=a.size();
            for(int i=0;i<l;i++){
    
                int num=a.top();
                a.pop();
                b.push(num);
            }
        }
        int ans=b.top();
        b.pop();
        if(b.size()==0){
    
            int l=a.size();
            for(int i=0;i<l;i++){
    
                int num=a.top();
                a.pop();
                b.push(num);
            }
        }
        return ans;
    }
    
    int peek() {
    
        if(b.size()==0){
    
            int l=a.size();
            for(int i=0;i<l;i++){
    
                
                int num=a.top();cout<<num<<endl;
                a.pop();
                b.push(num);
            }
        }
        return b.top();
    }
    
    bool empty() {
    
        if(b.size()==0&&a.size()==0){
    
            return true;
        }
        else{
    
            return false;
        }
    }
};

/** * 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(); */