JavaScript基本数据结构：队列基本原理和实现

和栈一样，队列也是线性结构，它有特定的操作和执行顺序，其基本特征是：先进先出（FIFO），一个生活中的例子是：去餐厅排队点餐，在前面的客户优先下单或首先得到服务。其中删除操作和栈不同，栈是先删除最近添加的数据，而队列则是删除最先添加如队列中的数据。

队列的主要操作

队列的主要操作如下：

Enqueuer：添加一个数据到队列的队尾，如果队列已满，则不再进行操作，提示添加数据溢出。

Dequeue：从队列的队头移除数据，如果队列为空，则返回null。

Front/head：获取最早添加到队头的数据。

Rear/tail：获取最新添加到队尾的数据。

队列有哪些应用？

当有任务不需要立即处理的时候，我们可以使用一个队列保存这些任务，以后处理这些任务的顺序为先进先出，其中最明显地需要队列的是BFS广度优先遍历，下面是两个使用队列的例子：

1. 当资源在多个使用者之间共享时，例如CPU调度、磁盘调度。
2. 当数据在两个进程之间异步传输时(数据不一定以与发送相同的速率接收)，例子包括IO缓冲区、管道、文件IO等。

使用数组实现队列

为了实现队列，我们需要跟踪两个索引：front和rear，往队尾添加新数据，从队头将数据出队。如果只是简单增加这两个索引，可能会有问题，front可能会达到数组的末端，解决办法是使用循环的方式，例如当添加新数据的时候，rear递增，如果rear超过数组长度，而数组又未满，让rear跳到数组的前面，如果让rear跳到前面呢？使用取模rear%capacity即可。

下面实现的队列的各个操作的时间复杂度为O(1)。

下面是使用数组实现队列的源码：

// 使用数组实现队列

// 队列声明
function ArrayQueue(capacity){
    if(capacity < 3){
        console.log("capacity is too small.");
        return null;
    }
    this.capacity = capacity;
    this.size = 0;
    this.front = 0;
    this.rear = capacity - 1;
    this.array = new Array(capacity);
}

// 检查队列是否已满
ArrayQueue.prototype.isFull = function(){
    return this.size == this.capacity;
}

// 检查队列是否为空
ArrayQueue.prototype.isEmpty = function(){
    return this.size == 0;
}

// 入队enqueue操作
ArrayQueue.prototype.enqueue = function(value){
    if(this.isFull()){
        console.log("overflow: could not enqueue value.");
        return;
    }
    this.rear = ++this.rear % this.capacity;
    this.array[this.rear] = value;
    this.size++;
}

// 出队dequeue操作
ArrayQueue.prototype.dequeue = function(){
    if(this.isEmpty())
        return null;
    var value = this.array[this.front];
    this.front = ++this.front % this.capacity;
    this.size--;
    return value;
}

// front查看队头的数据
ArrayQueue.prototype.head = function(){
    if(this.isEmpty())
        return null;
    return this.array[this.front];
}

// rear查看最新添加的数据
ArrayQueue.prototype.tail = function(){
    if(this.isEmpty())
        return null;
    return this.array[this.rear];
}

// 调用实例
var queue = new ArrayQueue(10);
for(var i = 0;i < 10;i++)
    queue.enqueue(i * i * i + 9);
console.log(queue.head());
console.log(queue.tail());
var str = "";
while(!queue.isEmpty()){
    str += queue.dequeue() + " ";
}
console.log(str);

使用链表实现队列

上面使用数组实现队列的难点是font和rear位置的设置和变化处理，和使用数组的方式不同，使用链表则不用考虑太多，相对简单很多，也没有容量限制，只需要实现基本的队列的FIFO即可，其中下面实现的各个操作的时间复杂度也是O(1)，下面是使用链表实现队列的完整源码：

// 使用链表实现队列

// 结点
function Node(value){
    this.value = value;
    this.next = null;
}

// 队列声明
function LinkedQueue(){
    this.size = 0;
    this.head = this.tail = null;
}

// 检查队列是否为空
LinkedQueue.prototype.isEmpty = function(){
    return this.size == 0;
}

// 入队操作
LinkedQueue.prototype.enqueue = function(value){
    var node = new Node(value);
    if(this.size == 0){
        this.head = this.tail = node;
        this.size++;
    }
    else{
        this.tail.next = node;
        this.tail = node;
        this.size++;
    }
}

// 出队操作
LinkedQueue.prototype.dequeue = function(){
    if(this.isEmpty())
        return null;
    var head = this.head;
    var value = head.value;
    this.head = head.next;
    head = null;
    this.size--;
    return value;
}

// 获取队头元素
LinkedQueue.prototype.front = function(){
    if(this.isEmpty())
        return null;
    return this.head.value;
}

// 获取队尾元素
LinkedQueue.prototype.rear = function(){
    if(this.isEmpty())
        return null;
    return this.tail.value;
}


// 调用实例
var queue = new LinkedQueue(10);
for(var i = 0;i < 10;i++)
    queue.enqueue(i * i * i + 9);
console.log(queue.front());
console.log(queue.rear());
var str = "";
while(!queue.isEmpty()){
    str += queue.dequeue() + " ";
}
console.log(str);