常用数据结构《三》· 队列
队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时,称为空队列。
刘亚东;曲心慧编.C/C++常用算法手册:中国铁道出版社,2017.09
单链队列的实现
//@ 单链队列的实现
class Queue {
constructor() {
this.queue = [];
}
//* 入队列
enQueue(item) {
this.queue.push(item);
}
//* 出队列
deQueue() {
return this.queue.shift();
}
//* 获取队头
getHeader() {
return this.queue[0];
}
//* 获取队列长度
getLength() {
return this.queue.length;
}
//* 检测是否为空队列
isEmpty() {
return this.getLength() === 0;
}
}
循环队列的实现
因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列结构中,当存储空间的最后一个位置已被使用而再要进入队运算时,只需要存储空间的第一个位置空闲,便可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。
//@ 循环队列的实现
class SqQueue {
constructor(length) {
this.queue = new Array(length + 1);
//* 队头
this.first = 0;
//* 队尾
this.last = 0;
//* 当前队列大小
this.size = 0;
}
//* 入队列
enQueue(item) {
/**
* *队列判满的条件:this.first === (this.last + 1) % this.queue.length
* *如果队列为满就代表需要扩容数组
* *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;
}
}