盒子
盒子
文章目录
  1. 使用两个栈实现队列
  2. 使用两个队列实现栈
  3. 比较

栈和队列的相互实现

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

使用两个栈实现队列

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

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

双栈实现队列

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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,插入过程如下:

栈的插入过程

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)。

比较

  • 用栈实现队列时,两个栈中都存储数据;用队列实现栈时,只有一个队列中存储数据
  • 用栈实现队列时,插入数据可直接操作,删除栈中为空时才转移数据;在用队列实现时,每次插入数据时进行数据转移,删除数据可直接删除
欢迎关注公众号
扫码关注我的微信公众号-大前端合集
  • 微信公众号-大前端合集