【剑指 offer】用两个栈实现队列

题目

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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 中。如果有增加队尾,直接增加到队尾当中就行。

广告 我要投放

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • Kikkawa
    支持者 订阅者

    虽然看不懂,但是顶帖 666

  • 其他回帖
  • limanting
    作者

    是我哪里写的没描述清楚咩