专栏首页BFE.dev前端刷题日记BFE.dev前端刷题#108. 用队列(Queue)实现栈(Stack)
原创

BFE.dev前端刷题#108. 用队列(Queue)实现栈(Stack)

bfe.dev 是一个针对前端的刷题网站,像是前端的LeetCode。该系列文章是我在上面的刷题日记。

题目108

BFE.dev#108 利用队列(Queue)实现栈(Stack)

分析

假设我们有一个队列

[1,2,3,4]
复制代码

如果我们要pop4的话,因为这是一个队列,我们只能把1 dequeue掉。所以为了要得到4,我们必须要把其余的1,2,3给dequeue掉。dequeue掉的元素因为只能用队列,所以需要用第二个队列来装。比如这样:

[4], [1,2,3]
复制代码

现在我们可以取得4了。

[ ] , [1,2,3]
复制代码

这时候我们可以把1,2,3放回去。但是这会让peek()的实现比较麻烦,因为单纯为了peek()也要重复上述操作的话,太浪费了。

为了解决这个问题,我们可以好好利用这两个queue,让其中一个queue始终只有一个元素。比如。

[ ], [ ] 
复制代码

现在添加1,我们需要enqueue即可。

[1], [ ]
复制代码

添加2,enqueue过后,我们保持第一个queue只有一个元素,所以把1放入第二个queue。

[1,2], [ ]
[2], [1]
复制代码

添加3和4的时候,重复相同操作。

[2,3], [1]
[3], [1,2]
[3,4], [1,2]
[4], [1,2,3]
复制代码

现在我们可以dequeue 4了。

[ ], [1,2,3]
复制代码

因为第一个queue成了空,我们可以尝试让第二个queue包含只有一个元素。

[1,2], [3]
复制代码

现在我们可以交换两个queue的地位,这样就变成了和之前完全一样的状态。

[3], [1, 2]
复制代码

OK,综上所述,我们只需要有两个queue。

  • queue1 始终保持只有一个元素(或者初始都为空的状态)
  • queueRest 用来存放其余的元素

来,代码写起来

如下代码完全是按照上述想法的复现,就不再说明了。

class Stack {
  constructor() {
    this.queue1 = new Queue()
    this.queueRest = new Queue()
  }
  
  push(element) {
    this.queue1.enqueue(element)
    this._move()
  }
  
  _move() {
    while (this.queue1.size() > 1) {
      this.queueRest.enqueue(this.queue1.dequeue())
    }
  }
  
  peek() { 
    return this.queue1.peek()
  }
  pop() {
    if (this.queue1.size() === 0) {
      return undefined
    }
    
    const element = this.queue1.dequeue()
    
    // swap if the other queue is not empty
    if (this.queueRest.size() > 0) {
      ;[this.queue1, this.queueRest] = [this.queueRest, this.queue1]
      this._move()
    }
    
    return element
  }
  size() { 
    return this.queue1.size() + this.queueRest.size()
  }
}
复制代码

通过,撒花!

如果你感兴趣可以去BFE.dev 试试 bigfrontend.dev/zh/problem/…

感谢阅读,希望有所帮助,下次见!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何检测JavaScript中的死循环?

    如果我们需要执行用户写的代码,如和避免死循环?我们最近遇到了这个问题,因为写错代码很常见,所以我们进行了一下尝试。

    JSer
  • BFE.dev前端刷题 104. 按层遍历DOM树

    可以看到我们只需要不停的从左边取出元素,然后将其子元素从右边不停放入即可。这用queue实现。

    JSer
  • BFE.dev前端刷题#107. 找到最大的差

    上面的代码显示找到了max,然后再找到min,实际上我们可以合并两次循环为一次,只需要记住当前最大和最小的数即可。

    JSer
  • web-worker 优化惨案纪实

    这是我的第一篇文章,也是我工作一年后的新征程。作者是 2019 年刚刚毕业的,出身贫寒(普通二本)。亲眼目睹校招神仙打架,不幸流落凡尘(我不配)。现在以外包的形...

    winty
  • 在 Vue 对象模块内如何使用 this 对象?

    众所周知,js 中的 this 对象在不同作用域下指代不同的对象实例,并且在以下 4 种场景中经常会“不知所向”:

    程序员LIYI
  • Reactjs开发自制编程语言Monkey的编译器:语法解析

    望月从良
  • 实现红警式的建筑物拖拽生成特效

    望月从良
  • Creator3D新教程,你能射中靶心么?

    长按屏幕,拖动瞄准,放手发射。风向、重力和距离影响最终结果!越靠近中心得分越高!最高分10分!

    张晓衡
  • 使用物理引擎Box2D设计类愤怒小鸟的击球游戏--基本架构设置

    望月从良
  • 上下div高度动态自适应--另类处理方案

         这段时间在工作中遇到一个看似较为棘手的问题。问题描述:查询报表页面分为上下两部分,上部分为条件输入区域,下部分为报表展示区域。客户要求做到默认满屏(但...

    sam dragon

扫码关注云+社区

领取腾讯云代金券