JavaScript实现循环队列（非Array.prototype.pop和Array.prototype.shift）

循环队列优点

重用浪费的内存

例: [1,2,3,4] -> deQueue -> [null, 2,3,4] -> deQueue -> [null,null,3,4]

优于数组已满,无法从队尾将新元素入队,因此用循环队列来重新利用被浪费的空间

功能

MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

changeHeadPoint(): 移动头指针。

changeTailPoint(): 移动尾指针。

思路

一般来说,利用Javascript实现队列可用Array.prototype.pop()和Array.prototype.shift()来实现入队和出队,但是为了表现循环队列的优点,即可以重复利用普通队列浪费的空间,此处定义一个空数组,并利用头指针和尾指针的移动来实现循环队列

代码

MyCircularQueue类

var MyCircularQueue = function(k) {
this.queue = new Array(k)
for(let i = 0;i this.queue[i] = null
}
this.head = -1
this.tail = -1
};
MyCircularQueue.prototype.enQueue = function(value) {
if (!this.isFull()) {
// 改变尾指针后入队
this.changeTailPoint()
this.queue[this.tail] = value
return true
} else {
return false
}
};
MyCircularQueue.prototype.deQueue = function() {
if (!this.isEmpty()) {
// 出队后改变头指针
this.queue[this.head] = null
this.changeHeadPoint()
return true
} else {
return false
}
};
MyCircularQueue.prototype.FrOnt= function() {
if(!this.isEmpty()) {
return this.queue[this.head]
} else {
return -1
}
};
MyCircularQueue.prototype.Rear = function() {
if(!this.isEmpty()) {
return this.queue[this.tail]
} else {
return -1
}
};
MyCircularQueue.prototype.isEmpty = function() {
return this.head === -1 && this.tail === -1
};
MyCircularQueue.prototype.isFull = function() {
return this.queue.indexOf(null) === -1
};
MyCircularQueue.prototype.changeHeadPoint = function() {
// 是否剩下一个元素
if(this.head === this.tail) {
this.head = -1
this.tail = -1
} else {
this.head++
// 边界
if(this.head === this.queue.length) {
this.head = 0
}
}
}
MyCircularQueue.prototype.changeTailPoint = function() {
// 空数组入队
if(this.tail === -1 && this.head === -1) {
this.tail++
this.head++
} else {
this.tail++
// 边界
if(this.tail === this.queue.length) {
this.tail = 0
}
}
}
MyCircularQueue.prototype.show = function() {
console.log('queue: ', this.queue)
console.log('front: ', this.head)
console.log('rear: ', this.tail)
}


调试

let queue = new MyCircularQueue(6)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.deQueue()
queue.deQueue()
queue.enQueue(2)
queue.show()


调试结果:

queue: [ 2, null, 2, 2, 2, 2 ]

front: 2

rear: 0