用两个栈实现队列

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路

栈1:

用于入队列存储

栈2:

出队列时将栈1的数据依次出栈，并入栈到栈2中

栈2出栈即栈1的底部数据即队列要出的数据。

注意:

栈2为空才能补充栈1的数据，否则会打乱当前的顺序。

• 

代码

var CQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if (this.stack2.length == 0) {
        while(this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop() || -1;
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

复杂度分析

• 时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为 O(1)。

• 空间复杂度：O(n)。需要使用两个栈存储已有的元素。

• leetcode (opens new window)

两个队列实现栈

两个队列分别作为压入队列

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
    this.quene1 = [];
    this.quene2 = [];
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
    if (this.quene1.length === 0) {
        this.quene1.push(x);
        while(this.quene2.length > 0) {
            this.quene1.push(this.quene2.shift());
        }
    } else if (this.quene2.length === 0) {
        this.quene2.push(x);
        while(this.quene1.length > 0) {
            this.quene2.push(this.quene1.shift());
        }
    }
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    if (this.quene1.length > 0) {
        return this.quene1.shift();
    } else if (this.quene2.length > 0) {
        return this.quene2.shift();
    }
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    if (this.quene1.length > 0) {
        return this.quene1[0];
    } else if (this.quene2.length > 0) {
        return this.quene2[0];
    }
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    return this.quene1.length === 0 && this.quene2.length === 0;
};

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

复杂度分析

• 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。 入栈操作需要将 queue1中的 n 个元素出队，并入队 n+1n+1 个元素到 queue2，共有 2n+12n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。 出栈操作对应将queue1的前端元素出队，时间复杂度是 O(1)O(1)。获得栈顶元素操作对应获得queue1的前端元素，时间复杂度是 O(1)。 判断栈是否为空操作只需要判断 queue1是否为空，时间复杂度是 O(1)O(1)。

• 空间复杂度：O(n)，其中 n 是栈内的元素。需要使用两个队列存储栈内的元素。

方法二：一个队列

方法一使用了两个队列实现栈的操作，也可以使用一个队列实现栈的操作。 使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。 入栈操作时，首先获得入栈前的元素个数 nn，然后将元素入队到队列，再将队列中的前 nn 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。 由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。 由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

复杂度分析

时间复杂度：入栈操作 O(n)，其余操作都是 O(1)。 入栈操作需要将队列中的 n 个元素出队，并入队 n+1n+1 个元素到队列，共有 2n+12n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)。 出栈操作对应将队列的前端元素出队，时间复杂度是 O(1)。 获得栈顶元素操作对应获得队列的前端元素，时间复杂度是 O(1)。 判断栈是否为空操作只需要判断队列是否为空，时间复杂度是 O(1)。

空间复杂度：O(n)O(n)，其中 nn 是栈内的元素。需要使用一个队列存储栈内的元素。

• LeetCode (opens new window)