🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：前面两章重点介绍了栈的表示与实现，本章将详细解释队列的表示与实现，以及相关的基本操作。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第七章：队列的表示与操作实现
📝1️⃣队列的类型定义
队列的操作与栈的操作类似，不同的是，删除是在表的头部（即队头）进行。
✨队列的抽象数据类型
ADT Queue { 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系：R={＜ai−1,ai＞|ai−1,ai∈D,i=2,…,n} 基本操作： InitQueue(＆Q) 操作结果：构造一个空队列Q。 DestroyQueue(＆Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 ClearQueue(＆Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回true，否则返回false。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q) 初始条件：Q为非空队列。 操作结果：返回Q的队头元素。 EnQueue(＆Q,e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(＆Q,＆e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 QueueTraverse(Q) 初始条件：Q已存在且非空。 操作结果：从队头到队尾，依次对Q的每个数据元素访问。 QueueTraverse(Q,visit())//遍历 }ADT Queue
✨类型定义
#define M 100 //队列最大长度 Typedef struct { Queue *base;//初始化的动态分配空间 int front;//头指针 int rear;//尾指针 }SqQueue;
📝2️⃣循环队列—队列的顺序表示和实现
队列也有两种存储表示，顺序表示和链式表示。
和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个整型变量front和rear分别指示队列头元素及队列尾元素的位置（后面分别称为头指针和尾指针）。
编辑
✨初始化
循环队列的初始化操作就是动态分配一个预定义大小为MAXQSIZE的数组空间。
【算法步骤】
- 为队列分配一个最大容量为MAXSIZE的数组空间，base指向数组空间的首地址。
- 头指针和尾指针置为零，表示队列为空。
【算法描述】
Status InitQueue(SqQueue ＆Q) { //构造一个空队列Q Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间 if(!Q.base) exit(OVERFLOW); //存储分配失败 Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空 return OK; }
✨求队列长度
对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。
QueueLength = (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE
【算法描述】
int QueueLength(SqQueue Q) { //返回Q的元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }
✨入队
入队操作是指在队尾插入一个新的元素。
【算法步骤】
- 判断队列是否满，若满则返回ERROR。
- 将新元素插入队尾。
- 队尾指针加1。
【算法描述】
Status EnQueue(SqQueue ＆Q,QElemType e) { //插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满 return ERROR; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1 return OK； }
✨出队
出队操作是将队头元素删除。
【算法步骤】
- 判断队列是否为空，若空则返回ERROR。
- 保存队头元素。
- 队头指针加1。
【算法描述】
Status DeQueue(SqQueue ＆Q,QElemType ＆e) { //删除Q的队头元素，用e返回其值 if(Q.front==Q.rear) return ERROR; //队空 e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1 return OK; }
✨取队头元素
当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。
【算法描述】
SElemType GetHead(SqQueue Q) { //返回Q的队头元素，不修改队头指针 if(Q.front!=Q.rear) //队列非空 return Q.base[Q.front]; //返回队头元素的值，队头指针不变 }
由上述分析可见，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法预估所用队列的最大长度，则宜采用链队。
📝3️⃣链队—队列的链式表示和实现
链队是指采用链式存储结构实现的队列。通常链队用单链表来表示。一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。这里和线性表的单链表一样，为了操作方便起见，给链队添加一个头结点，并令头指针始终指向头结点。
编辑
✨链式存储结构
typedef struct QNode { QElemType data; struct QNode next; }QNode, QueuePtr; typedef struct { QueuePtr front; //队头指针 QueuePtr rear; //队尾指针 }LinkQueue;
链队的操作即为单链表插入和删除操作的特殊情况，只是需进一步修改尾指针或头指针。下面给出链队初始化、入队、出队操作的实现。
✨初始化
链队的初始化操作就是构造一个只有一个头结点的空队。
【算法步骤】
- 生成新结点作为头结点，队头和队尾指针指向此结点。
- 头结点的指针域置空。
【算法描述】
Status InitQueue(LinkQueue ＆Q) { //构造一个空队列Q Q.front=Q.rear=new QNode; //生成新结点作为头结点，队头和队尾指针指向此结点 Q.front->next=NULL; //头结点的指针域置空 return OK; }
✨入队
和循环队列的入队操作不同的是，链队在入队前不需要判断队是否满，需要为入队元素动态分配一个结点空间。
【算法步骤】
- 为入队元素分配结点空间，用指针p指向。
- 将新结点数据域置为e。
- 将新结点插入到队尾。
- 修改队尾指针为p
【算法描述】
Status EnQueue(LinkQueue ＆Q,QElemType e) { //插入元素e为Q的新的队尾元素 p=new QNode; //为入队元素分配结点空间，用指针p指向 p->data=e; //将新结点数据域置为e p->next=NULL; Q.rear->next=p; //将新结点插入到队尾 Q.rear=p; //修改队尾指针 return OK; }
✨出队
和循环队列一样，链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放出队头元素的所占空间。
【算法步骤】
- 判断队列是否为空，若空则返回ERROR。
- 临时保存队头元素的空间，以备释放。
- 修改队头指针，指向下一个结点。
- 判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。
- 释放原队头元素的空间。
【算法描述】
Status DeQueue(LinkQueue ＆Q,QElemType ＆e) { //删除Q的队头元素，用e返回其值 if(Q.front==Q.rear) return ERROR; //若队列空，则返回ERROR p=Q.front->next; //p指向队头元素 e=p->data; //e保存队头元素的值 Q.front->next=p->next; //修改头指针 if(Q.rear==p) Q.rear=Q.front; //最后一个元素被删，队尾指针指向头结点 delete p; //释放原队头元素的空间 return OK; }
需要注意的是，在链队出队操作时还要考虑当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）。
✨取队列头元素
与循环队列一样，当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。
【算法描述】
SElemType GetHead(LinkQueue Q) { //返回Q的队头元素，不修改队头指针 if(Q.front!=Q.rear) //队列非空 return Q.front->next->data; //返回队头元素的值，队头指针不变 }
