image.png
单向循环队列
可以使用数组来实现队列，并且各项接口也可以优化到 O(1) 的时间复杂度--这就是循环队列
// 环形队列 使用动态数组来实现队列 实现复杂度O(1)
const DEFAULT_CAPATICY = 10;
class CircleQueue {
constructor(capaticy = DEFAULT_CAPATICY) {
this.elements = new Array(capaticy);
this.size = 0;
// 头部指针
this.front = 0;
}
// 清空队列
clear() {
this.elements = new Array(DEFAULT_CAPATICY);
this.size = 0;
this.front = 0;
}
// 判断队列是否为空
isEmpty() {
return this.size === 0;
}
// 获取队列size
getSize() {
return this.size;
}
// 入队列 入队列时不需要置front位置 复杂度O(1) 因为是循环的，所以不需要挪位置，使用front头部指针来定位
enQueue(ele) {
this.expandCapacity(this.size + 1);
// 入队列是从最后入队列，不需要重置front的位置，就是没有元素的时候，只要在删除的时候重置front即可。
this.elements[this.getRealIndex(this.size)] = ele;
this.size++
}
// 出队列 复杂度 O(1)
deQueue() {
// 缓存头部元素
let old = this.elements[this.front];
// 删除头部元素
this.elements[this.front] = null;
// 重置头部指针到下一位
this.front = this.getRealIndex(1);
this.size--;
return old;
}
// 获取队列头 复杂度 O(1)
getFront() {
return this.elements[this.front];
}
// 获取真正的index下标，因为循环下标会有差异
getRealIndex(index) {
let real = this.front + index;
let capaticy = this.elements.length;
return real % capaticy;
}
// 扩容 -- 如果已使用的容量已经大于等于容量需要扩容
expandCapacity(capaticy) {
let oldCapaticy = this.elements.length;
if (capaticy <= oldCapaticy) return false;
let newCapaticy = oldCapaticy + (oldCapaticy >> 1);
let elements = new Array(newCapaticy);
for (let i = 0; i < this.size; i++) {
elements[i] = this.elements[this.getRealIndex(i)];
}
this.elements = elements;
this.front = 0;
console.log(`${oldCapaticy} -->扩容为--> ${newCapaticy}`);
}
toString() {
return this.elements;
}
}
循环双端队列
可以进行两端添加、删除操作的循环队列
// 双端环形队列
const DEFAULT_CAPATICY = 10;
class CircleDeQueue {
constructor(capaticy = DEFAULT_CAPATICY) {
this.elements = new Array(capaticy);
this.size = 0;
this.front = 0;
}
// 清空队列
clear() {
this.elements = new Array(DEFAULT_CAPATICY);
this.size = 0;
this.front = 0;
}
// 判断队列是否为空
isEmpty() {
return this.size === 0;
}
// 获取队列size
getSize() {
return this.size;
}
// 从头部插入元素 复杂度O(1)
enQueueFront(ele) {
this.expandCapacity(this.size + 1);
// 获取头部前一个元素的下标 重置给头部指针front，再赋值
this.elements[this.front = this.getRealIndex(-1)] = ele;
this.size++
}
// 从尾部插入元素 复杂度 O(1)
enQueueRear(ele) {
this.expandCapacity(this.size + 1);
// 获取尾部下一个插入位置的下标，再赋值，此时由于头部没有变化，所以不需要改变头部指针front，就是没有元素，front仍然是0或者之前的front位置，还是对的
this.elements[this.getRealIndex(this.size)] = ele;
this.size++
}
// 从头部出队列 复杂度 O(1)
deQueueFront() {
// 获取头部元素
let old = this.elements[this.front];
// 删除头部元素
this.elements[this.front] = null;
// 重置头部指针为下一个元素
this.front = this.getRealIndex(1);
this.size--;
return old;
}
// 从尾部出队列， 复杂度 O(1)
deQueueRear() {
// 获取最后一个元素
let realIndex = this.getRealIndex(this.size - 1);
let old = this.elements[realIndex];
// 删除最后一个元素，此时不需要更新头部指针，因为头部没有改变，就是如果剩一个元素时，删除后front仍然是之前的front位置，下次插入仍然插入在这个头部位置。
this.elements[realIndex] = null;
this.size--;
return old;
}
// 获取队列头 复杂度 O(1)
getFront() {
return this.elements[this.front];
}
// 获取队列尾 复杂度 O(1)
getRear() {
return this.elements[this.getRealIndex(this.size - 1)]
}
// 获取真实的下标，支持负数
getRealIndex(index) {
let real = this.front + index;
let capaticy = this.elements.length;
return (real < 0 ? capaticy + real : real) % capaticy;
}
// 扩容 -- 如果已使用的容量已经大于等于容量需要扩容
expandCapacity(capaticy) {
let oldCapaticy = this.elements.length;
if (capaticy <= oldCapaticy) return false;
let newCapaticy = oldCapaticy + (oldCapaticy >> 1);
let elements = new Array(newCapaticy);
for (let i = 0; i < this.size; i++) {
elements[i] = this.elements[this.getRealIndex(i)];
}
this.elements = elements;
this.front = 0;
console.log(`${oldCapaticy} -->扩容为--> ${newCapaticy}`);
}
toString() {
return this.elements;
}
}
网友评论