数据结构：队列

一.队列的概念和结构：

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

结构：一般情况下，队列我们用链表来实现，因为如果用顺序表来表示在出队列的时候，删除第一个元素后，后面的元素都要往前移，这样效率就没那么高了。

但是用链表来表示的话，入队还需要遍历才能找到队列的末尾。所以我们比之前写队列的时候多定义两个指针：head,tail一个指向队头，一个指向队尾。

所以定义一个队列，这里来定义两个结构体：

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
16

二.队列的实现

2.1队列的初始化

//初始化
void QueueInit(Queue* pq)
{
	//在进来之前要先判断指针是否为空
	assert(pq);

	//在刚开始的时候，因为没有任何元素
	//两个指针应该都指向空，size的大小也是0
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11

2.2队列的销毁

//删除
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->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里定义一个指针cur来向队列后面遍历：
和链表的销毁一样先保存cur下一个节点的位置：
然后把cur指向的空间释放掉，然后cur指向next的位置，next继续指向下一个节点的位置：
最后再把两个指针置空，size的大小置为0.

2.3判断队列是否为空

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}
1
2
3
4
5
6
7

直接判断size大小是否为0，是的话说明为空，pq->size == 0结果为真返回true，否则返回false.

2.4入队列

//入对列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//新创建一个节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
	//节点的初始化
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	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

在插入新节点之前要新创建一个节点的空间。创建好之后把新节点的next默认设为空，data则设置为x。

插入一个节点很简单：
因为我们已经知道队尾的指针，所以直接将tail->next = newnode就行，随后tail往后挪动，因为tail永远指向的是队尾

但是还要考虑一下特殊条件：
如果此时head指针为空，说明此时队列还没有任何节点，如果对这种情况不管不顾的话pq->tail->next这一步就会造成空指针的解引用。所以我们要根据这种情况单独写一段代码。

pq->head = pq->tail = newnode;
1

tail,head同时指向这个新节点。

2.5出队列

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

出队列要在头部出：
定义一个next指针指向头指针的下一个位置，这样在释放第一个节点的空间时还能找到第二个节点：
释放掉head指向的节点后，head指向新的头部：
但是假如一直删一直删，删到只剩一个节点的时候，会发现此时如果把最后一个节点删掉后然后把head置空，但是此时tail指针却没有变化，也就意味着此时tail指针指向的最后一个节点释放了然后tail指针变成了野指针。
所以再删到最后一个节点的时候要单独拎出来：

free(pq->head);
pq->head = pq->tail = NULL;
1
2

我们手动调成空指针。

2.6取出队尾数据

//取出队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

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

将tail指针指向的最后一个数据返回即可，但是这里要考虑一个特殊情况，如果此时队列数据为空，在取数据就没意义了，所以这里断言一下判断。

2.7取出队列头数据

//取出队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

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

和取出队尾数据一样，这里不做过多强调了。

2.8队列元素大小

//队列大小
QDataType QueueSize(Queue* pq)
{
	assert(pq);

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

直接返回size的大小。

三.代码

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

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

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 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->size = 0;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

//入对列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == 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));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//取出队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

//取出队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

//队列大小
QDataType QueueSize(Queue* pq)
{
	assert(pq);

	return 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
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