1.队列概述

队列类似现实场景中的排队。

1.1.队列的定义

队列是一种特殊的线性表，入队操作在表的一端，出队操作在表的另一端。

允许入队的一端称为队尾，允许出队的一端称为队头。

位于队尾的元素称为队尾元素，位于队头的元素称为队头元素。

简单的队列如下图所示：

队列是一种先进先出的线性表。

1.2.队列的操作

队列共有以下五种运算：

（1）create：创建空队列

（2）enQueue：入队，将新元素插入队尾，使之称为队尾元素

（3）deQueue：出队，返回队头元素的值，将队头元素删除

（4）getHead：返回队头元素的值

（5）isEmpty：判断队列是否为空

1.3.队列的使用场景

队列保证先后顺序，不允许插队。场景场景比如：

（1）CPU任务调度

（2）线程池阻塞队列

2.队头固定的数组实现

如下图所示：

2.1.入队操作——enQueue

如下图所示：

2.2.出队操作——deQueue

如下图所示：

3.队头不固定的数组实现

如下图所示：

3.1.入队操作——enQueue

如下图所示：

3.2.出队操作——deQueue

如下图所示：

3.3.队列满

如下图所示：

4.循环队列的数组实现

如下图所示：

4.1.入队操作——enQueue

如下图所示：

4.2.出队操作——deQueue

如下图所示：

4.3.队列满

如下图所示：

5.队列的链表实现

如下图所示：

链表实现不存在队列满的情况。

5.1.入队操作——enQueue

如下图所示：

5.2.出队操作——deQueue

如下图所示：