1. 概念
队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。
队列可由数组或链表实现
队列有单向队列和循环队列
image-20200324173259966.png
2. 单向队列 ( 数组 )
class Queue{
constructor(size){
this.arr = new Array(size);
this.size = size
this.front = -1; //队列头, 指向队列元素的前一个位置
this.rear = -1; //队列尾, 指向队列最后一个数据的位置
};
isFull() {
return this.rear == this.size -1
};
isEmpty() {
return this.rear == this.front
}
add(n) {
if(this.isFull()){
console.log('队列已满,添加失败');
return
}
this.rear ++
this.arr[this.rear] = n
}
get() {
if (this.isEmpty()) {
throw new Error('队列为空,获取失败')
}
this.front ++
let tem = this.arr[this.front]
this.arr[this.front] = undefined
return tem
}
show() {
if (this.isEmpty()) {
console.log('队列为空,获取失败');
return
}
for (let i = 0; i < this.size; i++) {
console.log(this.arr[i]);
}
}
peek() {
if (this.isEmpty()) {
console.log('队列为空,获取失败');
return
}
return this.arr[this.front+1]
}
}
3. 循环队列 ( 数组 )
class SqQueue {
constructor(length) {
this.queue = new Array(length + 1)
// 队头
this.first = 0
// 队尾
this.last = 0
// 当前队列大小
this.size = 0
}
enQueue(item) {
// 判断队尾 + 1 是否为队头
// 如果是就代表需要扩容数组
// % this.queue.length 是为了防止数组越界
if (this.first === (this.last + 1) % this.queue.length) {
this.resize(this.getLength() * 2 + 1)
}
this.queue[this.last] = item
this.size++
this.last = (this.last + 1) % this.queue.length
}
deQueue() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
let r = this.queue[this.first]
this.queue[this.first] = null
this.first = (this.first + 1) % this.queue.length
this.size--
// 判断当前队列大小是否过小
// 为了保证不浪费空间，在队列空间等于总长度四分之一时
// 且不为 2 时缩小总长度为当前的一半
if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
this.resize(this.getLength() / 2)
}
return r
}
getHeader() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
return this.queue[this.first]
}
getLength() {
return this.queue.length - 1
}
isEmpty() {
return this.first === this.last
}
resize(length) {
let q = new Array(length)
for (let i = 0; i < length; i++) {
q[i] = this.queue[(i + this.first) % this.queue.length]
}
this.queue = q
this.first = 0
this.last = this.size
}
}
为什么循环队列空出最后一个
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满；
② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。
