Implement the queue through two stacks

subject

As the title described, you should only use two stacks to implement a queue’s actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

As the title says , You can only use two stacks to implement some operations of the queue . Queues should support push(element),pop() and top(), among pop Is the first in the pop-up queue ( The front of ) Elements .pop and top Methods should return the value of the first element .

title

Stack First in, then out First in Last Out
Queue First in, first out First in First Out

Through two stack Reverse can be achieved Queue structure

Ideas

Two stack
push The team When , namely Additive elements , Put it directly in stack1

pop When , from stack2 Start shooting , If stack2 It's empty , execute stack1 Put it all in stack2
then , Again from stack2 Eject .

top When , Direct execution stack.peek（） see stack2 The top element of the
If stack2 It's empty , Just put stack1 Put it all in stack2, And then from stack2 take peek

summary
When you join the team , Press elements into s1.

When the team , Judge s2 Is it empty , If not empty , Pop up the top element directly ;

If blank , Will s1 Element by element “ Pour into ”s2, Pop the last element out of the queue .

Code

public class MyQueue {
    

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
    
        // do intialization if necessary
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /* * @param element: An integer * @return: nothing */
    public void push(int element) {
    
        // write your code here
        stack1.push(element);
    }

    /* * @return: An integer */
    public int pop() {
    
        // write your code here
        if(!stack2.isEmpty()){
    
            return stack2.pop();
        }

        while(!stack1.isEmpty()){
    
            stack2.push(stack1.pop());
        }

        return stack2.pop();
    }

    /* * @return: An integer */
    public int top() {
    
        // write your code here
        if(!stack2.isEmpty()){
    
            return stack2.peek();
        }

        while( !stack1.isEmpty()){
    
            stack2.push(stack1.pop());
        }

        return stack2.peek();
    }
}

Reference

https://www.lintcode.com/problem/40/solution/18895
https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html