limanting 的个人博客

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案 （语言：javascript）

var CQueue = function (init) {
    this.stackTail = init || [];
    this.stackHead = [];

};

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

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
    if (!this.stackTail.length) {
        return -1;
    }
    while (this.stackTail.length !== 0) {
        const member = this.stackTail.pop();
        this.stackHead.push(member);
    }
    const head = this.stackHead.pop();
    while (this.stackHead.length !== 0) {
        const member = this.stackHead.pop();
        this.stackTail.push(member);
    }
    return head;

};

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

思路

因为JavaScript是没有堆栈的概念的，所以这里堆栈用数组来模仿，并且只使用数组的pop和push方法。
取队列尾部很容易，就是push出最后一个就行。取队头的话，就是需要另外一个栈来倒一次，并取出栈底，再导回到原来的栈中。

优化

内存上的优化思路： 数组pop和push的时候，不要用另外的变量再存一次。直接 this.stackTail.push(this.stackHead.pop())；
并注意，两个堆栈都要初始化，如果一开始只有一个 this.stackTail，而在 deleteHead函数 中动态生成 stackHead 的话，不仅增加了内存开销，还会拖慢执行速度。

运行速度上的优化： 我的这个答案中其实做了不必要的动作。我们可以知道，倒入 stackHead堆栈中后，栈底一定是队头，所以我们其实取出队头后不必倒回 stackTail，下一次取队头的时候直接从 stackHead 中取，直到 stackHead取完后再从 stackTail倒入到 stackHead中。如果有增加队尾，直接增加到队尾当中就行。