栈和队列都可以使用数组实现,所以栈和队列都可以相互实现。
队列的特性是先进先出,一端添加另一端删除;而栈的特性是先进后出,且只能在一端添加或删除数据。
很明显,两个栈,栈底相接,两个栈顶向外,这样就有了两个可以操作数据的端。队列先进先出的特性,我们可以通过「两次进栈出栈」实现,一次进出栈可以实现倒序,两次可以将顺序再恢复。
双栈实现队列
代码实现
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,插入过程如下:
栈的插入过程
代码实现:
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)。