队列（C语言实现）

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的特点，入队列：进行插入操作的一端称为队尾，出队列：进行删除操作的一端称为队头

2.队列的结构

队列也可以数组和链表的结构实现，由于队列先进先出的特点，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，需要挪动后面的数据，效率会比较低，而链表头部的插入删除是很快的

//数据类型
typedef int QDataType;
//队列结点数据
typedef struct QueueNode
{
	QDataType data;//数据（数值域）
	struct QueueNode* next;//指向下一个结点的指针（指针域）
}QNode;
//整个队列数据
typedef struct Queue
{
	QNode* head;//指向对头
	QNode* tail;//指向对尾
	int size;//数据个数（队列长度）
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里是使用结构体嵌套，方便我们出队入队时修改队头和队尾结点，我们直接上图理解：
链式队列结构图示：

3.接口实现

3.1初始化队列

将头尾指针置空，避免成为野指针，再将数据个数置零，方便后面统计时累加，这里断言pq是为了避免人为不小心传了空指针进来

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8

3.2判断队列是否为空

当队头指针和队尾指针都指向NULL时，说明队列就是空队，当然也可以使用队长size为0来判断

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
   //头尾指针都指向NULL时为空队
	return pq->head == NULL && pq->tail == NULL;
}
1
2
3
4
5
6
7

3.3入队

入队操作就是单链表的尾插，首先创建一个新结点存入目标值，如果是空队的情况就直接将新节点赋值给头尾结点指针，通常情况先将尾结点指向新节点，再将队尾指针指向新节点即可，同时队列长度+1，这里因为需要修改队头或队尾，所以传Queue结构体指针

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)//判断申请空间成功
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队为空的情况
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//通常情况（尾插）
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	//队列长度+1
	pq->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.4出队

出队操作就是单链表的头删，这里首先要断言队列为空的情况，队空不能出队，再就是最后一个元素出队时我们直接释放掉队头指针并将队头指针和队尾指针都置空（避免野指针），通常情况先记录队头指针，再将队头指针指向其下一个成为新的队头指针，最后释放掉记录的原队头指针即可，同时队长-1

//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	//断言队列为空
	assert(!QueueEmpty(pq));
	//最后一个元素出队
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//通常情况（头删）
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		//del = NULL; 局部变量没必要置空
	}
	//队长-1
	pq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.5查看队头元素

首先需要断言队列为空的情况，为空无队头元素，然后直接返回队头结点指向的数值域即可

//查看队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//返回队头结点指向的数值域
	return pq->head->data;
}
1
2
3
4
5
6
7
8

3.6查看队尾元素

首先也需要断言队列为空的情况，为空无队尾元素，然后直接返回队尾结点指向的数值域即可

//查看队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//返回队尾结点指向的数值域
	return pq->tail->data;
}
1
2
3
4
5
6
7
8

3.7统计队列数据个数

这里size就是队列内的有效数据个数，我们直接将其返回即可

//统计队列数据个数
int QueueSize(Queue* pq)
{
	assert(pq);
	//返回size即可
	return pq->size;
}
1
2
3
4
5
6
7

3.8销毁队列

队列的销毁类似单链表，从队头结点开始循环依次销毁所有节点即可，这里我们也是先记录遍历指针的位置，然后将遍历指针移动到下一个结点，最后释放掉先前记录的节点，最后将队头指针和队尾指针都置空（防止野指针），再将size置零就完成了

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	//从队头开始遍历销毁
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;//置空
	pq->size = 0;//置零
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

队列的实现到这里就介绍结束了，期待大佬们的三连！你们的支持是我最大的动力！
文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正。