数据结构之队列

3.4 队列

3.4.1 抽象的数据类型队列的定义

和栈相反，队列是一种先进先出（first in first out,缩写为FIFO）的线性表，它只允许在表的一端进行插入，而在表的另一端删除元素。

这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear）,允许删除的一端则称为队头。

队列的操作与栈的操作类似，也有8个，不同的是删除是在表的头部（即队列）进行。

补

充

知

识

双端队列

双端队列是限定插入和删除操作在表的两端进行的线性表。这两个端分别为称作 端点1和端点2

在实际的使用中，还可以有：

输出受限的双端队列（一个端点允许插入和删除，另一个端点只允许插入）

输入受限的双端队列（一个端点允许插入和删除，另一个端点只允许删除）

3.4.2 链队列---队列的链式表示和实现

和线性表类似，队列也可以有两种存储表示。

用链表表示的队列简称链队列。一个链队列显然需要两个分别指示队头和队尾的指针（分别称之为头指针和伪指针）才能唯一确定。

这里和线性表一样，为了操作方便起见，我们给链队列添加一个头结点，并令头指针指向头结点，由此，空的链队列的判决条件为头指针和尾指针均指向头结点。

链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。

程序

（程序框可以左右滑动哦~）

执行结果：

3.4.3 循环队列---队列的顺序表示和实现

循环队列和 一般的队列的区别在于：

如图所示，和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头和队尾的位置之外，

尚需附设两个指针front 和 rear 分别指示队头元素及队尾元素的位置。为了在C语言中描述方便起见，再次约定：

初始化建空队列时，令front=rear=0,

每当插入新的队列尾元素时，“尾指针之增1”；

每当删除队列头元素时，“头指针增1”

因此，在非空队列中，头指针始终队列头元素，而尾指针始终指向队尾元素的下一个位置。

但是当出现如图d的情况时，队尾已经将已有的空间用尽，同时队头也马上追平队尾

如果继续插入新的元素，程序会因为数组越界而被破坏，然而此时又不宜如顺序栈那样，进行存储再分配扩大数组（因为队列的可用空间并未占满）。

优点：

所以这个时候 循环队列的作用就体现出来了，如图所示：

这时出现一个问题，Q.front == Q.rear 无法判别队列空间是 “空” 还是“满”

处理这种情况的方法一般有两种：

1. 再设一个标志位以区别队列是“空” 还是“满”

2. （强烈推荐）少用一个元素的空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列 “满”状态的标志

缺点：

从上述分析可见，在C语言中不能用动态分配的一维数组来实现。

如果用户的应用程序设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队列。

程序

（程序框可以左右滑动哦~）

执行结果：