栈和队列的相互实现

不作声

发布于 2021-01-06 18:39:50

3350

发布于 2021-01-06 18:39:50

文章被收录于专栏：M不作声M不作声

栈和队列都可以使用数组实现，所以栈和队列都可以相互实现。

使用两个栈实现队列

队列的特性是先进先出，一端添加另一端删除；而栈的特性是先进后出，且只能在一端添加或删除数据。

很明显，两个栈，栈底相接，两个栈顶向外，这样就有了两个可以操作数据的端。队列先进先出的特性，我们可以通过「两次进栈出栈」实现，一次进出栈可以实现倒序，两次可以将顺序再恢复。

双栈实现队列

代码实现

var CQueue = function () {
  this.topStack = []
  this.tailStack = [];
}

CQueue.prototype.appendTail = function(value) {
  this.tailStack.push(value)
}

CQueue.prototype.deleteHead = function() {
  let top = this.topStack
  let tail = this.tailStack
  
  if (tail.isEmpty() && top.isEmpty()) return -1
  if (tail.isEmpty()){
    while(!top.isEmpty()) {
      tail.push(top.pop())
    }
  }
  let item = tail.pop()
  return item
}

双栈实现队列，当删除栈中为空时，在队列的内部还要经过额外的数据转移，删除操作的时间复杂度为O(n)；当删除栈中不为空时，删除操作的事件复杂度就是O(1)。总的来说，删除操作的时间复杂度是小于O(n)的，添加操作的时间复杂度一直为O(1)。

使用两个队列实现栈

使用队列实现栈先进后出的思路如下：

创建两个队列，一个是存储数据的队列Q1，另一个辅助队列Q2。
插入数据时，先将数据插入到Q2中，再将Q1中所有的数据出队，再入队到Q2中。保证新插入的数据总是在队头（栈顶），且只有一个数据栈有数据，而辅助栈总是空的。
交换Q1和Q2。
删除数据时，直接从数据栈的队头删除数据。

如图，左边的队列为Q1，右边的队列为Q2，插入过程如下：

栈的插入过程

代码实现：

var MyStack = function() {
  this.q1 = []
  this.q2 = []
}

MyStack.prototype.push = function(item) {
  this.q2.push(item)
  while(this.q1.length > 0) {
    this.q2.push(this.p1.shift())
  }
  this.q1 = this.q2
  this.q2 = []
}

MyStack.prototype.pop = function() {
  if(this.q1.length == 0) return null
  return this.q1.shift()
}

MyStack.prototype.isEmpty = function() {
  return this.q1.length == 0
}

MyStack.prototype.top = function() {
  return this.q1[0]
}

双队列实现栈，每次插入一个元素都要移动一次数据，移动数据总次数大约为(1+2+3+…+n-1/n)每次，所以时间复杂度为O(n-1)，删除操作的时间复杂度一直为O(1)。空间复杂度使用了两个队列，每个队列都要能容纳n个元素，所以空间复杂度为O(2n)。

比较

用栈实现队列时，「两个栈中都存储数据」；用队列实现栈时，「只有一个队列中存储数据」。
用栈实现队列时，「插入数据可直接操作，删除栈中为空时才转移数据」；在用队列实现时，每次「插入数据时进行数据转移，删除数据可直接删除」。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-12-31，如有侵权请联系 cloudcommunity@tencent.com 删除

队列

本文分享自大前端合集微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

队列

登录后参与评论

0 条评论

热度