关于前端:BFEdev前端刷题108-用队列Queue实现栈Stack

35次阅读

共计 1321 个字符,预计需要花费 4 分钟才能阅读完成。

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

题目 108

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

剖析

假如咱们有一个队列

[1,2,3,4]

如果咱们要pop 4 的话,因为这是一个队列,咱们只能把 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 试试 https://bigfrontend.dev/zh/pr…

感激浏览,心愿有所帮忙,下次见!

正文完
 0