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

时间:2020-9-12 作者:admin

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

题目13

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

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前端刷题#13. 利用栈(Stack)创建队列(Queue)

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

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

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。