摘要HookXuan：本文主要介绍队列的结构、基本原理和操作，涉及两种实现：顺序队列和链式队列。1.什么是队列？举一个日常的例子，排队买菜。排队买菜的时候，大家按照先到先得的顺序在窗口前排队买菜。买完走开，轮到下一个人买。新人排在队尾，不能插队。可以看出，上面“团队”的特点是只允许从一端进入，从另一端离开。这样的队在数据结构中称为“队列”。首先，队列是一个线性表，所以它具有线性表的基本特征。其次，队列是一个有限制的线性表，限制是：只允许一端进入队列，不允许另一端离开。根据以上特点，可以画出一个示意图：元素1出队后，元素4入队后：下面是几个相关名词：Enqueue：入队，也就是将元素插入到队列出队：离开队列，即从队列中删除元素头：允许出队（删除）的一端队尾：允许入队（插入）的一端队列头元素：即是的元素pushedinstallfirstinthequeuetailelement:队列中最后入栈的元素head元素视为队头，tail元素视为队尾。（理解这些名词概念就够了，不用再仔细研究了。）队列的重要特点是在队尾入队，在队头进行出队操作队列，所以上图中元素入队顺序为：1,2,3，出队顺序为：1,2,3，即先入先出队（先进先出，FIFO），最后进队然后出队（LastInLastOut，LILO）。总结一下，队列是一个先进先出的受限线性表，只允许在一端插入，在另一端删除。2.队列的实现思路和栈是一样的。队列也可以有两种实现方式：数组实现的顺序队列和链表实现的链式队列。2.1.数组实现——顺序队列一个用数组实现的顺序队列如下图所示：队列的容量值——MAXSIZE标识队列头的头下标——front标识队列尾部的尾下标——rearfront和rear会随着进出队列的操作而变化。为了方便，我们规定在空队列中，尾索引为尾元素的下一个元素的索引。了解结构后，我们可以很容易的用C语言的结构实现：#defineMAXSIZE5//顺序队列的最大存储容量/*顺序队列的结构*/typedefstruct{intdata[MAXSIZE];intfront;//队头下标intrear;//队尾下标}QueueArray;2.2.链表实现——链式队列我们使用单链表和首节点来实现队列，如下图所示：链式队列可以看出，要实现一个链式队列，需要如下结构：1.单向链表的基本单元节点——QueueNode存储数据的数据域——指向下一个节点的数据指针域——next2。指向链表头部的指针——head3。指针-front4。标识队尾的尾指针-rear其中，头指针head和队头指针front都指向单链表的第一个节点，所以这个指针可以合二为一，队头指针是头指针。这样我们就可以使用链表的尾插入方式实现队列的入队操作，使用链表的头删除方式实现队列的出队操作。理清结构后，用如下结构实现：/*单链表节点结构*/typedefstructQueueNode{intdata;//数据域structQueueNode*next;//指针域}QueueNode;/*链式队列结构*/typedefstruct{QueueNode*front;//队列头指针QueueNode*rear;//队列尾指针}QueueLink;，队列头尾下标都为0，即front=rear=0：空队列【非空非满队列】：队列非空且有剩余空间：非空非满queue[fullqueue]：顺序队列分配的固定空间用完了，没有空间了，不能再插入元素了。此时front=0,rear=MAXSIZE:fullqueue从上图可以看出，非空队列的尾部下标rear永远是队列尾元素的下一个元素的下标。3.2.Falsefullqueue以上是数组实现的顺序队列的三种状态，但是上图中的三个队列都有一个问题，就是队列的存储问题！首先再次明确队列的两个重要特性：队列只允许Delete队头元素和插入队尾元素。我们规定front是队头元素的下标，rear是队尾元素的下标。两者会随着出队和入队的操作而变化。图中前面在下标0处，不容易看出问题。请看下面的流程图：入队和出队流程图用文字简单描述了上面的流程：图1：清空队列图2：入队3个元素：1,2,3图3：出队2个元素：1,2图4：Enqueue2elements:4,5至此一切正常。图5：入队1个元素，但是图4中rear=5已经超出了数组的最大范围，所以图5中入队时会报错，不能再往这个队列中插入元素。图5中的队列是否已满？没满！可以继续插入元素吗？不！有剩余空间，但不能使用。这就像一家旅馆，有空房间，不允许客人入住。满队列是空间不足且无法插入更多元素的队列。图5中的队列虽然不能继续插入元素，但它还有剩余空间，所以这样的队列不能称为满队列，可以称为Fake满队列。之所以会出现falsefullqueue的问题，是因为sequentialqueue的空间有限。经过几次入队操作，我们的后方“跑”出数组，导致越界。假满队列明明只存了一个元素，但是因为假满，整个队列已经存不下了。这样的队列当然不是一个合格的数据结构。如何解决？错误是后方越界造成的，而队列最前面的大部分是空闲的，那么当后方越界时，我们能不能把它移到下标0呢？显然是的，这就构成了一个“Circulation”，我们把这种前后可以循环的称为循环队列。3.3.循环队列为了突出“循环”二字，我们把这个顺序队列画成一个圆圈：循环队列循环队列的后部和前部可以在队列中来回转动，就像时钟的时针和分针一样.将不再有无法使用的空间。顺序队列的形式从“直线式”变成了这种循环式之后，对状态的判断也发生了变化。【EmptyQueue】：队列中没有元素，如上图所示。请注意，空队列的条件不是front=rear=0。例如，空队列经过3次入队和3次出队操作后仍然是空队列：emptyqueue所以，当循环队列为空队列时，条件应该是front=rear[fullqueue]：队列中没有空闲空间。上面的full队列是一个最大容量为8的空队列，加入7个元素后，队列中还有1个空闲位置。如果此时我们再次入队1个元素：是否满队？此时队列中确实没有空闲空间，但是注意此时队列满足rear=front，但是满足rear=front的队列不应该是空队列吗？这是一种误解。我们何不退后一步，少用一个元素来消除误解。如下图，规定这是一个满队列。Fullqueue我们规定当front出现在rear的下一个位置时，队列满了。比如上面的full队列，front=3在rear=2的下一个位置，所以判断队列满的条件是：rear+1=front，但是这个条件是不准确的。因为循环队列中的front和rear是循环使用的，就像时钟的时针一样，我们只根据下标的大小来判断位置是不合理的。下面两个是满队列，右图不满足rear+1=front：就像时钟的时针满12归零一样，front和rear也应该在到达某个数后归零已满，这个数字是MAXSIZE。比如rear=7，如果按照惯例，下一步应该是rear=8，但是这里，我们让它归零，所以下一步应该是rear=0。上面的归零过程表示由一个数学公式：rear%MAXSIZE，所以满队列的判断条件应该是：(rear+1)%MAXSIZE=front。【非空非满队列】：很容易理解，这里不再赘述。3.4.链式队列我们使用单向链表与领先节点来实现链式队列。[EmptyQueue]：空链表。此时头指针（和链表的头指针）和尾指针都指向头节点。空队列【非空队列】：与顺序队列有空间限制不同，链式队列的空间是无限的（只要你的内存足够大），自然没有“满队列”和“循环队列”的概念队列”。.4.初始化在操作队列之前，首先要进行初始化，即初始化一个空队列。4.1.对于顺序队列，只需将队列的头下标和尾下标设置为0即可。/***初始化顺序队列：将头下标和尾下标设置为0*queue：指向队列的指针*/voidinit(QueueArray*queue){queue->front=0;queue->rear=0;}4.2.链式队列创建一个头节点，然后队列头指针和队列尾指针都指向头节点。/***初始化链式队列：将队列头指针和队列尾指针指向头节点*/voidinit(QueueLink*queue){//创建头节点QueueNode*head_node=create_node(0);//队列头pointerteam尾指针指向头节点queue->front=head_node;queue->rear=head_node;}5.入队操作入队操作只允许元素从队尾进入。5.1.顺序队列我们规定顺序队列的尾标为队尾元素的下一个元素，所以直接把要入队的元素放到队尾的下标中，然后加一个到队尾的下标。(注：循环队列中加1需要取模MAXSIZE)入队过程/***入队操作*queue:队列指针*elem:入队数据*return:0失败，1成功*/inten_queue(QueueArray*queue,intelem){//判断队列是否满if((queue->rear+1)%MAXSIZE==queue->front){printf("队列满不能继续入队。\n");return0;}//元素进入队列queue->data[queue->rear]=elem;//在队列尾部添加下标queue->rear=(queue->rear+1)%MAXSIZE;return1;}5.2。ChainQueue链式队列的入队操作本质是单链表的尾插入方式：/***入队操作*queue:队列指针*elem:数据入队*/voiden_queue(QueueLink*queue,intelem){//新建节点QueueNode*new=create_node(elem);//进入队列（尾部插入方式）queue->rear->next=new;queue->rear=new;}6.出队操作Dequeue该操作只允许元素从队列头部出队。6.1.顺序队列将队头下标处的元素出队，然后对队头下标“加一”（取模MAXSIZE）。出队过程/***出队操作*queue:队列指针*elem:指向保存出队数据的变量*return:0失败，1成功*/intde_queue(QueueArray*queue,int*elem){//判断队列是否为空if(queue->front==queue->rear){printf("队列为空，不能输出元素。\n");return0;}//元素出队列*elem=queue->data[queue->front];//队头下标加一个queue->front=(queue->front+1)%MAXSIZE;return1;}6.2.链式队列链式队列的出队操作本质上是一种单链表的Header删除方式。注意，如果队列中的最后一个元素出队，出队后需要将尾指针重新指向头节点，重新形成一个空队列。/***出队操作*queue:队列指针*elem:保存变量指针*return:0失败，1成功*/intde_queue(QueueLink*queue,int*elem){//检查队列是否为空if(queue->front==queue->rear){printf("队列为空，没有元素出去。\n");return0;}QueueNode*front_node=queue->front->next;//队头元素//保存数据*elem=front_node->data;//队头元素出队（队头删除法）queue->front->next=front_node->next;//如果元素执行完毕，队尾指针再次指向队头节点if(front_node==queue->rear)queue->rear=queue->front;free(front_node);}7.遍历操作这里我们以打印整个队列为例，介绍如何遍历队列。顺序队列有头标和尾标，链式队列有头指针和尾指针。我们要做的就是用一个临时变量，从头下标一个一个遍历到尾下标。7.1.借助于临时变量i，顺序队列从队头的下标开始一个一个“加一”，直到队尾的下标结束。起始标记为：i=front加一操作为：i=(i+1)%MAXSIZE结束标记为：i%MAXSIZE=rear/***printqueue*/voidoutput(QueueArrayqueue){inti=queue.front;while(i%MAXSIZE!=queue.rear){printf("%d",queue.data[i]);i=(i+1)%MAXSIZE;}printf("\n");}如何计算顺序队列长度？当然可以遍历队列，用count变量来存长度，比较麻烦。因为顺序队列是使用数组实现的，所以我们可以直接根据下标计算顺序队列的长度。如果是非循环队列就很简单了，直接rear-front就是队列的长度。但是循环队列不能直接这样缩减，因为rear和front的位置关系是不确定的。左图rear
