队列
-
是一种特殊的线性表,它只允许在表的前端进行删除操作,而在表的后端进行插入操作,和栈一样,队列是一种操作受限制的线性表。(特点:先进先出)
-
题目:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
-
你的实现应该支持如下操作:
- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
-
示例:
rcularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false,队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
来源:力扣(LeetCode)
- 直接上代码
ES5 版
function MyCircularQueue (k) {
// 保存长度 为 k 的数据结构
this.list = Array(k)
// 对首的指针
this.front = 0
// 队尾的指针
this.rear = 0
// 对列的长度
this.max = k
}
// 向循环队列插入一个元素。如果成功插入则返回真。否则返回 false
MyCircularQueue.prototype.enQueue = function(value) {
if (this.isFull()) {
return false
} else {
this.list[this.rear] = value
// 把指针 + 1, % 因为指针到末尾后,要在重新指回到第一个
this.rear = (this.rear + 1) % this.max
return true
}
}
// deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
MyCircularQueue.prototype.deQueue = function() {
// 取出第一个元素
const f = this.list[this.front]
// 删除元素
this.list[this.front] = ''
// 同样的道理 front 的指针 + 1
this.front = (this.front + 1) % this.max
// 返回元素
return !!f
}
// Front: 从队首获取元素。如果队列为空,返回 -1 。
MyCircularQueue.prototype.Front = function() {
return this.list[this.front] ? this.list[this.front] : -1
}
// Rear: 获取队尾元素。如果队列为空,返回 -1 。
MyCircularQueue.prototype.Rear = function() {
if (this.isEmpty()) {
return -1
} else {
// 获取 index
const rear = this.rear - 1
// 判断当前的 index
const cur = rear < 0 ? this.max - 1 : rear
return this.list[cur]
}
}
// isEmpty(): 检查循环队列是否为空。
MyCircularQueue.prototype.isEmpty = function() {
// 两个指针相同,并且元素为空
return this.front === this.rear && !this.list[this.front]
}
// isFull(): 检查循环队列是否已满。
MyCircularQueue.prototype.isFull = function() {
return this.front === this.rear && !!this.list[this.front]
}
const circularQueue = new MyCircularQueue1(3)
console.log(circularQueue.enQueue(1)) // true
console.log(circularQueue.enQueue(2)) // true
console.log(circularQueue.enQueue(3)) // true
console.log(circularQueue.enQueue(4)) // false
console.log(circularQueue.Rear(4)) // 3
console.log(circularQueue.Front(4)) // true
console.log(circularQueue.deQueue(4)) // true
console.log(circularQueue.enQueue(4)) // true
console.log(circularQueue.Rear(4)) // 4
ES6 版
class MyCircularQueue1 {
constructor(k) {
this.list = Array(k)
this.front = 0
this.rear = 0
this.max = k
}
enQueue(value) {
if (this.isFull()) {
return false
} else {
this.list[this.rear] = value
this.rear = (this.rear + 1) % this.max
return true
}
}
deQueue() {
const f = this.list[this.front]
this.list[this.front] = ''
this.front = (this.front + 1) % this.max
return !!f
}
Front() {
return this.list[this.front] ? this.list[this.front] : -1
}
Rear() {
if (this.isEmpty()) {
return -1
} else {
// 获取 index
const rear = this.rear - 1
// 判断当前的 index
const cur = rear < 0 ? this.max - 1 : rear
return this.list[cur]
}
}
isEmpty() {
return this.front === this.rear && !this.list[this.front]
}
isFull() {
return this.front === this.rear && !!this.list[this.front]
}
}
const circularQueue1 = new MyCircularQueue1(3)
console.log(circularQueue1.enQueue(1)) // true
console.log(circularQueue1.enQueue(2)) // true
console.log(circularQueue1.enQueue(3)) // true
console.log(circularQueue1.enQueue(4)) // false
console.log(circularQueue1.Rear(4)) // 3
console.log(circularQueue1.Front(4)) // true
console.log(circularQueue1.deQueue(4)) // true
console.log(circularQueue1.enQueue(4)) // true
console.log(circularQueue1.Rear(4)) // 4
网友评论