【数据结构】队列

---

1.队列的概念及结构

队列：队列也是一种特殊的线性表，只允许在一端进行插入数据操作，在另一端进行删除数据操作。队列具有先进先出FIFO（First in First Out）的原则。
队尾（入队列）：进行插入操作的一端称为队尾
队头（出队列）：进行删除操作的一端称为队头
在我们的生活中，如银行窗口的叫号排队，核算检测排队跟队列的结构一个道理，先进先出。

2.队列的实现

2.1队列的实现思路

队列可以使用数组实现，也可以使用链表实现，因为队列的原则是先进先出，采用的是头删，尾插，所以用单链表实现更优一些。

2.2队列的结构体定义

//队列(链表)的结点结构
typedef struct QueueNode
{
	QDataType data;//数据域
	struct QueueNode* next;//指针域
}QNode;//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
16
17

2.3函数接口（功能）

void QueueInit(Queue* pq);——队列初始化
void QueueDestroy(Queue* pq);——销毁队列
void QueuePush(Queue* pq);——入队数据(尾插)
void QueuePop(Queue* pq);——出队数据(头删)
QDataType QueueFront(Queue* pq);——获取队头数据
QDataType QueueBack(Queue* pq);——获取队尾数据
bool QueueEmpty(Queue* pq);——判断队列是否为空，不为空，才能头删，不为空，才能打印队列中的数据
int QueueSize(Queue* pq);——记录队列数据个数

2.4头文件Queue.h

#pragma once
#include
#include
#include
#include

typedef int QDataType;

//队列(链表)的结点结构
typedef struct QueueNode
{
	QDataType data;//数据域
	struct QueueNode* next;//指针域
}QNode;//QNode是结点类型

//队列结构
//将头指针和尾指针，用队列的结构体封装起来
//这样可以避免使用二级指针
typedef struct Queue
{
	QNode* head;//头指针指向队头(要被头删的数据)
	QNode* tail;//尾指针指向队尾

	int size;//便于统计队列数据个数
}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
33
34
35
36
37
38
39
40
41
42

2.5函数实现Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Queue* pq)//队列初始化
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 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;
	}
	//若一开始为空队列
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
void QueuePop(Queue* pq)//出队数据(头删)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//注意这个时候tail指向最后一个结点
	//Pop头删的时候，不要让tail沦为野指针

	if (pq->head->next == NULL)//只剩下最后一个结点时，为了避免tail沦为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		//迭代
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
	pq->size--;
}
void QueueDestroy(Queue* pq)//销毁队列
{
	assert(pq);
	//释放所有结点的空间，还给操作系统
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pq->head = pq->tail = NULL;
}
bool QueueEmpty(Queue* pq)//判断队列是否为空，不为空，才能头删，不为空，才能打印队列中的数据
{
	assert(pq);
	//当头指针和尾指针为空时，队列为空
	return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)//记录队列数据个数
{
	assert(pq);
	return pq->size;
}
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;
}
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

2.6测试函数Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;//先创建一个队列
	QueueInit(&q);
	/*QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);*/

	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);

	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 4);
	QueuePush(&q, 4);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}
int main()
{
	TestQueue();
	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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38