面试题 03.04. 化栈为队

[GpingFeng]

面试题 03.04. 化栈为队

解题思路

题目要求用两个栈来实现队列，我们要定义两个栈 this.stack = [];this.vmStack = [];，因为入栈的操作和队列是一样的，但是出队列方式和出栈的方式不一样，队列是先进先出，栈是先进先出，用辅助栈解决这个问题。

可以理解 vmStack 是用来进行出栈时候，现有在 stack 的 “倒序”，这样就可以跟出栈一样出队列了

代码

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stack = [];
    this.vmStack = [];
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    for (let i = this.vmStack.length; i > 0; i--) {
        this.stack.push(this.vmStack.pop());
    }
    this.stack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    for (let i = this.stack.length - 1; i >= 0; i--) {
        this.vmStack.push(this.stack.pop());
    }
    return this.vmStack.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    for (let i = this.stack.length - 1; i >= 0; i--) {
        this.vmStack.push(this.stack.pop());
    }
    console.log(this.vmStack);
    return this.vmStack[this.vmStack.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.vmStack.length && !this.stack.length;
};

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

复杂度

• 时间复杂度——O(n)
• 空间复杂度——O(n)

[GpingFeng]

解法二思路——减少复制的步骤

可以看到，push 的时候，不需要从辅助栈中复制到 stack 中，pop 或者 peek 的时候，如果 vmStack 为空，则将 stack 里的所有元素弹出插入到 vmStack 里

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stack = [];
    this.vmStack = [];
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
+    // for (let i = this.vmStack.length; i > 0; i--) {
+   //     this.stack.push(this.vmStack.pop());
+    // }
    this.stack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
+    if (this.vmStack.length) {
+       return this.vmStack.pop();
+    }
    for (let i = this.stack.length - 1; i >= 0; i--) {
        this.vmStack.push(this.stack.pop());
    }
    return this.vmStack.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
+    if (this.vmStack.length) {
+       return this.vmStack[this.vmStack.length - 1];
+    }
    for (let i = this.stack.length - 1; i >= 0; i--) {
        this.vmStack.push(this.stack.pop());
    }
    return this.vmStack[this.vmStack.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return !this.vmStack.length && !this.stack.length;
};

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

[GpingFeng]

剑指 Offer 09. 用两个栈实现队列