队列

定义

队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除。

向队列中插入元素称为入队或进队。删除队列中的元素称为出队或离队。

跟我们生活中排队是一样的，最早排队的也是最早离队的，队列的操作特性是先进先出（First In First Out，FIFO）。如图所示：

一些概念如下：

• 队头（front）：允许删除的一端，又被称为队首。

• 队尾（rear）：允许插入的一端。

• 空队列：不包含任何元素的空表。

• 入队：从队尾插入元素。

• 出队：从队头删除元素。

例如，某个队列 Q=(a1, a2, a3, a4, a5)，其中 a1 是队头元素，a5 是队尾元素。由于只能在队头删除元素、在队尾插入元素。因此入队顺序为 a1, a2, a3, a4, a5，出队顺序为 a1, a2, a3, a4, a5。

基本操作

注：

• 队列的基本操作的名称各不相同，应该说数据结构中的基本操作名称在各大书籍或资料中不尽相同，但表达的意思是相通的。
• 下面的基本操作中 & 表示引用调用，这是 C++ 的语法，仅是抽象表示，不必在意。但在实际实现中 C 语言采用的是双指针，而 Java 采用的是对象和函数返回值。

无论是顺序队列还是链式队列，它的基本操作如下：

• init(&Queue)：初始化队列，即构造一个空队列 Queue。
• isEmpty(Queue)：判定队列是否为空，如果队列为空则返回 1，否则返回 0。
• isFull(Queue)：判定队列是否已满，由于顺序（循环）队列分配的空间是有限的，所以存在队满的情况，而链式队列不需要。
• enQueue(&Queue, ele)：将元素入队。如果队列未满，则将 ele 插入，使之成为新的队尾。
• deQueue(&Queue, &ele)：将元素出队。如果队列非空，则删除队头元素，并用 ele 返回。
• size(Queue)：队列中的元素个数。
• getFront(Queue, &ele)：读取队头元素。如果队列非空，则将队头元素赋值给 ele。
• getRear(Queue, &ele)：读取队尾元素。如果队列非空，则将队尾元素赋值给 ele>
• clear(Queue)：清空队列。
• print(Queue)：打印队列中的所有元素。

注意，栈和队列都是操作受限的线性表，因此不是任何队线性表的操作都可以作为栈和队列的操作。比如不能随便读取栈或队列中的某个数据。

注：这里的操作受限指的是，栈只能在一端进行插入和删除操作，另一端不能；而队列只允许在一端进行插入，另一端进行删除，不能都进行删除和插入操作。所以说它们是操作受限的。

存储结构

队列也有两种存储方式，顺序存储和链式存储。前者称为顺序队列（循环队列也是顺序存储的队列），后缀称为链式队列或链队。

顺序（循环）队列

队列的顺序实现指分配一块连续的存储单元存放队列中的元素，并附设两个指针：

• 队头指针 front 指向队头元素。
• 队尾指针 rear 指向队尾元素的下一个位置。

通常采用数组实现。

注：

• 顺序队列和循环队列都是队列的顺序存储实现。
• 在不同的参考书中对 front 和 rear 的定义可能不同。有些参考书中是队头指针 front 指向队头元素的前一个位置，队尾指针 rear 指向队尾元素；有些参考书中是队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素。对于不同的定义，出队和入队的操作是不一样的，但大体原理都是基本相同的，即都需要移动指针和取值或赋值，只是它们的先后顺序有所不同。不必在意这个，学会一种即可。

更多请参考：顺序队列 和 循环队列。

链式队列

采用链式存储的队列称为链队。链队是一个同时带有队头指针和队尾指针的单链表。其中队头指针始终指向队头结点，队尾指针始终指向队尾结点（即单链表的最后一个结点）。

注：链式队列和顺序队列的队尾指针指向不同，在顺序队列中队尾指针指向队尾元素的下一个位置，在链式队列中队尾指针指向队尾结点。

更多请参考：链队列。

其他队列

双端队列

双端队列是普通队列的扩展，是指允许两端都可以进行入队和出队操作的队列（即可以在队头进行入队和出队操作，也可以在队尾进行入队和出队操作的队列）。其元素的逻辑结构仍然是线性结构，可以采用顺序存储，也可以采用链式存储。将队列的两端分别称为前端和后端，两端都可以入队和出队。

更多请参考：双端队列。