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

BFE.dev前端刷题#13. 利用栈(Stack)创建队列(Queue)

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

题目13

BFE.dev#13 利用栈(Stack)创建队列(Queue)

分析

要从Stack中dequeue一个元素的的话,因为Stack只能pop,所以需要pop掉除了最后一个元素的所有元素。那我们在不断pop的时候,pop掉的元素放哪儿呢?

我们不能使用Array,只能将其放入另外一个stack,像这样。

// 初始状态
[1,2,3,4],  [ ]

// 为了获得1,我们pop掉其余元素到第二个stack
[1], [4,3,2]

// 现在我们dequeue1
[ ], [4,3,2]

复制代码

当得到1过后,我们可以把元素再放回原来的Stack。不过我们可以发现,如果放回去的话再要dequeue的时候,上述过程有得重复一遍,浪费时间。

预期放回去,不如就像现在这样,也就是我们我们有了2个stack,一个用来push,一个用来pop。

pushStack [ ], popStack [4,3,2]

// dequeue的话,直接从popStack里面pop掉2即可
pushStack [ ], popStack [4,3]

// enqueue的话,只需要放入pushStack
pushStack [5], popStack [4,3]
复制代码

popStack空掉的话,如果pushStack还没空,我们就可以按照最开始的方法,把所有元素放到popStack中。

以上就是实现方案了,来写点代码。

代码

代码就比较简答了,完全按照上述逻辑来写的。稍微留意一下_transfer()的作用。

class Queue {
  constructor() {
    this.pushStack = new Stack()
    this.popStack = new Stack()
  }
  _transfer() {
    while(this.pushStack.size() > 0) {
      this.popStack.push(this.pushStack.pop())
    }
  }
  enqueue(element) { 
    this.pushStack.push(element)
  }
  peek() { 
    if (this.size() === 0) return undefined

    if (this.popStack.size() === 0) {
      this._transfer()
    }

    return this.popStack.peek()
  }
  size() { 
    return this.pushStack.size() + this.popStack.size()
  }
  dequeue() {
      if (this.size() === 0) return undefined

    if (this.popStack.size() === 0) {
      this._transfer()
    }

    return this.popStack.pop()
  }
}
复制代码

通过,撒花

有兴趣可以去 bfe.dev 自己试试。

希望能帮助到你,下次见!

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    如果我们要pop4的话,因为这是一个队列,我们只能把1 dequeue掉。所以为了要得到4,我们必须要把其余的1,2,3给dequeue掉。dequeue掉的元...

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

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

    JSer
  • BFE.dev前端刷题64 - Promise reject的时候自动retry

    其中调用fetcher的逻辑可能会被调用很多次,所以把它wrap在一个function以便未来之需。

    JSer
  • CTFweb类型(二十)5位、4位可控字符下的任意命令执行

    网上解释得非常多,这边也讲一下代码其实比较简单跟之前的结构类似,传递的字符串小于5位就能够去执行。我们如何get shell,思路比较清晰,像这些都是拼接命令的...

    牛油果
  • Django—视图

    视图负责接受Web请求HttpRequest,进行逻辑处理,返回Web响应HttpResponse给请求者。

    py3study
  • ThinkPHP邮箱验证

    Thinkphp用户注册使用邮箱验证的功能实现! 小伙伴平时在用户注册的时候,是否为邮箱验证的功能所困扰,下面思梦PHP就为大家带来了这个案例! 首先数据表的结...

    思梦php
  • Distanced: 效果优于DADA2和Deblur的α多样性算法

    Link: https://academic.oup.com/bioinformatics/advance-article-abstract/doi/10.10...

    Listenlii-生物信息知识分享
  • 史上最全《知识图谱》2020综述论文,18位作者, 130页pdf

    在本文中,我们对知识图谱进行了全面的介绍,在需要开发多样化、动态、大规模数据收集的场景中,知识图谱最近引起了工业界和学术界的极大关注。在大致介绍之后,我们对用于...

    新智元
  • Java基础:一、复用具体实现(5)

    最简单地复用某个类的方式就是直接使用该类的一个对象,另外一种就是将那个类的一个对象置于某个新的类中。

    桑鱼
  • 这可能是全网最简单的KMP了(上篇)

    KMP 其实已经念念叨叨挺长时间了,一直没写的原因是我觉得自己可能写不好。与其误人子弟,宁可错失良机。毕竟自己懂是一码事,能讲清楚是另一码事。

    程序员小浩

扫码关注云+社区

领取腾讯云代金券