数据结构浅析：队列

图片来源:marketwatch.com

黑色星期五快到了，新版的 Microsoft Surface Studio 已经上架（我是 Windows 的忠实粉丝）。我们一起来讨论每一个人最喜欢的购物经历：排队等待。以及一个比较老的数据结构，队列。

队列

队列就是一条线

添加（enqueues）总是添加到线的尾部

移除（dequeues）总是从线的头部开始移除

队列遵循先进先出（FIFO）模式。

使用范例

• 解决同时有多个用户请求服务，比如有3个人几乎同时购买最后一张机票
• 广度优先搜索算法中数据的排列

为了解决第一种使用场景，我们帮助微软创建一个队列数据结构来管理所有的新版 Surface Studio 订购请求。

在开始之前，快速的说明一下 JavaScript 的数组。和栈一样，JavaScript 的数组本身就有队列的功能。

怎么用 JavaScript 的数组来表现队列

Enqueue：向数组的尾部添加：

<pre>

Array.push(someVal)

</pre>

Dequeue：移除数组的第一个元素并将它返回：

<pre>

Array.shift()

</pre>

如果由于你感到叛逆的原因，你也可以添加到数组的头部，然后从尾部开始移除。

Enqueue 向数组的头部添加数据：

<pre>

Array.unshift(someVal)

</pre>

Dequeue 从数组的尾部开始移除数据：

<pre>

Array.pop()

</pre>

也就是说，为了理解透彻，你需要使用 JavaScript 对象重新实现一个队列。

所以你需要为微软做的第一件事情就是创建一个真实的队列，用于存储在他们网站上点击了订购按钮的每一个顾客。

class Queue{
  constructor(){
    this._storage = {};
    this._start = -1; //replicating 0 index used for arrays
    this._end = -1; //replicating 0 index used for arrays
  }
  
  size(){
   return this._end - this._start;
  }
}
let appleQueue = new Queue();

变量名称前面的下划线仅仅是用于说明这是一个私有变量，不可直接访问。

和栈数据结构不一样（它的添加和移除发生在同一端），队列的本质要求我们同时管理其两端。因此，你需要创建 start 变量用于跟踪队列的头，而 end 变量用于跟踪队列的尾。

最后，获取队列大小最简单的方式（不用创建一个不必要的计数器变量）就是跟踪 start 和 end 之间的差。

首先，你应该提供一种方式来将点击了订购按钮的人员添加到队列。你可以通过 enqueue 方法实现：

class Queue{
  constructor(){
    this._storage = {};
    this._start = -1; //replicating 0 index used for arrays
    this._end = -1; //replicating 0 index used for arrays
  }
  
  enqueue(val){
    this._storage[++this._end] = val; 
     
    //++this._end just means increment the end variable first
    //It's equivalent to
    //this._end++   //->
    //this._storage[this._end] = val;
  }
  
  size(){
   return this._end - this._start;
  }
}
let microsoftQueue = new Queue();
microsoftQueue.enqueue("{user: ILoveWindows@gmail.com}")
microsoftQueue.enqueue("{user: cortanaIsMyBestFriend@hotmail.com}")
microsoftQueue.enqueue("{user: InternetExplorer8Fan@outlook.com}")
microsoftQueue.enqueue("{user: IThrowApplesOutMyWindow@yahoo.com}")

很棒！现在你的 microsoftQueue 中存储的内容看起来应该是这样：

{
  0: "{email: ILoveWindows@gmail.com}"
  1: "{email: cortanaIsMyBestFriend@hotmail.com}"
  2: "{email: InternetExplorer8Fan@outlook.com}"
  3: "{email: IThrowApplesOutMyWindow@yahoo.com}"
}

简单的说明一下上面 users （{user: ...}）的表现方式。

当用户在客户端点击订购按钮的时候，他们就会将所有相关的信息发送到处理请求的服务端。当系统之间交换数据时（比如客户端和服务端），最常用的方式就是通过 Ajax 以 JSON（JavaScript Object Notation）形式发送。

这和 JavaScript 对象很相似，因为它仅仅是一个字符串版本的键值对。如果你对 JavaScript 不熟悉，它和字典或者哈希表（我们在后续文章中介绍）很相似。有关 JSON 的更多信息，Andreas Grech 在 Stack Overflow 上有一篇很棒的文章可以参考。

现在回到我们讨论的队列。

得益于你创建的队列。微软现在可以按照交易的先后顺序高效地跟踪所有已经购买 Surface Studio 的顾客。为了保证所有的顾客是按照正确的顺序获得服务，你需要创建一个准确的 dequeue 方法来跟踪所有顾客的顺序，并且在提供服务之后将他们从队列中移除。

class Queue{
  constructor(){
    this._storage = {};
    this._start = -1; //replicating 0 index used for arrays
    this._end = -1; //replicating 0 index used for arrays
  }
  
  enqueue(val){
    this._storage[++this._end] = val; 
  }
  dequeue(){
    if(this._end > this._start){ //check if there are values
      let nextUp = this._storage[++this._start];
      delete this._storage[this._start];
      return nextUp;
    }
  }  
  
  size(){
   return this._end - this._start;
  }
}
let microsoftQueue = new Queue();
microsoftQueue.enqueue("{user: ILoveWindows@gmail.com}")
microsoftQueue.enqueue("{user: cortanaIsMyBestFriend@hotmail.com}")
microsoftQueue.enqueue("{user: InternetExplorer8Fan@outlook.com}")
microsoftQueue.enqueue("{user: IThrowApplesOutMyWindow@yahoo.com}")
//Function to send everyone their Surface Studio!
let sendSurface = recepient => {
   sendTo(recepient);
}
//When your server is ready to handle this queue, execute this:
while(microsoftQueue.size() > 0){
  sendSurface(microsoftQueue.dequeue());
}

好了，现在 microsoftQueue 中等待的每一位都得到了他们的新 Surface Studio。

还有一些快速优化可以使代码工作更合理。

• 1、一旦队列中每一个人都已经获得了服务，你可以重置 start 和 end。你的队列不太可能达到 JavaScript 的最大数，但是为了安全起见还是需要重置。
• 2、由于JavaScript 中 0 被当做 “false” 处理（更多信息可以参考这里），你可以将 “end > start 检查” 用 size 方法替换

dequeue(){
    if(this.size()){ //0 is a falsey value...coerced to return false
      let nextUp = this._storage[++this._start];
      delete this._storage[this._start];
      if(!this.size()){ //Recheck after incrementing (!0 == true)
        this._start = -1;
        this._end = -1; 
      }
      
      return nextUp;
    }
}

就这么多，你已经完成了一个基本的队列实现！

队列方法的时间复杂度分析

再来看一下代码

class Queue{
  constructor(){
    this._storage = {};
    this._start = -1; //replicating 0 index used for arrays
    this._end = -1; //replicating 0 index used for arrays
  }
  
  enqueue(val){
    this._storage[++this._end] = val; 
  }
  dequeue(){
    if(this.size()){ /
      let nextUp = this._storage[++this._start];
      delete this._storage[this._start];
      if(!this.size()){ 
        this._start = -1;
        this._end = -1; 
      }
      
      return nextUp;
    }
  }
  
  size(){
   return this._end - this._start;
  }
}

栈分析时使用的逻辑在这里同样适用：

Enqueue（添加）是O(1)。因为你在总是知道队列的尾部在哪里，你不必在遍历所有元素之后再添加。

Dequeue（删除）是O(1)。同样因为你总是知道头部的位置，所以移除元素时也不需要遍历。

Size是O(1)。因为有 start 和 end 两个变量，所以队列的大小总是已知的。

这里有一点非常重要的需要说明：队列并非意味着无限大小，尽管我们实现的 queue 类 和 JavaScript 的数组在系统内存耗尽前允许你持续添加元素。

一种优化方式是通过使用限制空间的数组来创建循环队列。Damian Gordon 在 Youtube 上提供了非常有用的视频讲解。这对于我们在后续文章中分析哈希表时也非常得有用！

总结

队列：

1、遵循先进先出（FIFO）模式

2、有一个 start 和 end 属性，分别用于跟踪队列的头部和尾部

3、有 enqueue（add） 和dequeue（remove）方法，用于管理队列内容

4、有 size 属性用于跟踪队列的大小

挑战

尝试仅仅使用栈来重新实现队列，小提示，只需要两个栈就可。

本文译自：A Gentle Introduction to Data Structures: How Queues Work