队列
基本概念
只允许在表(线性表)的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。特点：
- 先进先出(FIFO)
- 数组或链表实现
名词解释：
- 入队：在队列中插入一个元素
- 出队：在队列中删除一个元素
- 指针：用两个指针管理，一个队头指针 front，指向队头元素；另一个队尾指针 rear，指向下一个入队元素的存储位置
顺序队列
定义数组，设置两个指针管理。队头指针 front、队尾指针 rear。当元素入队 rear+1，当元素出队 front+1
信息
假溢出：队尾指针指向数组的最后一个位置。但是队列没有填满
真溢出：队尾指针指向数组的最后一个位置。但是队列已经满了
顺序队列实现
class Queue {
constructor(n) {
this.arr = new Array(n);
this.front = 0;
this.rear = 0; // 尾指针指向最后一个元素的下一个位置
}
// 入队
enqueue(val) {
if (this.full()) return;
this.arr[this.rear++] = val;
}
// 出队
dequeue() {
if (this.empty()) return;
this.front++;
}
// 队列是否满了
full() {
return this.rear === this.arr.length;
}
// 队列是否为空
empty() {
return this.rear === this.front;
}
// 队列是否为空
size() {
return this.rear - this.front;
}
}
循坏队列
为了使队列空间能重复使用，把队列空间想象成一个环形空间，环形空间中的存储单元循坏使用。
循坏队列实现
class Queue {
construct(n) {
this.arr = new Array(n);
this.front = this.rear = 0;
this.count = 0;
}
enqueue(val) {
if (this.full()) return;
this.arr[this.rear++] = val;
this.rear = this.rear % this.arr.length;
this.count++;
}
dequeue() {
if (this.empty()) return;
this.front++;
this.front = this.front % this.arr.length;
this.count--;
}
empty() {
return this.count === 0;
}
full() {
return this.count === this.arr.length;
}
size() {
return this.count;
}
}