当前位置：首页 > news >正文

【数据结构】三、栈和队列：6.链队列、双端队列、队列的应用（树的层次遍历、广度优先BFS、先来先服务FCFS）

news 来源：原创 2024/9/20 16:59:22

文章目录

- 2.链队列
- - 2.1初始化（带头结点）
  - - 不带头结点
  - 2.2入队（带头结点）
  - 2.3出队（带头结点）
  - ❗2.4链队列c++实例
- 3.双端队列
- - 考点:输出序列合法性
  - - 栈
    - 双端队列
队列的应用
- 1.树的层次遍历
- 2.图的广度优先遍历
- 3.操作系统 - FCFS
补充：释放内存

2.链队列

链队列的front，rear不能存在data的结构体里面，如果那样，每一个结点都有自己的front和raer。

//单链表的结构
typedef struct LinkNode{	//链式队列结点ElemType data;struct LinkNode *next;
}LinkNode;//链队列，队头，对尾结构
//因为队列只处理队头队尾，所以后面只操作这个结构体
typdef struct{				//链式队列LinkNode *front,*rear;	//队列的队头和队尾指针结点
}LinkQueue;

请添加图片描述

2.1初始化（带头结点）

//初始化队列(带头结点)
void InitQueue(LinkQueue &Q){//初始时 front、rear 都指向头结点Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next=NULL;
}

判空

//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.front==Q.rear)return true;elsereturn false;
}

不带头结点

//初始化队列(不带头结点）
void InitQueue(LinkQueue &Q){//初始时 front、rear 都指向NULLQ.front=NULL;Q.rear=NULL;
}//判断队列是否为空（不带头结点）
bool IsEmpty(LinkQueue Q){if(Q.front==NULL)return true;elsereturn false;
}

2.2入队（带头结点）

将元素x入队：

创建新结点。
判断内存是否分配成功。
将元素x放入结点数据域、新节点next指针置空。
队尾rear指向新结点、更新队尾结点。

//新元素入队（带头结点）
void EnQueue(LinkQueue &Q, ElemType x){LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode));if(!s){    //创建结点，分配内存要判断是否分配成功return false; //内存分配失败}s->data=x;s->next=NULL;Q.rear->next=s;//新结点插入到rear之后Q.rear=s;//修改队尾指针
}

2.3出队（带头结点）

步骤：

判断链队列是否为空。
创建temp指针指向要出栈的元素。
用x返回该元素。
删除该结点：将头结点指向删除结点的后继结点，更新队头。
若删除的是队尾，则队头队尾指针均指向队头结点。

//队头元素出队（不带头结点）
bool DeQueue(LinkQueue &Q, ElemType &x){ if(Q.front==0.rear)return false;		//空队LinkNode *temp = Q.front->next;x=temp->data;			//用变量x返回队头元素Q.front->next=p->next;	//修改头结点的 next 指针if (Q.rear==temp)		//此次是最后一个结点出队Q.rear=Q.front;		//修改 rear 指针free(temp);				//释放结点空间return true;
}

❗2.4链队列c++实例

#include<iostream>
using namespace std;#define MaxSize 50 //最大队列长度
typedef int QElemType;// 链队列（带头结点）
// C++//结点结构
typedef struct LinkNode
{QElemType data;struct LinkNode* next; 
}LinkNode; //队列结点类型//链队列，队头，对尾结构
//因为队列只处理队头、队尾，所以后面只操作这个结构体
typedef struct
{LinkNode  *front; //队头指针LinkNode  *rear;  //队尾指针
}LinkQueue; //链式队列定义bool InitQueue(LinkQueue& Q);	//循环队列初始化
bool QueueEmpty(LinkQueue Q);	//判断队列是否为空
int  QueueLength(LinkQueue Q);	//循环队列长度bool EnQueue(LinkQueue& Q, QElemType value);	//循环队列入队
bool DeQueue(LinkQueue& Q, QElemType& value);	//循环队列出队QElemType GetHead(LinkQueue Q);		//获取队头元素
bool QueuePrint(LinkQueue Q);		//打印输出队列
void DestroyQueue(LinkQueue& Q); 	//销毁链队列int main()
{LinkQueue Q;QElemType value;InitQueue(Q);int number = 0;		//入队的元素个数cout << "请输入要入队的元素个数：" << " ";cin >> number; int num = 0;		//入队的数据元素while ((number--) > 0){EnQueue(Q, num); //将num入队num++;}cout << "队列输出顺序：";QueuePrint(Q); //遍历输出队列元素cout << "队头元素为：" << GetHead(Q) << endl;cout << "队列长度为：" << QueueLength(Q) << endl;DeQueue(Q, value); //出队cout << "出队元素为：" <<value<<endl;QueuePrint(Q); //遍历队列元素DestroyQueue(Q);//销毁链式队列，释放内存空间return 0;
}//初始化链队列：front与rear都指向队头结点，队头结点next指针置空
bool InitQueue(LinkQueue& Q) {// 将队列的头尾指针都指向同一个节点，表示队列为空Q.front = Q.rear = new LinkNode;  //Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));if(!Q.front){return false; //内存分配失败}// 带头结点Q.front->next = NULL; //将队列队头指针置空return true; //初始化完成
}//链队列判空
bool QueueEmpty(LinkQueue Q) {//队头队尾指针指向同一位置(队头结点)，队列为空。return Q.front == Q.rear;
}//入队
// 将元素value入队：创建新结点，将元素放入结点数据域、新节点next指针置空、队尾rear指向新结点、更新队尾结点。
bool EnQueue(LinkQueue& Q, QElemType value) {// step1创建指针型LinkNode结点，指针指向要插入的结点元素LinkNode* temp = new LinkNode; // step2判断是否分配成功if (!temp) return false; 	//内存分配失败// step3构建新结点temp->data = value;    //将要插入的元素放入temp结点数据域temp->next = NULL;     //temp结点指针域置空// step4将新结点temp插入到队尾Q.rear->next = temp;   //将队尾指针接上temp结点Q.rear = temp;         //更新队尾结点return true; 
}//出队：删除队头结点的下一位，头结点不存储数据元素。
// 判断链队列是否为空，创建temp指针指向要出栈的元素、删除该结点，将头结点指向删除结点的后继结点，更新队头，若删除的是队尾，则队头队尾指针均指向队头结点。
bool DeQueue(LinkQueue& Q, QElemType &value) {// step1判断链队列是否为空if (!QueueEmpty(Q))   //若链队列不为空{// step2创建temp指针指向要出栈的元素LinkNode* temp = Q.front->next;//temp指向队头结点下一位即第一位元素if (!temp)  return false;// step3删除该结点，将头结点指向删除结点的后继结点，更新队头value = temp->data;		//将temp所指结点的数据保存到value中Q.front->next = temp->next;//更新队头结点// step4若删除的是队尾，则队头队尾指针均指向队头结点if (Q.rear == temp)//如果删除的是最后一个结点(尾结点)，尾结点回移{Q.rear = Q.front;//rear、front均指向仅存的头结点Q.front->next = NULL;}// step5释放出元素所占结点空间delete temp;  //释放出栈元素所占结点空间return true;  //出栈成功}return false; //队列为空
}//获取链队的队头元素
QElemType GetHead(LinkQueue Q) {if (!QueueEmpty(Q)){return Q.front->next->data;}return false; 
}//链队列的长度/元素个数
// 这里Q不能用'&'引用型传递，否则下方队头指针front的移动会修改原队列front指针。不加引用，就会创建一个副本执行操作，故相比前者会多消耗些内存和时间。也可以创建一个临时指针temp对队列进行遍历，这样即使Q加了&, 也不会影响原链队列。
int QueueLength(LinkQueue Q) {if (!QueueEmpty(Q)){int count = 0;	     //元素个数/队列长度while (Q.front != Q.rear)//直到 == 队尾rear{Q.front = Q.front->next;//队头指针后移一位count++; //计数加一}return count; }return false; //队列为空或不存在
}//遍历输出链队元素
bool QueuePrint(LinkQueue Q)  {if (!QueueEmpty(Q)){while (Q.front != Q.rear){Q.front = Q.front->next;	  //将链队头指针指向第一个元素结点cout << Q.front->data <<" ";  //输出该结点所指的结点数据}cout << endl;return true; }cout << "队列为空或不存在！";return false;  
}//链队列销毁：从队头结点开始，一次释放所有结点
void DestroyQueue(LinkQueue& Q) {LinkNode* temp;   //创建临时指针while (Q.front){ //反正rear指针闲置无事，此处可以不额外创建temp，直接将下列temp替换成Q.rear效果一样。temp = Q.front->next; //temp指向队头结点的下一个结点delete Q.front;  //释放队头结点Q.front = temp;  //更新队头结点}Q.rear = NULL;cout << "队列销毁成功！" << endl;
}