数据结构——队列（C语言实现）_c语言队列

队列的概念与结构

队列是一种特殊的线性结构，数据只能在一端插入，数据也只能在另一端进行删除。插入数据的那一端称之为队尾，插入数据的动作称之为入队。删除数据的那一端称之为队头，删除数据的动作称之为出列。队列遵守的是FIFO原则（Frist In First Out），即先进先出原则。

队列具体实现结构比较灵活，只要遵循FIFO原则即可。顺序表的方式实现，虽然尾插数据方便，头删的代价较大，故不推荐。单链表的方式实现，头删数据方便，只需要添加一个记录尾结点的指针，进行尾插数据的效率也还可以。所以本篇文章将以单链表的方式来实现队列。

队列的特点

由于队列是FIFO的原则，这就类似于去食堂排队打饭，先排队的就一定先吃上饭。而队尾的就得等先排队的打完饭了，才有机会吃饭。所以队列无论是变入列变出列，还是全部入列后再出列，结果是一样的。这和栈的LIFO原则有些许不同。

队列的实现

队列的定义

首先，我们需要定义的是链式结构的队列，即单链表为底层实现的。所以需要定义单链表结构来存储数据。然后，定义队列，队列里需要定义两个指向单链表的指针，一个是指向单链表头结点的指针，另一个则用来保存尾结点地址的指针。最后，还需定义一个记录当前队列元素个数的变量，用于遍历队列和判空。

typedef int QueueDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

初始化队列

首先，断言判断一下指针合法性。然后，需要将队列内两个指针变量初始化。最后，将记录队列有效元素个数的变量初始化一下。

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);

	//初始化
	q->head = q->tail = NULL;
	q->size = 0;
}
1
2
3
4
5
6
7
8
9

队列销毁

首先，断言一下指针有效性。然后，依次释放每个结点。最后释放最后一个结点时，把tail和head置空，size置零。

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);

	//释放结点
	while (q->head)
	{
		QueueNode* next = q->head->next;
		if (q->tail != q->head)
		{
			free(q->head);
			q->head = next;
		}
		else
		{
			//避免野指针
			free(q->head);
			q->head=q->tail = NULL;
		}
	}
	//手动置零
	q->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

队列判空

由于在定义队列时，增加了额外的记录当前有效数据个数的变量，所以这里直接返回该变量与0比较的值即可。

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
	return q->size == 0;
}
1
2
3
4
5

数据入队

首先，依旧断言判断指针有效性。其次，就是动态开辟结点，并对新节点初始化。然后，进行头插操作，记得第一次插入时，需要单独判断两个指针同时指向新结点。最后，记得让tail指针指向最后一个结点和size++。

// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
	//断言判断指针有效性
	assert(q);

	//开辟结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newnode)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;


	//插入数据
	//空队列插入数据
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	//非空队列插入数据
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}

	q->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
28
29
30
31
32

数据出列

首先，当队列为空时，不能进行删除操作，所以断言判断一下是否为空队列。然后，就是头删链表的操作，需要注意的是当只剩一个结点时，对tail进行特殊处理避免野指针。最后，就是让记录有效元素的size–一下。

// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	//空队列无法删除数据
	assert(!QueueEmpty(q));


	//只有一个数据
	if (q->head == q->tail)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		//先保存下一个结点
		QueueNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}

	//记录当前数据个数
	q->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

获取有效数据个数

由于在定义队列时，定义了一个记录当前有效元素个数的变量，所以这里直接返回该变量当前的值即可。

// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);

	return q->size;
}

1
2
3
4
5
6
7
8

获取队头数据

直接返回第一个结点的data即可。

// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

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

获取队尾数据

直接返回tail指针指向的链表存放的数据即可。

// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->tail->data;

}
1
2
3
4
5
6
7
8
9

完整代码

//头文件

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

typedef int QueueDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
}QueueNode;

typedef struct Queue
{
	struct QueueNode* head;
	struct QueueNode* tail;
	int size;
}Queue;


// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
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

//源文件

#include"Queue.h"

// 初始化队列
void QueueInit(Queue* q)
{
	//断言判断指针有效性
	assert(q);

	//初始化
	q->head = q->tail = NULL;
	q->size = 0;
}

// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{
	//断言判断指针有效性
	assert(q);

	//开辟结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newnode)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->next = NULL;
	newnode->data = data;


	//插入数据
	//空队列插入数据
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	//非空队列插入数据
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}

	q->size++;
}



// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	//空队列无法删除数据
	assert(!QueueEmpty(q));


	//只有一个数据
	if (q->head == q->tail)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QueueNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}

	//记录当前数据个数
	q->size--;

}


// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->head->data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));

	return q->tail->data;

}


// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);

	return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
	return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);

	//释放结点
	while (q->head)
	{
		QueueNode* next = q->head->next;
		if (q->tail != q->head)
		{
			free(q->head);
			q->head = next;
		}
		else
		{
			//避免野指针
			free(q->head);
			q->head=q->tail = NULL;
		}
	}
	//手动置零
	q->size = 0;
}
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133