转载

数据结构基础温故-3.队列

在日常生活中，队列的例子比比皆是，例如在车展排队买票，排在队头的处理完离开，后来的必须在队尾排队等候。在程序设计中，队列也有着广泛的应用，例如计算机的任务调度系统、为了削减高峰时期订单请求的消息队列等等。与栈类似，队列也是属于操作受限的线性表，不过队列是只允许在一端进行插入，在另一端进行删除。在其他数据结构如树的一些基本操作中（比如树的广度优先遍历）也需要借助队列来实现，因此这里我们来看看队列。

一、队列的概念及操作

1.1 队列的基本特征

数据结构基础温故-3.队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。它是一种 先进先出 （First In First Out）的线性表，简称 FIFO 。允许插入的一端称为队尾，允许删除的一端称为队头。

1.2 队列的基本操作

数据结构基础温故-3.队列

（1）入队（Enqueue）：将一个数据元素插入队尾；

（2）出队（Dequeue）：读取队头节点数据并删除该节点；

二、队列的基本实现

既然队列也属于特殊的线性表，那么其实现也会有两种形式：顺序存储结构和链式存储结构。首先，对于Queue，我们希望能够提供以下几个方法供调用：

Queue<T>()	创建一个空的队列
void Enqueue(T s)	往队列中添加一个新的元素
T Dequeue()	移除队列中最早添加的元素
bool IsEmpty()	队列是否为空
int Size()	队列中元素的个数

2.1 队列的顺序存储实现

与Stack不同，在队列中我们需要定义一个head队头“指针”和tail队尾“指针”，当新元素入队时tail+1，当老元素出队时head+1。下面重点来看看Enqueue和Dequeue两个方法的代码实现。

（1）入队：Enqueue

public void EnQueue(T item) {  if (Size == items.Length)  {   // 扩大数组容量   ResizeCapacity(items.Length * 2);  }  items[tail] = item;  tail++;  size++; }

新元素入队后，tail队尾指针向前移动指向下一个新元素要插入的位置；这里仍然模仿.NET中的实现，在数组容量不足时及时进行扩容以容纳新元素入队。

（2）出队：Dequeue

public T DeQueue() {  if (Size == 0)  {   return default(T);  }  T item = items[head];  items[head] = default(T);  head++;  if (head > 0 && Size == items.Length / 4)  {   // 缩小数组容量   ResizeCapacity(items.Length / 2);  }  size--;  return item; }

在对老元素进行出队操作时，首先取得head指针所指向的老元素，然后将head指针向前移动一位指向下一个将出队的老元素。这里将要出队的元素所在数组中的位置重置为默认值。最后判断容量是否过小，如果是则进行数组容量的缩小。

下面是完整的队列模拟实现代码，仅供参考，这里就不再做基本功能测试了，有兴趣的读者可以自行测试：

/// <summary> /// 基于数组的队列实现 /// </summary> /// <typeparam name="T">类型</typeparam> public class MyArrayQueue<T> {  private T[] items;  private int size;  private int head;  private int tail;  public MyArrayQueue(int capacity)  {   this.items = new T[capacity];   this.size = 0;   this.head = this.tail = 0;  }  /// <summary>  /// 入队  /// </summary>  /// <param name="item">入队元素</param>  public void EnQueue(T item)  {   if (Size == items.Length)   {    // 扩大数组容量    ResizeCapacity(items.Length * 2);   }   items[tail] = item;   tail++;   size++;  }  /// <summary>v   /// 出队  /// </summary>  /// <returns>出队元素</returns>  public T DeQueue()  {   if (Size == 0)   {    return default(T);   }   T item = items[head];   items[head] = default(T);   head++;   if (head > 0 && Size == items.Length / 4)   {    // 缩小数组容量    ResizeCapacity(items.Length / 2);   }   size--;   return item;  }  /// <summary>  /// 重置数组大小  /// </summary>  /// <param name="newCapacity">新的容量</param>  private void ResizeCapacity(int newCapacity)  {   T[] newItems = new T[newCapacity];   int index = 0;   if (newCapacity > items.Length)   {    for (int i = 0; i < items.Length; i++)    {     newItems[index++] = items[i];    }   }   else   {    for (int i = 0; i < items.Length; i++)    {     if (!items[i].Equals(default(T)))     {      newItems[index++] = items[i];     }    }    head = tail = 0;   }   items = newItems;  }  /// <summary>  /// 栈是否为空  /// </summary>  /// <returns>true/false</returns>  public bool IsEmpty()  {   return this.size == 0;  }  /// <summary>  /// 栈中节点个数  /// </summary>  public int Size  {   get   {    return this.size;   }  } }

View Code

2.2 队列的链式存储实现

跟Stack链式存储结构不同，在Queue链式存储结构中需要设置两个节点：一个head队头节点，一个tail队尾节点。现在我们来看看在链式存储结构中，如何实现Enqueue与Dequeue两个方法。

（1）入队：Enqueue

public void EnQueue(T item) {  Node<T> oldLastNode = tail;  tail = new Node<T>();  tail.Item = item;  if(IsEmpty())  {   head = tail;  }  else  {   oldLastNode.Next = tail;  }  size++; }

入队操作就是在链表的末尾插入一个新节点，将原来的尾节点的Next指针指向新节点。

（2）出队：Dequeue

public T DeQueue() {  T result = head.Item;  head = head.Next;  size--;  if(IsEmpty())  {   tail = null;  }  return result; }

出队操作本质就是返回链表中的第一个元素即头结点，这里可以考虑到如果队列为空，将tail和head设为null以加快垃圾回收。

模拟的队列链式存储结构的完整代码如下，这里就不再做基本功能测试了，有兴趣的读者可以自行测试：

/// <summary> /// 基于链表的队列节点 /// </summary> /// <typeparam name="T"></typeparam> public class Node<T> {  public T Item { get; set; }  public Node<T> Next { get; set; }  public Node(T item)  {   this.Item = item;  }  public Node()  { } } /// <summary> /// 基于链表的队列实现 /// </summary> /// <typeparam name="T">类型</typeparam> public class MyLinkQueue<T> {  private Node<T> head;  private Node<T> tail;  private int size;  public MyLinkQueue()  {   this.head = null;   this.tail = null;   this.size = 0;  }  /// <summary>  /// 入队操作  /// </summary>  /// <param name="node">节点元素</param>  public void EnQueue(T item)  {   Node<T> oldLastNode = tail;   tail = new Node<T>();   tail.Item = item;   if(IsEmpty())   {    head = tail;   }   else   {    oldLastNode.Next = tail;   }   size++;  }  /// <summary>  /// 出队操作  /// </summary>  /// <returns>出队元素</returns>  public T DeQueue()  {   T result = head.Item;   head = head.Next;   size--;   if(IsEmpty())   {    tail = null;   }   return result;  }  /// <summary>  /// 是否为空队列  /// </summary>  /// <returns>true/false</returns>  public bool IsEmpty()  {   return this.size == 0;  }  /// <summary>  /// 队列中节点个数  /// </summary>  public int Size  {   get   {    return this.size;   }  } }

View Code

2.3 循环队列

首先，我们来看看下面的情景，在数组容量固定的情况下，队头指针之前有空闲的位置，而队尾指针却已经指向了末尾，这时再插入一个元素时，队尾指针会指向哪里？

数据结构基础温故-3.队列

图1

从图中可以看出，目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“ 假溢出 ”。现实当中，你上了公交车，发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做？立马下车，并对自己说，后面没座了，我等下一辆？没有这么笨的人，前面有座位，当然也是可以坐的，除非坐满了，才会考虑下一辆。

所以解决假溢出的办法就是后面满了，就再从头开始，也就是 头尾相接的循环 。我们把队列的这种头尾相接的顺序存储结构称为 循环队列 。在循环队列中需要注意的几个问题是：

（1）入队与出队的索引位置如何确定？

这里我们可以借助%运算对head和tail两个指针进行位置确定，实现方式如下所示：

// 移动队尾指针 tail = (tail + 1) % items.Length; // 移动队头指针 head = (head + 1) % items.Length;

（2）在队列容量固定时如何判断队列空还是队列满？

①设置一个标志变量flag，当head==tail，且flag=0时为队列空，当head==tail，且flag=1时为队列满。

②当队列空时，条件就是head=tail，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。如下图所示：

数据结构基础温故-3.队列

图2

从上图可以看出，由于tail可能比head大，也可能比head小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是 (tail+1)%QueueSize==head （ 取模“%”的目的就是为了整合tail与head大小为一个问题 ）。比如上面这个例子，QueueSize=5，图中的左边front=0，而rear=4，(4+1)%5=0，所以此时队列满。再比如图中的右边，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。

（3）由于tail可能比head大，也可能比head小，那么队列的长度如何计算？

当tail>head时，此时队列的长度为tail-head。但当tail<head时，队列长度分为两段，一段是QueueSize-head，另一段是0+tail，加在一起，队列长度为tail-head+QueueSize。因此通用的计算队列长度公式为： (tail-head+QueueSize)%QueueSize 。

三、队列的应用场景

队列在实际开发中应用得非常广泛，这里来看看在互联网系统中常见的一个应用场景： 消息队列 。“ 消息 ”是在两台计算机间传送的数据单位。消息可以非常简单，例如只包含文本字符串；也可以更复杂，可能包含嵌入对象。消息被发送到队列中，“ 消息队列 ”是在消息的传输过程中保存消息的容器。

在目前广泛的Web应用中，都会出现一种场景：在某一个时刻，网站会迎来一个用户请求的高峰期（比如：淘宝的双十一购物狂欢节，12306的春运抢票节等），一般的设计中，用户的请求都会被直接写入数据库或文件中，在高并发的情形下会对数据库服务器或文件服务器造成巨大的压力，同时呢，也使响应延迟加剧。这也说明了，为什么我们当时那么地抱怨和吐槽这些网站的响应速度了。当时2011年的京东图书促销，曾一直出现在购物车中点击“购买”按钮后一直是“ Service is too busy ”，其实就是因为当时的 并发访问量过大，超过了系统的最大负载能力 。当然，后边，刘强东临时购买了不少服务器进行扩展以求增强处理并发请求的能力，还请了信息部的人员“喝茶”，现在京东已经是超大型的网上商城了，我也有同学在京东成都研究院工作了。

数据结构基础温故-3.队列

从京东当年的“Service is too busy”不难看出，高并发的用户请求是网站成长过程中必不可少的过程，也是一个必须要解决的难题。在众多的实践当中，除了增加服务器数量配置服务器集群实现伸缩性架构设计之外，异步操作也被广泛采用。而异步操作中最核心的就是使用 消息队列 ，通过消息队列，将短时间高并发产生的事务消息存储在消息队列中，从而削平高峰期的并发事务，改善网站系统的性能。在京东之类的电子商务网站促销活动中，合理地使用消息队列，可以有效地抵御促销活动刚开始就开始大量涌入的订单对系统造成的冲击。

数据结构基础温故-3.队列

四、.NET中的Queue<T>

虽然队列有顺序存储和链式存储两种存储方式，但在.NET中使用的是顺序存储，它所对应的集合类是System.Collections.Queue与System.Collections.Generic.Queue<T>，两者结构相同，不同之处仅在于前者是非泛型版本，后者是泛型版本的队列。它们都属于循环队列，这里我们通过Reflector来重点看看泛型版本的实现。

数据结构基础温故-3.队列

我们来看看在.NET中的Queue<T>是如何实现入队和出队操作的。首先来看看入队Enqueue方法：

public void Enqueue(T item) {  if (this._size == this._array.Length)  {   int capacity = (this._array.Length * 200) / 100;   if (capacity < (this._array.Length + 4))   {    capacity = this._array.Length + 4;   }   this.SetCapacity(capacity);  }  this._array[this._tail] = item;  this._tail = (this._tail + 1) % this._array.Length;  this._size++;  this._version++; }

可以看出，与我们之前所实现的Enqueue方法类似，首先判断了队列是否满了，如果满了则进行扩容，不同之处在我们是直接*2倍，这里是在原有容量基础上+4。由于是循环队列，对tail指针使用了%运算来确定下一个入队位置。

我们再来看看Dequeue方法时怎么实现的：

public T Dequeue() {  if (this._size == 0)  {   ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);  }  T local = this._array[this._head];  this._array[this._head] = default(T);  this._head = (this._head + 1) % this._array.Length;  this._size--;  this._version++;  return local; }