【LeetCode 0225】【队列】用队列实现栈

描述

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

注意

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

例子

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
 

约束

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

JS实现

var MyStack = function() {
	// 使用2个队列
    this.queue1 = []
    this.queue2 = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    // 任何时候非空队列作为压栈队列
    if(this.queue1.length){
        this.queue1.push(x)
    }else{
        this.queue2.push(x)
    }
};

/**
 * @return {number}
 */
MyStack.prototype.pop = function() {
	// 出栈时，如果队列非空（即为压栈队列），则将除了最后元素外的所有元素倒入空队列中，并且弹出最后一个元素
    if(this.queue1.length){
        while(this.queue1.length>1){
            this.queue2.push(this.queue1.shift())
        }
        return this.queue1.shift()
    }else{
        while(this.queue2.length>1){
            this.queue1.push(this.queue2.shift())
        }
        return this.queue2.shift()
    }
};

/**
 * @return {number}
 */
MyStack.prototype.top = function() {
	// 查看栈顶元素，跟出栈操作类似，将所有元素从非空入栈队列倒入空队列中，并返回非空队列最后一个元素
    let e
    if(this.queue1.length){
        while(this.queue1.length>1){
            this.queue2.push(this.queue1.shift())
        }
        e =  this.queue1.shift()
        this.queue2.push(e)
    }else{
        while(this.queue2.length>1){
            this.queue1.push(this.queue2.shift())
        }
        e = this.queue2.shift()
        this.queue1.push(e)
    }
    return e
};

/**
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
	//当且仅当两个队列为空时，整个栈为空
   return  !this.queue1.length && !this.queue2.length 
};

/** 
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */