- 源码地址请点击此处
队列也是一种操作受限的线性表，和栈只能在一端操作不同，队列可以在两端进行操作，这两端分别叫做队首和队尾。
队列的基本结构如下：
队列的基本结构
队列是一种先进先出（FIFO，First In First Out）的数据结构，因此，如果将元素添加到队列中的顺序为 a1，a2，...，an，那么将元素从队列中移除的顺序就是 an，...，a2，a1。
关于队列有以下几个基本概念：
- 队首
将元素从队列中移出时，需要在队首进行操作。 - 队尾
向队列中添加元素时，需要在队尾操作。 - 入队
向队列中添加元素的操作叫做入队。 - 出队
从队列中移出元素的操作叫做出队。 - 空队列
队列中没有任何元素时，这个队列就叫做空队列。
队列的代码实现
下面是队列的代码实现，在 JavaScript 中实现队列需要借助数组，其中入队操作需要借助数组的 push() 方法，出队操作需要借助数组的 shift() 方法。
接口定义
interface IQueue<T>{
// 获取队列的长度
size():number;
// 入队操作
enqueue(ele:T):T;
// 出队操作
dequeue():T;
// 清除队列
clear():void;
// 获取队列的第一个元素
front():T;
// 获取队列的最后一个元素
end():T;
// 判断队列是否为空
isEmpty():boolean;
// 获取队列中的所有元素
toString():T[];
}
接口实现
class Queue<T> implements IQueue<T>{
private _size:number = 0;
private dataStore:T[] = [];
size():number{
return this._size;
}
enqueue(ele:T):T{
// 向队列中添加元素，借助数组的 push 方法
this.dataStore.push(ele);
this._size++;
return ele;
}
dequeue():T{
// 从队列中移除元素，借助数组的 shift 方法
const ele:T = this.dataStore.shift();
this._size--;
return ele;
}
clear():void{
// 清除队列
this.dataStore = [];
// 重置队列长度
this._size = 0;
}
front():T{
const index:number = 0;
return this.dataStore[index];
}
end():T{
const index:number = this._size - 1;
return this.dataStore[index];
}
isEmpty():boolean{
return !this._size;
}
toString():T[]{
// 返回队列的元素信息
return this.dataStore;
}
}
优先队列
优先队列是队列的一种衍生结构，普通的队列在出队时遵循 FIFO 的原则，而优先队列在出队时，会根据元素的优先级出队，优先级最高元素最先出队，优先级最低的元素最后出队。除此之外，优先队列和普通的队列没有任何差异。
要实现优先队列，我们在向队列中添加元素时，需要指定优先级，因此我们还需要一个 QueueElement 类。
下面是 IQueueElement 接口和 QueueElement 类的代码实现：
interface IQueueElement<T>{
priority:number;
data:T;
}
class QueueElement<T> implements IQueueElement<T>{
priority:number = 1;
data:T = null;
constructor(data:T,priority:number){
this.data = data;
this.priority = priority;
}
}
定义 IPriorityQueue 接口和 PriorityQueue 类，IPriorityQueue 接口的定义和原始的 IQueue 接口定义类似，只是需要修改下接口的泛型约束。PriorityQueue 类在实现时需要修改入队方法 enqueue()，其他方法和原始的 Queue 类中的定义类似，只需要修改下泛型约束。代码如下：
interface IPriorityQueue<T>{
// 获取队列的长度
size():number;
// 入队操作
enqueue(ele:IQueueElement<T>):IQueueElement<T>;
// 出队操作
dequeue():IQueueElement<T>;
// 清除队列
clear():void;
// 获取队列的第一个元素
front():IQueueElement<T>;
// 获取队列的最后一个元素
end():IQueueElement<T>;
// 判断队列是否为空
isEmpty():boolean;
// 获取队列中的所有元素
toString():IQueueElement<T>[];
}
class PriorityQueue<T> implements IPriorityQueue<T>{
private _size:number = 0;
private dataStore:IQueueElement<T>[] = [];
size():number{
return this._size;
}
enqueue(ele:IQueueElement<T>):IQueueElement<T>{
// 向队列中添加元素，借助数组的 push 方法
this.dataStore.push(ele)
// 对队列中的元素进行排序
this.dataStore.sort((ele1,ele2) => ele1.priority - ele2.priority);
this._size++;
return ele;
}
dequeue():IQueueElement<T>{
// 从队列中移除元素，借助数组的 shift 方法
const ele:IQueueElement<T> = this.dataStore.shift();
this._size--;
return ele;
}
clear():void{
// 清除队列
this.dataStore = [];
// 重置队列长度
this._size = 0;
}
front():IQueueElement<T>{
const index:number = 0;
return this.dataStore[index];
}
end():IQueueElement<T>{
const index:number = this._size - 1;
return this.dataStore[index];
}
isEmpty():boolean{
return !this._size;
}
toString():IQueueElement<T>[]{
// 返回队列的元素信息
return this.dataStore;
}
}
简单测试一下：
const queue = new PriorityQueue<IQueueElement>();
queue.enqueue(new QueueElement("MIKE",2));
queue.enqueue(new QueueElement("JACK",4));
queue.enqueue(new QueueElement("MARRY",1));
queue.enqueue(new QueueElement("PENNY",3));
for(let i = 0,len = queue.size();i < len; i ++){
console.log(queue.dequeue())
}
输出结果：
QueueElement { priority: 1, data: 'MARRY' }
QueueElement { priority: 2, data: 'MIKE' }
QueueElement { priority: 3, data: 'PENNY' }
QueueElement { priority: 4, data: 'JACK' }
循环队列
循环队列是队列的另一种衍生结构，它和普通队列的区别在于：普通队列中的元素在出队后，会从队列中移除，而循环队列中的元素在出队后，会再进行一次入队操作，将该元素添加到队尾，以此循环往复。
在实现循环队列时，需要修改原始 Queue 类的出队方法 dequeue()：
...
dequeue():T{
// 从队列中移除元素，借助数组的 shift 方法
const ele:T = this.dataStore.shift();
// 将移除的元素再次添加到队列中
this.enqueue(ele);
return ele;
}
...
简单测试一下：
const queue = new CycleQueue<string>();
queue.enqueue("A")
queue.enqueue("B")
queue.enqueue("C")
queue.enqueue("D")
setInterval(()=>{
queue.dequeue();
console.log(queue.toString())
},1000);
输出结果：
[ 'B', 'C', 'D', 'A' ]
[ 'C', 'D', 'A', 'B' ]
[ 'D', 'A', 'B', 'C' ]
[ 'A', 'B', 'C', 'D' ]
[ 'B', 'C', 'D', 'A' ]
[ 'C', 'D', 'A', 'B' ]
[ 'D', 'A', 'B', 'C' ]
...
可见，循环队列的特点是出队操作不会使队列中的元素减少。
完。
网友评论