数据结构，队列篇（链式队列）

前言：

上一篇博主简单讲解了顺序队列和循环队列，今天讲解队列最后一篇链式队，链式队在数据结构中用到比较多，用来做一些排队的算法，还有链式队列是也是和链式栈一样采用链表的方式来表现，链式队列针对数据比较灵活的数据比较方便，因为它不像顺序队列一样需要定义最大值，链式队列只需要建立新结点，比较灵活，没有大小限制，只要内存，并且用完了就释放了，对于变动较大的数据很友好。

每日一遍，防止颓废

1.理解链式队列逻辑，认识核心代码

所谓队列的链式存储结构是用一个线性链表来表示一个队列，队列中每一个元素对应链表中一个链结点，这样的队列简称链接队列。具体地说，把线性链表第1个链结点的指针定义为队头指针front，在链表最后的链结点建立指针rear作为队尾指针，并且限定只能在链头进行删除操作，在链尾进行插入操作，这个线性链表就构成了一个链接队列。另一个与顺序存储结构队列的不同点是，队头指针与队尾指针都是指向实际队头元素与队尾元素所在的链结点。讲人话就是（有着两个指针的单链表，一个指针指向头用来出队，一个指针指向尾用来进队，出队退出条件就是队空，因为是活动的所以不存在存满，除非不能划分内存了）

让我们来认识链式队列的核心代码。

typedef struct Node//新结点的类型，就相当于链表
{
	int data;//存放队中的值
	struct Node *next;//用来指向下一个结点
}Queue;
typedef struct queue//用来链队的类型
{
	Queue *front;//链队头指针
	Queue *rear;//链队尾指针
}LinkQueue;
q = (LinkQueue *)malloc(sizeof(LinkQueue)); //分配链队的内存
q->rear =q->front=NULL;//初始队头队尾指针为空
s = (Queue*)malloc(sizeof(Queue));//创建入队结点
s->data = x;///新结点赋值
q->rear->next =s;//入队：尾指针指向新结点
q->rear = s;//入队：改变尾指针的指向，指向新结点
p=q->front;//出队：创建出队结点，把头节点赋值
x =p->data;//出队：出队结点赋值给x，x输出
q->front=q->rear=NULL; //出队：这个是出队结束判断
q->front=q->front->next;//出队：这个头结点已经出队了，改变指向，指向下一个变成新的头结点
free(p);//出队：出队后释放内存

1.1链式队列初始化和简单操作

其实q->rear和q->front就他们相当于两个链表结点，如果你链表学的好，就front就相当于单链表用头插法建立的头指针，rear就相当于单链表用尾插法建立的尾指针，大家联想记忆一下。

void InitQueue(LinkQueue *&q)//q代表引用形参数相当于指针里面指向指针的指针
{
	q = (LinkQueue *)malloc(sizeof(LinkQueue)); //分配链队的内存
	q->rear =q->foont=NULL;//初始队头队尾指针为空
}
int GetHead(LinkQueue *&q,int &x)//获取队头的值
{
	if(q->front==NULL)//判断是不是空队
	{
		return 0;
	}
	x = q->front->data;//将队头的值赋值给x
	return 1;
 } 
 int QueueEmpty(LinkQueue *q)//判断是不是空队
 {
 	if(q->front==NULL) return 1;//是空队返回1
 	else return 0;//不是返回0
 }
 void DestroyQueue(LinkQueue *&q)//销毁队列
{
	Queue *pre = q->front,*p;
	if(pre!=NULL)//判断是不是已经空队
	{
		if(pre==q->rear)//判断队列只剩一个值了，队头和队尾相等
		{
			free(pre);//释放
		}
		else{
			p=pre->next;//p指向头结点的下一个，用来保存头指针的位置（下面代码会把头释放）
			while(p!=NULL)//遍历p的队列结点
			{
				free(pre);//释放头节点
				pre=p;//重新改变头指针指向
				p=p->next;//指向下一个
			}
			free(pre);//释放最后一个，最后一个没释放
		}
		
	}
	free(q);//释放链队指针
}

1.2链式队列进队

链式队列的进队和单链表的建立用尾插法没什么区别

int EnQueue(LinkQueue *&q,int x)//链式队列进队操作
{
	Queue *s;//创建结点指针
	s = (Queue*)malloc(sizeof(Queue));//分配内存
	s->data = x;//给我们的结点赋值
	s->next=NULL;//尾插法，指向空
	if(q->front==NULL)//判断是不是第一个结点
	{
		q->rear=q->front=s;//第一个结点头尾都是指向它
	 } 
	 else//第二个或多个
	 {
	 	q->rear->next =s;//之前指向最后一个结点的尾指针连接新结点,形成链
	 	q->rear = s;//改变尾指针的指向，指向新结点
	 }
	 return 1;
}

1.3链式队列出队

链式队列的进队和单链表的建立用头插法有异曲同工之出，只不过单链表是输入值，队列是输出值

int DeQueue(LinkQueue *&q,int &x)//链式队列出队操作
{
	Queue *p;//创建出队指针
	if(q->front==NULL)//判断是不是空队
	{
		return 0;
	}
	p=q->front;//指向头指针指向的结点
	x =p->data;//获取结点的值并传回主函数
	if(q->rear==q->front)//原队列只有一个结点，出队后队列变空
	{
		q->front=q->rear=NULL; //变为空队
	}
	else{
		q->front=q->front->next;//有两个以上的队列，头指针已经出队，改变头指针的指向
	}
	free(p);//释放
	return 1;
}

1.4链式队列效果演示和整体代码

博主只是对链式队列做了几个简单的操作，用循环进行入队和出队。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
	int data;
	struct Node *next;
}Queue;
typedef struct queue
{
	Queue *front;
	Queue *rear;
}LinkQueue;

void InitQueue(LinkQueue *&q)
{
	q = (LinkQueue *)malloc(sizeof(LinkQueue)); 
	q->rear =q->front=NULL;
}
void DestroyQueue(LinkQueue *&q)
{
	Queue *pre = q->front,*p;
	if(pre!=NULL)
	{
		if(pre==q->rear)
		{
			free(pre);
		}
		else{
			p=pre->next;
			while(p!=NULL)
			{
				free(pre);
				pre=p;
				p=p->next;
			}
			free(pre);
		}
		
	}
	free(q);
}
int EnQueue(LinkQueue *&q,int x)
{
	Queue *s;
	s = (Queue*)malloc(sizeof(Queue));
	s->data = x;
	s->next=NULL;
	if(q->front==NULL)
	{
		q->rear=q->front=s;
	 } 
	 else
	 {
	 	q->rear->next =s;
	 	q->rear = s;
	 }
	 return 1;
}
int DeQueue(LinkQueue *&q,int &x)
{
	Queue *p;
	if(q->front==NULL)
	{
		return 0;
	}
	p=q->front;
	x =p->data;
	if(q->rear==q->front)
	{
		q->front=q->rear=NULL; 
	}
	else{
		q->front=q->front->next;
	}
	free(p);
	return 1;
}
int GetHead(LinkQueue *&q,int &x)
{
	if(q->front==NULL)
	{
		return 0;
	}
	x = q->front->data;
	return 1;
 } 
 int QueueEmpty(LinkQueue *q)
 {
 	if(q->front==NULL) return 1;
 	else return 0;
 }
int main(int argc, char** argv) {
	LinkQueue *lq;
	int e;
	printf("初始化队列\n");
	InitQueue(lq);
	printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空"));
	int i;
	for(i= 1;i<5;i++)
	{
		printf("%d进队\n",i);
		EnQueue(lq,i);
	}
	printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空"));
	GetHead(lq,e);
	printf("队头元素:%d\n",e);
	printf("出队次序");
	while(!QueueEmpty(lq)) 
	{
		DeQueue(lq,e);
		printf("%d",e); 
	}
	printf("\n");
	DestroyQueue(lq);
	return 0;
}

注：大家在跑整体代码的时候，要建立的是cpp的文件，博主不是用到c的文件，大家注意一些，建立cpp文件就是建立C++控制台。

总结：

数据结构线性表的存储博主就差不多就讲完了，我们重点要学好链表，因为栈和队列基本上都是在链表的基础上实现的，所以链表很重要，大家不会的可以看博主之前的链表的文章，我会把链表的博客链接放在下面，大家可以学习一下，创作不易，点赞，关注，评论，收藏。
上一篇：数据结构专升本学习，队列篇（顺序队和循环队列）
上上篇：数据结构专升本学习笔记，线性表链表小节

下一篇：数据结构专升本学习，顺序串篇