队列的定义

在现实生活中，像队列的例子就是我们平时的排队买票，先来的先买，后来的只能站在末尾，不允许插队。

队列的特征是，先进先出。跟栈一样，队列也是一种操作受限的线性表数据结构。

队列的基本操作：

  • 入列：在队列尾部添加一个元素

  • 出列：从队列头部移除一个元素

09 - 队列：队列在线程池等有限资源池中的应用 - 图1

队列的实现

  1. //基于数组实现的队列
  2. function Queue(){
  3.     var items = [];
  5.     //入队
  6.     this.enqueue = function(elem){
  7.         items.push(elem);
  8.     }
  10.     //出队
  11.     this.dequeue = function(){
  12.         return items.shift();
  13.     }
  15.     //返回队列最前面的项
  16.     this.front = function(){
  17.         return items[0];
  18.     }
  20.     //队列是否为空
  21.     this.isEmpty  = function(){
  22.         return items.length == 0;
  23.     }
  25.     //队列的长度
  26.     this.size = function(){
  27.         return items.length;
  28.     }
  30.     //打印队列
  31.     this.print = function(){
  32.         console.log(items.toString());
  33.     }
  34. }

基于链表实现的队列：https://github.com/wangzheng0822/algo/blob/master/javascript/09_queue/QueueBasedOnLinkedList.js

队列的类型

循环队列

循环队列其实是将队列的头尾相连，形成一个环。