数据结构——队列

源码地址请点击此处

队列也是一种操作受限的线性表，和栈只能在一端操作不同，队列可以在两端进行操作，这两端分别叫做队首和队尾。
队列的基本结构如下：

队列的基本结构

队列是一种先进先出（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' ]
...

可见，循环队列的特点是出队操作不会使队列中的元素减少。

完。