【数据结构】三、栈和队列：6.链队列、双端队列、队列的应用（树的层次遍历、广度优先BFS、先来先服务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入队：

1. 创建新结点。
2. 判断内存是否分配成功。
3. 将元素x放入结点数据域、新节点next指针置空。
4. 队尾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出队（带头结点）

步骤：

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

//队头元素出队（不带头结点）
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;
}

请输入要入队的元素个数： 5
队列输出顺序：0 1 2 3 4
队头元素为：0
队列长度为：5
出队元素为：0
1 2 3 4
队列销毁成功！
Press any key to continue . . .

3.双端队列

按照输出种类从少到多：

队列：只允许从一端插入、另一端删除的线性表。

栈：只允许从一端插入和删除的线性表。

输入受限的双端队列：只允许从一端插入、两端删除的线性表。
输出受限的双端队列：只允许从两端插入、一端删除的线性表。

双端队列：允许从两端插入、两端删除的线性表。

考点:输出序列合法性

若数据元素输入序列为1,2,3,4。则共有$A_4^4!=24$种顺序。

栈

卡特兰（Catalan）数：n个不同元素进栈，出栈元素不同排列的个数为
$$\frac{1}{n+1}{C}_{2n}^n$$
所以有
$$\frac{1}{4+1}{C}_8^4=\frac{1}{5}\ast \frac{8\ast 7\ast 6\ast 5}{4\ast 3\ast 2\ast 1}=14$$
种出栈可能。

双端队列

栈中合法的序列，双端队列中一定也合法。

输入受限的双端队列、输出受限的双端队列同样包含栈合法的序列。

队列的应用

1.树的层次遍历

在“树”章节会详细学习。

2.图的广度优先遍历

在“图”章节会详细学习。

3.操作系统 - FCFS

多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。

eg.: CPU的资源分配。

补充：释放内存

在C语言中，动态分配内存用 malloc() 函数，释放内存用 free() 函数。如下所示：

1. int *p = (int*) malloc( sizeof(int) * 10 ); //分配10个int型的内存空间
2. free(p); //释放内存

在C++中，这两个函数仍然可以使用，但是C++又新增了两个关键字，new 和 delete：new 用来动态分配内存，delete 用来释放内存。

用 new 和 delete 分配内存更加简单：

1. int *p = new int; //分配1个int型的内存空间
2. delete p; //释放内存

new 操作符会根据后面的数据类型来推断所需空间的大小。

如果希望分配一组连续的数据，可以使用 new[]：

1. int *p = new int[10]; //分配10个int型的内存空间
2. delete[] p;

用 new[] 分配的内存需要用 delete[] 释放，它们是一一对应的。

和 malloc() 一样，new 也是在堆区分配内存，必须手动释放，否则只能等到程序运行结束由操作系统回收。为了避免内存泄露，通常 new 和 delete、new[] 和 delete[] 操作符应该成对出现，并且不要和C语言中 malloc()、free() 一起混用。

在C++中，建议使用 new 和 delete 来管理内存，它们可以使用C++的一些新特性，最明显的是可以自动调用构造函数和析构函数。