队列

队列，又称为伫列（queue），计算机科学中的一种抽象资料类型，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。 队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

特点

1. 先进先出（FIFO, First-In-First-Out）；
2. 除头尾节点之外，每个元素有一个前驱，一个后继。

存储结构

1. 数组队列：利用一组地址连续的存储单元依次存放从队列头到队列尾的元素，同时附设两个整型变量 front 和 rear 分别指示队列头元素及队列尾元素的位置。

2. 单链队列：使用链表作为基本数据结构，所以不存在伪溢出的问题，队列长度也没有限制，但插入和读取的时间代价较高。

3. 循环队列：可以更简单防止伪溢出的发生，但队列大小是固定的。

操作

我们以数组队列为例，在下面的入队和出队程序中，省略了对上溢和下溢的检查。

入队（ENQUEUE）

ENQUEUE(Q,x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else Q.tail = Q.tail + 1

出队（DEQUEUE）

DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head = Q.length
        Q.head = 1
    else Q.head = Q.head + 1
    return x

可以看出，ENQUEUE 和 DEQUEUE 操作的时间复杂度都为 O(1)。

参考资料

• 《算法导论》第三版 殷建平 等译
• 《数据结构》（C 语言第二版）严蔚敏 等编著
• 维基百科