目录

队列（Queue）

队列的顺序存储结构

队列的顺序存储结构 -入队

队列的顺序存储结构 -出队

循环队列

队列的链式存储结构

队列的链式存储结构-入队

队列的链式存储结构-出队

队列的实现（顺序存储结构和链式存储结构）

---

队列（Queue）

队列（Queue），是具有一定操作限制的线性表。只能在一端插入，在另一端删除。

• 插入数据：入队（AddQ）
• 删除数据：出队（DeleteQ）
• 先进先出：First In First Out（FIFO）

队列的抽象数据类型描述

数据对象集：一个有0或多个元素的线性表。

操作集：

1. 生成长度为MaxSize的空队列
2. 判断队列是否已满
3. 判断队列是否已空
4. 将元素插入队列中
5. 将元素从队列中删除并返回

队列的顺序存储结构

队列的顺序存储结构组成：一个一维数组、一个记录队列头元素位置的变量front、一个记录队列尾元素的变量rear。

• 可以声明front=0，rear=-1。每次入队rear+1，每次出队front+1。
• rear-front=-1时，队列空。
• rear+1=MaxSize时，队列满。

队列的顺序存储结构 -入队

队列的顺序存储结构 -出队

循环队列

经过多次的入队和出队，队尾会达到数组的限制，而对头会空出几个位置。为了更好地利用数组的空间，则引入循环队列的概念。

• 可以声明front=0，rear=-1。每次入队rear+1，每次出队front+1。
• 循环存入时，rear和front的值一直累加。需要确定front和rear下标时，使用front和rear与数组MaxSize取模。
• rear-front=-1时，队列空。
• rear-front+1=MaxSize时，队列满。

可以看到示例图中的循环队列，下标最大为5。如果不使用循环队列概念，最多能从a1存储到a6，队列就满了。但是经过两次出队后，下标0和1的位置空了，所以a7可以入队到循环队列下标为0的位置。

队列的链式存储结构

队列也可以使用一个单链表实现。插入和删除操作分别在链表的两端进行。

链表的特点是：在链表的头部，做插入、删除操作都方便；在链表的尾部，做插入操作方便，做删除操作不方便。

• 在链表头部进行出队操作
• 在链表尾部进行入队操作
• 需要front和rear分别指向链的头节点的和尾节点。当front不指向任何节点时，队列为空。

队列的链式存储结构-入队

队列的链式存储结构-出队

队列的实现（顺序存储结构和链式存储结构）

待补充