白日去如箭，达者惜今阳。                                                   --朱敦儒

目录 

🚁前言：​

🏝️一.队列的概念及结构 

🌻二.队列各种功能的实现

🍍1.队列的初始化

🏝️2.队列的尾入

🍉3.队列头的元素

🍁4.队列的头出

🍀5.判断是否为空

🚲6.队列尾的元素

🪂7.销毁队列

🌴三.队列的全部代码 

🌻1.Queue.h：

🍌2.Queue.c：

🍈3.test.c：

🚁前言：

前几天我们对栈进行了实现，栈是数据先进后出，而今天我们要是实现的队列是完全相反的，队列
是数据先进先出。而在栈中我们使用的顺序表(数组)来实现的。而队列却用单链表来实现是更加合适的。

在队列入数据的时候，相当于是尾插，而队列出数据的时候相当于是头删。

• 队列的顺序结构
  入队，不需要移动任何元素，时间复杂度为O(1)。
  出队，所有元素需要往前移动，时间复杂度为O(N)。
• 队列的链式结构
  首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点。
  入队（尾插），时间复杂度为O(1)。
  出队（头删），时间复杂度为O(1)。
  结论：所以我们使用单链表来实现队列。

🏝️一.队列的概念及结构 

     队列：只允许在一端进行插入数据操作，在另一端进行数据操作的特殊线性表，队列具有先进先出FIFO(Frist in First out)。

入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为对头。

队列的初始结构：单链表实现

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;//单链表
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;//队列头
	QNode* tail;//队列尾
}Queue;

🌻二.队列各种功能的实现

🍍1.队列的初始化

  这里我们实现的单链表是无头不循环的单链表。所以我们把队列头和队列尾初始化为空指针。

//初始化
void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = ps->tail = NULL;
}

🏝️2.队列的尾入

    对于队列的尾入，我们要分为两种情况：
第一种：第一次尾入数据的时候，队列头和队列尾都是指向的同一个位置，并且都是空，当我们要尾入的时候创建一个新的结点，把新结点赋值给队列的头和队列的尾。

第二种：队列已经有数据了，我们把新的结点链接到尾后面，然后再把新结点赋值为新的结点，也就是更新队列的尾。总结：队列头是一直不变的，队列尾入一个数据就需要把队列尾往后面移动一位。
 

//队尾入
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的结点
	if (newnode == NULL)
	{
		perror("malloc
");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if ( ps->tail == NULL)//第一种情况
	{
		ps->head=ps->tail = newnode;//新结点就是队列尾和队列头
	}
	else//第二种情况
	{
		ps->tail->next = newnode;//队列尾链接新的结点
		ps->tail = newnode;//更新队列尾
	}
}

🍉3.队列头的元素

     需要知道队列头的元素是非常简单的，只需要返回队列头的元素即可。

//头的元素
QDataType QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	return ps->head->data;
}

🍁4.队列的头出

   队列的头出也是分为两种情况：
第一种：当队列只有一个结点的时候，直接free掉第一个结点即可，然后把队列头和对列尾赋值尾空即可。
第二种：当队列有两个及两个以上的结点的时候，我们先保存队列头的下一个结点，然后free掉队列头即可。

//对头出
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	if (ps->head->next == NULL)//当队列只有一个结点时
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else//当队列有两个或者两个以上的结点时
	{
		QNode* next = ps->head->next;
		//free掉第一个结点时，先保存下一个结点
		free(ps->head);
		ps->head = next;
	}
}

🍀5.判断是否为空

在队列出的时候，我们出一个数据就要判断一下队列是否为空，如果为空，我们就不能出数据了。
我们还是和栈的判断空一样，使用bool值来判断。

//判断是否为空
bool QueueEmpty(Queue* ps) 
{
	assert(ps);
	return ps->head == NULL;
}

有了上面的代码我们就可以把出队列的数据给打印一下。

很明显这和队列的结构时一致的，即先进先出。 

🚲6.队列尾的元素

//尾的元素
QDataType QueueBack(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	return ps->tail->data;
}

🪂7.销毁队列

最后退出程序，我们再把队列给销毁一下。

//销毁队列
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;
		cur = next;
	}
	ps->head = ps->tail == NULL;
}

最后我们再把队列的功能给实现一下：

 

🌴三.队列的全部代码 

🌻1.Queue.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化
void QueueInit(Queue* ps);

//队尾插
void QueuePush(Queue* ps,QDataType x);

//队头出
void QueuePop(Queue* ps);

//头的元素
QDataType QueueFront(Queue* ps);

//尾的元素
QDataType QueueBack(Queue* ps);

//队列的元素个数
int QueueSize(Queue* ps);

//判断是否为空
bool QueueEmpty(Queue* ps);

//销毁队列
void QueueDestroy(Queue* ps);

🍌2.Queue.c：
 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

//初始化
void QueueInit(Queue* ps)
{
	assert(ps);
	ps->head = ps->tail = NULL;
}

//队尾入
void QueuePush(Queue* ps,QDataType x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc
");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if ( ps->tail == NULL)
	{
		ps->head=ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
}

//对头出
void QueuePop(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	if (ps->head->next == NULL)//当队列只有一个结点时
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else//当队列有两个或者两个以上的结点时
	{
		QNode* next = ps->head->next;
		//free掉第一个结点时，先保存下一个结点
		free(ps->head);
		ps->head = next;
	}
}

//头的元素
QDataType QueueFront(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	return ps->head->data;
}

//尾的元素
QDataType QueueBack(Queue* ps)
{
	assert(ps);
	assert(ps->head);
	return ps->tail->data;
}


//队列的元素个数
int QueueSize(Queue* ps)
{
	int count = 0;
	QNode* cur = ps->head;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

//销毁队列
void QueueDestroy(Queue* ps)
{
	assert(ps);
	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = ps->head->next;
		free(ps->head);
		ps->head = next;
		cur = next;
	}
	ps->head = ps->tail == NULL;
}

//判断是否为空
bool QueueEmpty(Queue* ps) 
{
	assert(ps);
	return ps->head == NULL;
}

🍈3.test.c：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{
	QNode q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("对于队列 1 2 3 4 出的数据为：
");
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	QueuePush(&q, 8);
	printf("
");
	printf("队列的元素为 5 6 7 8
");
	printf("队列头的元素为：
");
	int first = QueueFront(&q);
	printf("%d
", first);

	printf("队列尾的元素为:
");
	int tail = QueueBack(&q);
	printf("%d
", tail);

	printf("队列的元素的个数为：
");
	int count = QueueSize(&q);
	printf("%d
", count);


	QueueDestroy(&q);
	printf("退出程序
");
	printf("队列已经被销毁……
");
	return 0;
}