【数据结构之队列系列】队列详解_数据结构中队列

前言

前面我们学习了一种数据结构：栈，栈是一种只允许在一端尽进行插入删除的数据结构，而今天我们将学习另一种数据结构：队列，队列是一种支持在一端进行插入，在另一端进行删除的数据结构。

一、队列的介绍

队列是一种支持在一端进行插入，在另一端进行删除的数据结构，相当于尾插和头删，入队列的一端我们称之为队尾，出队列的一端我们称之为对头。

• 入队：向队列插入元素的操作，只能从队尾插入元素
• 出队：对队列进行删除元素的操作，只能从队头删除元素
• 基于队列上面的性质，队列的特点是先进先出的。这个需要和栈的后进先出区分开。

二、队列数据类型的重定义

与前面学习的数据结构一样，为了能够方便修改队列存储的数据类型，我们需要队数据类型进行重定义

三、队列的结构

因为队列中需要进行入队和出队，即尾插和头删，头删数组就不太方便了，因为数组的头删需要挪动后面的数据，效率比较低，所以采用链表的形式来实现队列。为了效率，我们需要准备两个指针来管理整个队列，因为我们需要对这个队列进行头删和尾插，所以需要两个指针分别标识队列的头结点和尾结点。实现链表的形式的队列，那么我们首先需要确定链表的结点的结构

1. 队列中链表的结点的结构
   
   和普通链表一样，队列中的链表同样需要存储数据，所以需要一个数据域，每一个结点需要找到其下一个结点，因此需要一个指针域指向每一个结点的下一个结点
   为了后面方便表示，我们同样可以对这个结点的结构进行重定义
   
2. 队列中的头指针和尾指针
   因为这是两个指针，所以我们可以考虑将这两个指针封装称为一个结构体，叫做队列Queue.也就是一个队列只需要知道其头结点和尾结点，那么我们就可以对这个队列进行操作了
   
   同样的道理，为了后续方便表示，我们可以对这个结构进行重定义
   

四、队列常见的基本操作

1. 声明

// 基本操作的声明、

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

// 销毁队列
void QueueDestroy(Queue* pq);

// 入队
void QueuePush(Queue* pq, QDataType val);

// 出队
void QueuePop(Queue* pq);

// 判空
bool QueueEmpty(Queue* pq);

// 队头元素
QDataType QueueFront(Queue* pq);

// 队尾元素
QDataType QueueBack(Queue* pq);

// 队列结点个数
size_t 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

在上面的函数声明中，我们发现函数的参数传的是队列结构体的地址，而不是结构体本身，道理和栈中的传参是一样的，首先可以节省空间，其次，我们需要在函数中通过这个队列的结构体指针找到队列的队头指针和队尾指针，如果传的是结构体，那么传参的过程是一次深拷贝，形参是实参的一份临时拷贝，这是两份不同的数据了，通过形参结构体找到的队头指针和队尾指针和实参的队头指针和队尾指针不是同一份数据，因此我们传的是队列的结构体指针。

2. 定义

• 初始化

// 初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6

因为队列中有两个指针，所以我们需要对队列进行初始化，防止队列的两个指针变成野指针，初始化就是将队列的两个指针置成空指针

• 销毁队列

// 销毁队列
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;
}

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

这个思路和销毁链表的思路是一样的，需要遍历队列中的每一个结点，然后依次进行释放结点空间，最终将队列的头指针和尾指针置成空指针即可。

• 入队

// 入队
void QueuePush(Queue* pq, QDataType val)
{
	assert(pq);
	// 申请新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		return;
	}
	newnode->val = val;
	newnode->next = NULL;

	// 入队
	if (pq->tail == NULL)
	{
		// 第一次入队
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->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
24
25
26
27
28

入队的步骤，首先申请空间创建新节点，在入队的时候因为这个队列的链表是没有头结点的，所以在入队的时候需要判断是否为第一次入队，如果是第一次入队，则需要同时将头指针和尾指针指向这个结点，即第一个结点，如果不是第一次入队，则只需要将尾指针的下一个更新为新插入的元素（结点），然后更新尾指针即可。

• 出队

// 出队
void QueuePop(Queue* pq)
{
	assert(pq);
	// 删除操作一定要判断是否为空
	assert(pq->head);
	// 删除结点
	// 先保存下一个位置
	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
}
1
2
3
4
5
6
7
8
9
10
11
12

出队的时候即删除元素的时候一定要检查队列是否为空，如果队列为空，是不能删除元素的，队列的删除元素的方式和链表删除元素的方式是一样的，先保存第二个结点，再删除第一个结点，再更新第二个结点为新的第一个结点。

• 判空

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

当队列中的头指针为空的时候队列就是空的

• 返回队头元素

// 队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->val;
}
1
2
3
4
5
6
7

• 返回队尾元素

// 队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->val;
}
1
2
3
4
5
6
7

这两个函数接口需要注意判断队列是否为空，如果队列为空，则队列中没有元素，是不能返回队头元素和队尾元素的

• 队列元素个数

int QueueSize(Queue* pq)
{
	if (pq->head == NULL)
	{
		return 0;
	}
	int count = 1;
	QNode* cur = pq->head;
	while (cur!=pq->tail)
	{
		cur = cur->next;
		count++;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意此时count的初始值，当count初始值为0时，需要从头遍历到空，当count的初始值为1时，只需要遍历到尾结点即可。

五、遍历队列

1. 代码

void test_queue5()
{
	// 遍历队列
	Queue q;
	// 初始化
	QueueInit(&q);
	// 入队
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	printf("此时队列的队头元素为：%d\n", QueueFront(&q));
	printf("此时队列的队尾元素为：%d\n", QueueBack(&q));
	printf("此时队列元素个数为：%d\n", QueueSize(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	printf("此时队列元素个数为：%d\n", QueueSize(&q));
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2. 结果
   
3. 思路分析
   遍历队列需要一个循环来实现，当队列不为空时，先访问队头元素，再删除队头元素（入队），知道队列为空时退出循环。