You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

Void push(int x) pushes element x to the end of the queue int pop() removes the element from the beginning of the queue and returns the element int peek() returns the element at the beginning of the queue Boolean empty() Returns true if the queue is empty; Otherwise, return false

Description:

You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are legal. Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Advanced:

Can you implement queues with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time.

Example:

Input: [” MyQueue “, “push” and “push” and “peek”, “pop”, “empty”]

[], [1], [2], [], []

Output: [null, NULL, NULL, 1, 1, false]

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  

Tip:

1 <= x <= 9

Push, POP, peek, and Empty are called up to 100 times

Assume that all operations are valid (for example, an empty queue does not call pop or PEEK)

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

A stack is used as an input stack for pushing data passed by push; The other stack acts as an output stack for POP and PEEK operations.

Each pop or PEEK, if the output stack is empty, all the data of the input stack will be popped and pushed into the output stack in turn, so that the sequence of the output stack from the top to the bottom is the sequence of the queue from the front to the back.

Code:

var MyQueue = function(){
    this.inStack=[]
    this.outStack=[]
};

MyQueue.prototype.push=function(x){
    this.inStack.push(x)
}

MyQueue.prototype.pop=function(){
    if(!this.outStack.length){
        this.in2out()
    }
    return this.outStack.pop()
}

MyQueue.prototype.peek=function(){
    if(!this.outStack.length){
        this.in2out()
    }
    return this.outStack[this.outStack.length-1]
}

MyQueue.prototype.empty=function(){
    return this.outStack.length===0&&this.inStack.length===0
}

MyQueue.prototype.in2out=function(){
    while(this.inStack.length){
        this.outStack.push(this.inStack.pop())
    }
}

Copy the code