JavaScript基本数据结构（队列基本原理和实现） _数据结构和算法

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

文章图片
队列的主要操作队列的主要操作如下：
Enqueuer：添加一个数据到队列的队尾，如果队列已满，则不再进行操作，提示添加数据溢出。
Dequeue：从队列的队头移除数据，如果队列为空，则返回null。
【JavaScript基本数据结构（队列基本原理和实现）】Front/head：获取最早添加到队头的数据。
Rear/tail：获取最新添加到队尾的数据。

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

当资源在多个使用者之间共享时，例如CPU调度、磁盘调度。
当数据在两个进程之间异步传输时(数据不一定以与发送相同的速率接收)，例子包括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 = http://www.srcmini.com/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 = http://www.srcmini.com/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);