队列

【队列的定义】

队列（Queue），也是一种操作受限的线性表，只允许在表的一端插入，在表的另一端删除，其中，只允许删除的那一端称为队首，只允许插入的那一端称为队尾，当线性表中不含元素时，称为空队列

队列具有先进先出（First In First Out，FIFO）的操作性质，如下图所示，假设某个队列 $Q=(a_1,a_2,a_3,a_4,a_5)$ ，其中 $a_1$ 为队首元素，$a_5$ 为队尾元素，进队顺序为：$a_1,a_2,a_3,a_4,a_5$，出队顺序为：$a_1,a_2,a_3,a_4,a_5$

【双端队列】

双端队列是指两端均可以进入队和出队的队列，其元素的逻辑结构仍为线性结构

双端队列分为前端、后端两端，均可以进行出队与入队，在双端队列进队时，前端进的元素排列在后端进的元素之前；在双端队列出队时，无论前端还是后端出队，先出的元素排列在后出的元素之前

只允许在一端进行插入、删除，在另一端只允许插入的双端队列被称为输出受限的双端队列

只允许在一端进行插入、删除，在另一端只允许删除的双端队列被称为输入受限的双端队列

【队列的存储结构】

队列也是一种受限的线性表，类似于线性表，其有顺序存储方式和链式存储方式两种

采用顺序存储方式的队列称为顺序队列，其利用一组地址连续的存储单元存放从队首到队尾的数据元素，并设置一个头指针来指示当前队首元素位置，设置一个尾指针来指示当前队尾元素位置或队尾元素的下一个位置

由于顺序队列假溢出的问题，可以令顺序队列在逻辑上视为一个环，当队首指针到达线性表最大长度时，再令其返回线性表的初始位置，以解决假溢出问题，这种逻辑上为环装的顺序队列称为循环队列

采用链式存储方式的队列称为链式队列，通常采用带有一个队首指针和一个队尾指针的带头单链表实现，其中，队首指针指向单链表头结点，队尾指针指向单链表的最后一个结点