数据结构与算法 - 队列

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

数据结构与算法 - 队列

在上一篇介绍了栈，栈是一种后进先出的数据结构，本章将要介绍的是队列，队列是先进先出结构，比如取车站排队取票，谁先来的谁先取，新来的只能后取。

可以向队列中插入、删除数据，其专有称呼为“入队”、“出队”：

  • 入队：向队尾添加元素
  • 出队：从队头删除元素

队列的实现

队列的实现可以采用数组或者链表，本文实现基于数组的队列，队列常用的操作包括：入队、出队、获取队头元素。从上图可以看出，一个队列需要两个指针，队头指针指向队列的第一个元素，队尾指针是一个尾后指针，指向最后一个元素的下一个位置。

入队：

1
2
3
4
5
6
7
8
9
10
11
12
public void Enqueue(T item)
{
    if (size == items.Length){
        T[] newArray = new T[items.Length == 0 ? defaultSize : items.Length * 2];
        Array.Copy(items, newArray, items.Length);
        items = newArray;
    }

    items[tail] = item;
    tail++;
    size++;
}

出队：

1
2
3
4
5
6
7
8
9
10
public T Dequeue()
{
    if (size == 0)
        throw new InvalidOperationException("Queue under flow");
    var item = items[head];
    items[head] = default(T);
    head++;
    size--;
    return item;
}

上面代码看起来没上面问题，但是自信分析之后，就会发现，随着不断的插入、删除元素，数组就会不断的扩容，并且数组会随着队头指针的移动，造成数组头部会有一部分空间被闲置。如何利用这部分闲置的空间呢？最直接的办法就是当数组满时，将数据移动到头部，这种数据移动效率比较低，其实有另一种比较常见的方法，是采用循环队列。

循环队列

循环队列实现有以下几点需要注意：

  1. 入队时，尾指针并不是简单的自增，需要使之能够循环，即 $Tail = (Tail + 1）% length$
  2. 出队时，头指针能够循环，即$Head = (Head + 1)% length$
  3. 动态扩容时，如果$Head数组结尾，0->Head，见下图。

详细代码在这里

总结

队列在大部分语言中都有实现，C# 语言中就采用循环队列来实现，感兴趣的可以参考这里。在日常开发中，队列也是一种比较常用的数据结构，比如异步任务队列、线程池、消息队列等等。