【数据结构】链队列的C语言实现_c链队列实现学生排队

队列

1.队列的概念

队列 和栈一样，是一个 特殊的线性表。

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。进行 插入操作 的一端称为 队尾，进行 删除操作 的一端称为队头。

队列中的元素遵守 先进先出(First In First Out) 的原则。就和排队一样，队列是绝对公平的，先来的先到队头，不存在插队行为，只能后面排队，前面离开。

2.队列的结构

队列的结构可以用 数组 或 链表 来实现。哪个结构更好？

数组：
数组左边为队头右边为队尾：队尾(右)插入数据 为 顺序表尾插 很方便，但是 队头(左)删除数据 需要挪动数据，很麻烦。
数组左边为队尾右边为队头：队头(右)删除数据 为尾删，队尾(左)插入数据 需要挪动数据，也很麻烦。
所以 数组结构 并不适合队列。

链表：
结构选择：单/双 循环/非循环 带头/不带头
带不带头？可要可不要，带头就是方便尾插，少一层判断，没什么影响。
双向吗？没必要找前一个元素，队列只需要队头队尾出入数据。
循环吗？价值不大。双向循环可以找尾，但是没有必要。

双向链表：
可以使用双向链表，但是没必要，小题大做了，使用单链表就可以。

3.队列的实现

3.1结构设计

上面确定了用 单链表实现，所以就一定要有结构体表示 节点：

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
1
2
3
4
5

由于链表的尾插比较麻烦，而队列的入数据为尾插。所以定义队列的结构体时，可以定义两个指针 head 和 tail 分别对应 队头 和 队尾 ，tail 的引入就是方便尾插，再在给定一个 sz 实时记录队列的 大小

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int sz;
}Queue;
1
2
3
4
5
6

看到这样的结构可能会有疑问：
1.为什么会有两个结构体？struct QueueNode是整体，是存数据和下一个节点链接的；struct Queue是局部，是头指针和存size的。
2.为什么不直接合并两个结构体呢？struct QueueNode是整体，struct Queue是局部，不能和在一起，同时也体现了使用数据结构的灵活性

3.2接口总览

void QueueInit(Queue* pq); // 初始化
void QueueDestroy(Queue* pq); // 销毁
void QueuePush(Queue* pq, QDataType x); // 入队列
void QueuePop(Queue* pq); // 出队列
QDataType QueueFront(Queue* pq); // 取队头元素
QDataType QueueBack(Queue* pq); // 取队尾元素
bool QueueEmpty(Queue* pq); // 判空
int QueueSize(Queue* pq); // 计算队列大小
1
2
3
4
5
6
7
8

3.3初始化

队列初始化，就只需要结构中指针初始化为 NULL，并将 sz 初始化为0。

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->sz = 0;
}
1
2
3
4
5
6
7

这里是通过结构体的地址来找到结构体中的两个指针，通过结构体来改变指针的。

3.4销毁

我们实现的队列结构为 链式 的，所以本质为一条 单链表。
那么销毁时，就需要迭代销毁链表的节点。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	
	QNode* cur = pq->head;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->sz = 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.5入队列

对于单链表的尾插，需要创建节点，找尾，然后链接。

但是我们设计队列结构时，给定了一个 tail 作为队尾，这时插入就比较方便了。但是需要注意一下 第一次尾插 的情况。

在 入队列 之后，记得调整 sz。

而且队列只会从队尾入数据，所以创建节点的一步，并没有必要封装一个接口专门调用，直接在函数中创建即可。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
		//不置空newnode->next是随机值，会出问题
	}

	// 尾插
	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		//头为空，尾却没为空，警告
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}

	pq->sz++; 
}
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
28
29
30
31
32

3.6 出队列

首先明确，队列为空不能出队列，出队列是从 队头 出数据。
其次，需要考虑删除时会不会有什么特殊情况。
一般删除时，可以记录 head 的下一个节点，然后释放 head ，再重新为 head 赋值。

但是，当 只有一个节点 呢？此刻 head == tail，它们的地址相同，如果此时仅仅释放了 head，最后head走到 NULL，但是tail 此刻指向被释放的节点，且没有置空，此刻风险就产生了，tail就变成野指针了。

之后一旦我 入队列 时，tail != NULL，那么必定就会走到 else 部分，对 tail 进行访问，此刻程序就会奔溃，所以需要处理一下，将 tail 也置空。

同样的，出队列 成功后 sz 需要发生调整。

void QueuePop(Queue* pq)
{
	assert(pq);

	assert(!QueueEmpty(pq));
	// 一个节点时删除的特殊情况
	// 需要将头尾都变为空
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* newhead = pq->head->next;
		free(pq->head);
		pq->head = newhead;
	}
	
	pq->sz--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.7取对头数据

队列非空，取 head 出数据

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}
1
2
3
4
5
6
7

3.8 取队尾数据

队列非空，取 tail 处数据。

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
1
2
3
4
5
6
7

3.9 判空

当 head 和 tail 都为空指针时，说明队列中无元素。

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL && pq->tail == NULL;
}
1
2
3
4
5
6

3.10 计算队列大小

从这个接口处，就可以看出设计结构时，设计的还是很精妙的，因为有 sz 直接返回即可。

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->sz;
}
1
2
3
4
5
6

试想一下，如果没有这个 sz，我们如何计算队列大小？是不是又得遍历链表了？这样接口的时间复杂度就为O(N)，而其他接口几乎都是O(1)的复杂度，是不是不太理想？所以结构设计时加上一个 sz 的效果是极好的！

下面贴上没有 sz 时的代码：

int QueueSize(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	int size = 0;
	while (cur)
	{
		cur = cur->next;
		++size;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4. 完整代码

Queue.h

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


typedef int QDataType;

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

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


void QueueInit(Queue* pq); // 初始化
void QueueDestroy(Queue* pq); // 销毁
void QueuePush(Queue* pq, QDataType x); // 入队列
void QueuePop(Queue* pq); // 出队列
QDataType QueueFront(Queue* pq); // 取队头元素
QDataType QueueBack(Queue* pq); // 取队尾元素
bool QueueEmpty(Queue* pq); // 判空
int QueueSize(Queue* pq); // 计算队列大小
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
28
29
30
31
32

Queue.c

#include "Queue.h"


void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->sz = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->sz = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
		//不置空newnode->next是随机值，会出问题
	}

	// 尾插
	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		//头为空，尾却没为空，警告
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}

	pq->sz++;
}

void QueuePop(Queue* pq)
{
	assert(pq);

	assert(!QueueEmpty(pq));
	// 一个节点时删除的特殊情况
	// 需要将头尾都变为空
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* newhead = pq->head->next;
		free(pq->head);
		pq->head = newhead;
	}

	pq->sz--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//防止空指针

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//return pq->size==0;
	return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->sz;
}


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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

test.c

#include "Queue.h"

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,1);
	QueuePush(&q,2);
	QueuePush(&q,3);
	QueuePush(&q,4);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
	system("pause");
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.总结：

今天我们认识并学习了队列的相关概念、结构与接口实现，并且针对每个常用的功能接口进行了实现。总体来说，链队列的结构相比于之前的数据结构是比较简单的，之后将介绍和讲解栈与队列的相关OJ题。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~