数据结构篇—队列（queue）

一、引入

Tips：队列本应该跟栈一块讲的，奈何实在是学不完了，悄悄偷个懒，把这个拆成两部分来写QAQ。

紧接上文....................

让我们把目光转到一条传送带上，让我们仔细观察一下这个物品在传送带上是怎么运行的呢？你发现了什么。

我们发现这样一条传送带的一端只能输入物品，而另一端只能输出物品。这样就出现了现象——先入先出。这也就是队列的基本运行逻辑。

接下来，就让我们一起来学习栈和队列吧！

二、队列的类型定义

1、队列的基本定义

队列的操作和栈的操作类似，只不过相当于栈底可操作的栈。通过这样的一同变化，我们就发现。当栈的栈顶只负责入栈操作，栈底只负责出栈操作，那我们就能得到一个先入先出的队列啦！

通过这样的理解，我们不难发现队列的组成就是在栈的基础上将栈顶变成了队尾、栈底变成了队头。

队头（Front）：允许删除的一端。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

2、队列的常用操作

函数名称	初始条件	操作结果
IntQueue(&Q)	\	构造一个空队列Q
DestroyQueue(&Q)	队列Q已存在	队列Q被销毁，不在存在
ClearQueue(&Q)	队列Q已存在	将Q清为空队列
QueueEmpty(Q)	队列Q已存在	判断Q是否为空
QueueLength(Q)	队列Q已存在	返回Q的元素个数，即队列长度
GetHead(Q)	队列Q非空	返回Q的队头元素
EnQueue(&Q,e)	队列Q已存在	插入元素e为Q的新队尾元素
DeQueue(&Q,e)	队列Q非空	删除Q的队头元素并用e返回
QueueTraverse(Q)	队列Q已存在且非空	从队头到队尾，依次遍历Q

三、队列的顺序、循环结构的表示和实现

1、顺序队列

和顺序栈一样，在队列的顺序储存结构中，出来用一组地址连续的存储单元依次存放从队头到队尾的元素外，尚需要设置两个整形变量front和rear来表示队头、队尾的元素的位置（头指针、尾指针）。

代码描述如下：

#define MAXQSIZE 100    //设置队列可能达到的最大长度
typedef struct{QElemType *base     //存储空间的基地址int front,rear;    //设置头尾指针。
}SqQueue;

为了描述方便，在此约定：初始化创建空队列时，令front=rear=0，每当插入新的队尾元素时，rear++；删除队头元素时front++。因此，在非空队列中，头指针实在指向队列头元素，尾指针始终指向队列尾元素的下一个位置。如下图所示

Tips：假设当前队列最大空间为6，则当队列处于（d）所示状态下则不可再继续插入新的元素，否则就会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象成为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。

那么为了解决这种问题，我们就引出了新的学习——循环队列。

2、循环队列

同循环链表一样，后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。而关于循环队列，我们就要引申到一种新的处理方式——“模”运算。通过取模，头指针和尾指针就能在顺序空间中以头尾相接的方式“循环移动”。

那么具体是怎么实现的呢？让我们一起来看看吧。

这是一个初始化创建的空队列，此时队头队尾都在同一个位置，然后我们顺时针向这个队列中添加一部分元素得到下图

一直往队列中插入元素直到队尾“遇见”队头。

此时，我们的队尾rear的值为8若我们继续进行入队操作的话。就要通过模运算：rear=(rear+1)%8=0。这样，尾指针就重新回到了队头位置开始循坏。

Tips：

初始时：Q->front = Q->rear=0。
队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

倘如我们仔细观察便不难发现，当循环队列为空队列或者是满队列的时候，我们的头指针和尾指针是指向同一个地址的。所以我们就无法通过头尾指针的值是否相同来判断循环队列是满还是空了。

那我们该怎么做呢？

这里推荐一种方法——少用一个元素空间。即当队列空间大小为m时，有m-1个元素就认为队满。这样的话就能将其于判断对空的条件——头尾指针的值相同，区分开来。所以，在循环队列中，

队满条件： (Q->rear + 1)%Maxsize == Q->front
队空条件仍： Q->front == Q->rear

3、循环队列的常见基本操作

3.1、初始化

队列的初始化较为简单，只需要对队列分配一个最大容量为MAXQSIZE的数组空间，用base指向该数组空间的首地址，在将头尾指针置为0，表示队列为空。

代码描述：

Status InitQueue(SqQueue &Q){Q.base=new QElemType[MAXQSIZE];    //为队列分配数组空间Q.fort=Q.rear=0;    //将队列设置为空return OK;    
}

3.2、求循环队列的长度

对于非循环队列，头尾指针的差值就是队列的长度，但对于首尾相接的循环队列来说，这样就不太适用，因为差值可能为负，所以我们需要将差值加上MAXQSIZE，之后在于MAXQSIZE求余。

代码描述：

int QueueLength(SqQueue Q){return (Q.rear-Q,front+MAXQSIZE)%MAXQSIZE;    //返回Q的元素个数，即队列的长度}

3.3、循环队列的入队

对于循环队列的入队操作首先需要判断队列是否为满，若未满则将新元素插入队尾，队尾指针+1.

代码描述：

Status EnQueue(SqQueue &Q,QElemType e){//判断队列是否为满，尾指针在循环意义上+1后等于头指针，表明队满if(Q.rear+1%MAXQSIZE==Q.front){reyurn ERROR;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;
}

3.4、循环队列的出队

对于循环队列的出队草最首先要判断队列是否为空，若不为空则保存队头元素，队头指针++。

代码描述：

Status DeQueue(SqQueue &Q,QElemType e){if(Q.front==Q.rear){        //判断队列是否为空return ERROR;}e=Q.base[Q.front];        //用e保存队头元素Q.front=(Q.front+1)%MAXQSIZE;    //队头元素++return OK;
}

3.5、取循环队列的队头元素

若队列非空，此操作返回其队头元素且指针不变。

代码描述：

QElemType GetTop(SqQueue Q){if(Q.front!=Q.rear){return Q.base[Q.front];}
}

4、链队——队列的链式表示和实现

在之前的学习中我们学到了一种用链式结构实现的栈结构——链栈。那么，对于队列，我们是不是也能用链式结构来实现出一种新的队列的形式呢？让我们一起来学习——链队。

4.1、链队的结构

同链表、链栈一样，当我们用指针将数据块给相连，那么它们就能摆脱顺序结构形成链式结构。如图所示，一个链队需要两个分别表示队头和队尾的指针。所以，为了方便起见，我们给链队添加给头节点，并令头指针始终指向头节点。

代码表示链队的储存结构：

typedef struct QNode{QElemTepy data;struct QNode *next;
}QNode,*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;
}LinkQueue

4.2、链队的基本操作

链队的操作就是单链表的插入、删除操作的特殊情况，只需要进一步修改尾指针或头指针即可。

链队的初始化：

链队的初始化就是和构造一个只有头节点的空队。所以，只需要生成新节点作为头节点，队尾队头指针指向该节点。最后将头节点的指针部分的内容清空。

如图所示

代码描述：

Status InitQueue(LinkQueue &Q){Q.front=new QNode;Q.rear=new QNode;    //生成新节点并用头尾指针指向；Q.front->next=NULL;    //清空头节点的指针部分return OK;
}

链队的入队：

链队的入队操作和一般队列有所不同，不需要判断是否为满。只需要为入队元素分配节点空间，用指针p指向，然后将需要插入的内容赋予给该节点，之后再将该节点插入队尾，并修改队尾指针为p。

如图所示

代码描述：

Status EnQueue(LingQueue &Q,QElemType e){p=new QNode;    //创建新节点p->data=e;       //赋值p->next=NULL;    Q.rear->next=p;    //将新节点插入队尾Q.rear=p;    //修改队尾指针return OK;
}

链表的出队：

链表出队首先要判断链表是否为空，然后再保存队头元素空间，再修改头节点的指针部分，使其指向下一个节点，再判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值并指向头节点。最后释放原队头空间。

如图所示：

代码描述：

Status DeQueue(LinkQueue &Q,QElemType e){if(Q.front==Q.rear){return ERROR;}        //判断队是否为空P=Q.front->next;    //p指向队头元素e=p->data;        //e临时保存Q.front=p->next;    //修改头节点指针域if(Q.rear==p){    Q.rear=Q.front;}    //判断师==是否为最后一个元素delete p;    //释放p空间return OK;
}

取队头元素：

当队列非空时，返回当前队头元素的值，队头指针不变。

代码描述：

QElemType GetTop(LinkQueue Q){if(Q.front==Q.rear){return Q.front->next->date;}
}

如果我的内容对你有帮助，在下就厚着脸皮讨个点赞关注。如果你有更好的想法，还望留在评论区让我来参考学习。我将不胜感激并努力创作出更好的内容。