带你认识什么叫做队列（队列的定义和基本操作）

1、队列概念和基本操作

队列(Queue)简称队，它和堆栈一样，也是一种运算受限的线形表。其限制是在表的一端进行插入，在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(Rear),删除元素的一端称为队头(Front)。向队尾插入元素称为入队或者进队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或者出队，元素出队后，其后续元素成为新的队头元素。

由于队列的插入和删除操作分别在队尾和队头进行，每个元素必然按照进入的次序离队，即先进队的元素必然先离队，所以队列又被称为先进先出表(Frist In Frist Our,FIFO)。如图1，1是对头，6是队尾，取出数据只能从队头取出，存入数据只能在队尾中进入。

2、顺序队列

利用顺序存储方式实现的队列称为顺序队列，顺序队列实际上是运算受限的顺序表。它是利用一组地址连续的存储单元存放队列中的元素，由于队列中的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队首元素和队尾元素。

设顺序队列Q的容量为6，其队头指针为front，队尾指针为rear,头、尾指针和队列中元素的关系如图2所示。

2.1入队操作思想

根据顺序队列的存储特点，要使某一元素进入队列，则要进行如下操作:

(1)先判断队列是否已经装满元素，如果未装满才能进行入队操作，否则不操作。

(2)将要入队的元素放入队尾，队尾指针再自增。

【例】某班已有2名同学张三、李四的学生信息存放在队列中，现有(10003，王五) 同学加入，请将其信息放入队列中。

放入对应结点的过程如下:

入队前如图3所示。

将要入队的元素(10003，王五)放入队尾，队尾指针再自增，如图4所示。

2.2出队操作思想

根据顺序队列的存储特点，要使某一元素移出队列，则要进行如下操作:

(1) 先判断队列是否为空，如果不为空才能进行出队操作，否则不操作。

(2)将队头的元素取出，再使队头指针自增。

【例】某班已有3 名同学张三、李四、王五的学生信息存放在队列内，现需要从队列中取出一位同学的信息进行审查，并显示取出的信息。

取出对应结点的过程如下:

出队前如图4所示。

将队头的元素(10001,张三)取出，再使队头指针自增，如图5所示。

3、循环队列

在顺序队列中，为了降低运算的复杂度，元素入队时，只需要修改队尾指针，元素出队时只需要修改队头指针。由于顺序队列的空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限值时，就不能只通过修改队尾指针来实现新元素的入队操作。此时就会出现如下问题：

设数组空间为M，如图6所示，则：

当front=0，rear=M-1时，再有元素入队发生溢出--真溢出。

当front !=0，rear=M-1时，再有元素入队发生溢出--假溢出。

解决假溢出的办法有两种：一是队首固定，每次出队剩余元素向下移动，这样时间效率比较低；二是使用循环队列。

在顺序队列的基础上，我们将数组的最后一个元素的下一个元素从逻辑上认为是数组的第一个元素，这样的形成逻辑上的环，如图6.1所示。

循环队列存在一个问题，就是如何判定循环队列空和满的问题。

表6.2列出了两种方法解决循环队列空和满的判定比较：

在图7中用队首指针front 指向队首元素所在的单元，用队尾指针rear 指向队尾元素所在单元的后一个单元。如此在图7 (b)所示的循环队列中，队首元素为e0, 队尾元素为e3。 当e4、e5、e6、e7 相继进入队列后，如图3.25(c) 所示，队列空间被占满，此时队尾指针追上队首指针，有rear = front。反之，如果从图7 (b)所示的状态开始，e0、e1、e2、e3 相继出队，则得到空队列，如图7 (a)所示，此时队首指针追上队尾指针，所以也有front =rear。可见仅凭front 与rear 是否相等无法判断队列的状态是“空”还是“满”。解决这个问题可以有两种处理方法: 一种方法是少使用一个存储空间，当队尾指针的下一个单元就是队首指针所指单元时，则停止入队。这样队尾指针就不会追上队首指针，所以在队列满时就不会有front = rear。这样一来，队列满的条件就变为 ( rear+1 )%M = front, 而队列判空的条件不变，仍然为front = rear。另外一种方法是增设一个标志，以区别队列是“空”还是“满”，例如增设size 变量表明队列中数据元素的个数，如果size = Max 则队列满。

4、链式队列

队列的链式存储可以使用单链表来实现。为了操作方便，这里采用带头结点的单链表结构。根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操作的实现。为此一共设置两个指针，一个队首指针和一个队尾指针，如图8所示。队首指针指向队首元素的前一个结点，即始终指向链表的头结点，队尾指针指向队列当前队尾元素所在的结点。当队列为空时，队首指针与队尾指针均指向空的头结点。

链队列的基本操作也有进队、出队操作。

4.1入队操作思想

将某一个新结点s 排入队列内，则要进行如下操作:

(1)将队尾rear 的后继设为新结点S。

(2)将队尾指针rear 后移，即rear= rear.next。

【例】 某班已有2名同学张三、李四的学生信息排在队列里，现有(10003，王五）同学加入，将其也排入队列中。

对应结点排入队列的过程如下:

入队列前如图9所示

4.2、出队列操作思想

在队列内有元素的情况下，对于带头结点的链式队列出队是头结点后的队首元素出队，具体操作如下:

(1) 保存头结点后的队首元素。

(2) 设置头结点的后继元素为队首元素的后继元素，即front.next=front.next.next。

【例】某班已有3名同学张三、李四、王五的学生息排入队列内，现需要从链队列中取出一位同学的信息进行审查，并显示取出的信息。

取出对应结点的过程如下:

出队前学生信息队列状态，如图12所示：

关注小编，每天学习一点点，提升自己的知识水平。