什么是队列？
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
在现实生活中，最常见的队列例子就是排队。
在JavaScript中，因为JavaScript在浏览器是单线程执行，所以在事件循环中会运用到队列的设计。具体的运用，大家可以仔细看JavaScript事件循环流程。
排队
JavaScript实现队列
队列是一种先进先出的结构，接下来主要实现队列的以下几个方法：
-
enqueue(element): 队首入队 -
dequeue(): 队尾出队 -
peek(): 仅返回队首元素 -
isEmpty(): 队列是否为空 -
size(): 队列长度 -
clear(): 清空队列 -
toString(): 顺序打印队列中数据
class Queue {
constructor() {
this.items = {};
this.lowerCount = 0; // 头指针
this.count = 0; // 尾指针
}
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowerCount];
delete this.items[this.lowerCount];
this.lowerCount++;
return result;
}
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowerCount];
}
isEmpty() {
return this.count - this.lowerCount === 0;
}
size() {
return this.count - this.lowerCount;
}
clear() {
this.items = {};
this.lowerCount = 0;
this.count = 0;
}
toString() {
if (this.isEmpty()) {
return " ";
}
let s = `${this.items[this.lowerCount]}`;
for (let i = this.lowerCount + 1; i < this.count; i++) {
s += `,${this.items[i]}`;
}
return s;
}
}
JavaScript实现双端队列
双端队列与队列的不同点在于，双端队列可以从队列头部和尾部添加或删除数据。双端队列也可以应用于计算机的撤销操作，可以把双端队列看成是对栈的一种扩展。
双端队列
主要实现双端队列的以下几种方法：
-
addFront(element): 从队首添加数据 -
addBack(element): 从队尾添加数据 -
removeFront()： 删除队首数据 -
removeBack(): 删除队尾数据 -
peekFront(): 仅返回队首数据 -
peekBack(): 仅返回队尾数据 -
isEmpty(): 队列是否为空 -
size(): 队列长度 -
toString(): 顺序打印队列
class Dequeue {
constructor() {
this.count = 0; // 队尾指针
this.lowerCount = 0; //队头指针
this.items = {}; // 双端队列对象存储
}
/**
* 存在3种情况
* 1. 队列为空,则调用添加队尾方法
* 2. 队头指针不为0,则队头指针需往前移
* 3. 队头指针为0,队列需整体后移一位
* */
addFront(element) {
if (this.isEmpty()) {
this.addBack(element);
} else if (this.lowerCount > 0) {
this.lowerCount--;
this.items[this.lowerCount] = element;
} else {
// 从后往前复制
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.lowerCount = 0;
this.items[0] = element;
}
}
addBack(element) {
this.items[this.count] = element;
this.count++;
}
removeFront() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowerCount];
delete this.items[this.lowerCount];
this.lowerCount++;
return result;
}
removeBack() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
peekFront() {
return this.items[this.lowerCount];
}
peekBack() {
return this.items[this.count - 1];
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.count - this.lowerCount;
}
toString() {
if (this.isEmpty()) {
return " ";
}
let s = `${this.items[this.lowerCount]}`;
for (let i = this.lowerCount + 1; i < this.count; i++) {
s += `,${this.items[i]}`;
}
return s;
}
}
JavaScript实现循环队列
循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
主要实现循环队列的以下几种方法：
-
CircleQueue(k): 构造器，设置队列长度为 k 。 -
Front: 从队首获取元素。如果队列为空，返回 -1 。 -
Rear: 获取队尾元素。如果队列为空，返回 -1 。 -
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 -
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回被删除元素。 -
isEmpty(): 检查循环队列是否为空。 -
isFull(): 检查循环队列是否已满。
class CircleQueue {
constructor(k) {
if (k === undefined) {
throw "必须传入循环队列长度";
}
this.size = k; // 队列长度
this.front = 0; // 队头指针
this.rear = 0; // 队尾指针
this.items = {}; // 数组存储队列
}
Front() {
if (this.isEmpty()) {
return -1;
}
return this.items[this.front];
}
Rear() {
/**
* 分为3种情况
* 1. 队列为空
* 2. 队尾指针超出
* 3. 队尾指针不超出
**/
if (this.isEmpty()) {
return -1;
}
const val = this.rear - 1 >= 0 ? this.rear - 1 : this.size - 1;
return this.items[val];
}
enQueue(element) {
if (this.isFull()) {
return -1;
}
this.items[this.rear] = element;
this.rear = (this.rear + 1) % this.size;
return true;
}
deQueue() {
if (this.isEmpty()) {
return -1;
}
const result = this.items[this.front];
delete this.items[this.front];
this.front = (this.front + 1) % this.size;
return result;
}
isEmpty() {
return this.front === this.rear && !this.items[this.front];
}
isFull() {
return this.front === this.rear && !!this.items[this.front];
}
toString() {
if (this.isEmpty()) {
return " ";
}
let s = `${this.items[this.front]}`;
for (let i = this.front + 1; i < this.rear; i++) {
s += `,${this.items[i]}`;
}
return s;
}
}
网友评论