第六章 队列的讲解与实现

初阶数据结构

第一章 时间复杂度和空间复杂度
第二章 动态顺序表的实现
第三章 单向链表的讲解与实现
第四章 带头双向链表的讲解与实现
第五章 栈的讲解与实现
第六章 队列的讲解与实现

---

---

前言

在上一章节中，我们了解到栈这种数据结构的特点是先进后出，那么今天所讲解的队列的特点则恰恰与之相反。队列这种数据结构的特点是：先进先出，后进后出。接下来我们将对其进行详细地讲解。

---

一、什么是队列？

队列在生活中是非常常见的，比如我们做核酸的时候，都会以队列的形式排队。很明显，先排队的人就可以先做核酸，后排队的人只能后做核酸。这其实就是队列这种结构的特点，那么其逻辑结构如下图所示：

二、队列的定义：

typedef int ElementType;

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

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

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

在上述的定义中，我们先定义了队列中的元素，很明显可以看出我们是用链表的形式来实现队列结构的。其实原因很简单，队列涉及头删的问题，而顺序表中头删的时间复杂度是O(N)。很明显，顺序表实现队列的效率是非常低的。所以，我们采用链表的形式。
当我们定义好节点之后，我们再来看队列这种数据结构。这种结构中最重要的其实就是尾插和头删这两种功能。而我们在前面的章节中学习单向链表的时候，我们发现，每次尾插的时候都需要寻找尾部节点。该过程的是将复杂度是O(N)。其效率是很低的。因此，我们可以实现定义一个尾指针来记录尾部节点。因此我们就有了另外一个关于队列的结构体，这个结构体中定义了两个变量，一个是头指针，一个是尾指针。

三、接口函数的实现：

1、初始化：

队列的初始化非常简单，就是将两个指针都指向空指针即可。

void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
}
1
2
3
4
5
6

2、判断是否为空：

头指针指向的是第一个元素，那么如果头指针指向的是空，那么这个队列就为空。

	assert(q);
	if (q->head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
1
2
3
4
5
6
7
8
9

3、插入：

队列的插入方式是尾插，在单向无头链表中尾插需要考虑空队列的情况。
第一种情况：队列不为空
这种情况下，我们需要做两件事情，一件事是将当前的尾节点的指针域指向新的节点，第二件事就是更新我们的尾指针，让我们的尾指针指向我们新的尾部节点。

第二种情况：队列为空：
这种情况下，我们也需要做两件事情，
第一件事是将头指针指向新的节点，由于只有一个节点，所以这个节点即使尾部，也是头部。
所以第二件事，就是将尾指针也指向新的节点。

void QueuePush(Queue* q,ElementType dat)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("Failed to creat new space!\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = dat;
	if (q->tail != NULL)
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	else
	{
		q->head = newnode;
		q->tail = newnode;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、删除：

删除分为三种情况，
第一种情况：
队列不为空，此时我们需要先释放头节点，然后将头指针向后移动一个位置，更新头部指针。

第二种情况：
队列为空的时候，我们是不需要删除的，如果我们强行删除的话，会出现访问野指针的情况。

第三种情况：
队列中只有一个元素。（这种情况最需要注意！！！）避免野指针！！！

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* nex = q->head->next;
	free(q->head);
	q->head = nex;
	if (q->head == NULL)//非常关键的判断！！！！
	{
		q->tail = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

5、访问队头：

这个函数就很简单了，先判断一下队列是否为空，如果不为空则返回头节点的数据。

ElementType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
1
2
3
4
5
6

6、访问队尾：

思路和访问队头的思路一样。

ElementType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
1
2
3
4
5
6

7、元素个数：

元素个数的计算有两种方法，第一种方法是我们在队列的结构体中创建一个变量来记录个数。另外一种方式就是遍历一遍整个队列。
遍历的方法就是，我们创建一个cur指针指向头部，然后偏移cur。

int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QueueNode* cur = q->head;
	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12

8、销毁：

销毁的逻辑和链表中的销毁函数的思路是一致的。
但是最后别忘了将头指针和尾指针设置为空，避免野指针的出现。

void QueueDestory(Queue* q)
{
	assert(q);
	QueueNode* cur = q->head;
	while (cur != NULL)
	{
		QueueNode* nex = cur->next;
		free(cur);
		cur = nex;
	}
	q->head = NULL;
	q->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

四、队列中元素的访问：

由于队列中的元素满足先进先出，后进后出的特点，所以我们只能访问头尾，想要访问第二个元素，必须删掉队头才行。因此，我们就可以结合上面的接口函数，模拟队列的实现。

#include"Queue.h"
void TestQueue1()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	ElementType front = QueueFront(&q);
	printf("%d ", front);
	QueuePop(&q);

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

	while (!QueueEmpty(&q))
	{
		ElementType front = QueueFront(&q);
		printf("%d ", front);
		QueuePop(&q);
	}
	printf("\n");
}
int main()
{
	TestQueue1();
	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