剑指 Offer 09. 用两个栈实现队列
发布日期:2021-05-12 21:18:21 浏览次数:22 分类:精选文章

本文共 765 字,大约阅读时间需要 2 分钟。

利用两个栈来实现队列的操作,我们可以利用栈的特性来模拟队列的先进先出的特性。以下是实现步骤:

  • 入队操作:将元素加入到入队栈(stackA)。
  • 出队操作
    • 如果出队栈(stackB)不为空,直接弹出栈顶元素。
    • 否则,将入队栈的所有元素倒序移到出队栈(stackB),然后弹出栈顶元素。如果出队栈仍为空,则说明队列为空,返回-1。
  • 这种方法高效且直观,充分利用了栈的先进后出特性来实现队列的先进先出功能。

    以下是优化后的完整代码:

    CQueue = function() {
    this.stackA = [];
    this.stackB = [];
    };
    CQueue.prototype.appendTail = function(value) {
    this.stackA.push(value);
    };
    CQueue.prototype.deleteHead = function() {
    if (this.stackB.length > 0) {
    return this.stackB.pop();
    } else {
    while (this.stackA.length > 0) {
    this.stackB.push(this.stackA.pop());
    }
    if (this.stackB.length === 0) {
    return -1;
    } else {
    return this.stackB.pop();
    }
    }
    };

    这个实现确保了队列操作的高效性,能够在O(1)平均时间复杂度内完成入队和出队操作。

    上一篇:剑指 Offer 10- II. 青蛙跳台阶问题(动态规划思想)
    下一篇:剑指 Offer 07. 重建二叉树

    发表评论

    最新留言

    留言是一种美德,欢迎回访!
    [***.207.175.100]2025年04月08日 18时45分30秒