数据结构——队列(Queue)

发布时间:2024年01月08日

目录

1.队列的介绍

2.队列工程

2.1 队列的定义

2.1.1 数组实现队列

2.1.2 单链表实现队列

2.2 队列的函数接口

2.2.1 队列的初始化

2.2.2 队列的数据插入(入队)

2.2.3 队列的数据删除(出队)

2.2.4 取队头数据

2.2.5 取队尾数据

2.2.6 判断队列是否为空

2.2.7 队列长度统计

2.2.8 队列的销毁

?3.队列总结反思


1.队列的介绍

? ? ? ? 队列,顾名思义,作为有素质的新时代公民,在现实生活中我们常常会遇到排队的场景,而队列就是借此种情形衍生出来的数据结构形式。在需要排队的时候,我们面对一个队列会自觉地站在队尾。随着当队伍中的人慢慢出队,我们的位置也从队尾慢慢移动到了队头,当我们成为一个队的第一个人时,我们就明白终于轮到我们出队了。队列这种数据结构组织数据的形式和排队的场景十分相似,均为先进先出,后进后出的规则。

? ? ? ? 在掌握了栈这种数据结构的基础之上,我们再来学习队列会比较轻松。栈主要实现的是“先进后出,后进先出”的规则,而队列遵循的则是“先进先出,后进后出”的规律。因此我们可以相互类比地进行学习。

2.队列工程

2.1 队列的定义

? ? ? ? 在创建队列之前,我们需要考虑队列用什么方式实现。我们依然从数组和链表两种结构去考虑优劣,我们发现队列在出队和访问时需要访问队头,在入队时需要找到队尾,所以我们根据这一特征仔细分析一下队列最合适的实现方式。

2.1.1 数组实现队列

? ? ? ? 当我们打算用数组实现队列的时候:

????????如果以下标小的一端为队头,我们发现在入队时,我们很容易可以在队尾插入数据。但是在出队的时候,类似于顺序标的头删操作,所有数据前移一位,需要O(n)的时间复杂度。

? ? ? ? 如果以下标大的一端为队头,在出队是很容易。但是在入队时同样需要依次挪动数据,也导致了O(n)的时间复杂度。

2.1.2 单链表实现队列

? ? ? ? 当使用单链表的时候,头删头插数据很容易,但是尾插尾删因为需要遍历链表找尾而变得复杂。这是我们只需要再引入一个指针指向单链表的尾即可解决这个问题。因为将单链表用作队列的时候,队列只会对队头和队尾进行操作,所以无论哪一边为队头,队列实际操作的都只有链表的头结点和尾结点,所以我们只需要定义指针指向头和尾即可避免遍历的冗余操作。

? ? ? ? 弄明白这一点后,我们再来详细讨论一下到底以单链表的哪一边为队头,哪一边为队尾。

? ? ? ? 如果以单链表头结点为队头,以尾结点为队尾。在入队的时候我们需要将数据插入队尾,也即在尾结点后插入数据,因为我们提前存储了尾结点位置,所以可以直接将新结点链接在尾结点后。在出队的时候,就相当于删除队头的结点,也就是单链表头删,也没有问题。看来这种方案是个不错的选择。

? ? ? ? 如果以单链表头结点为队尾,以尾结点为队头。那么在入队的时候,我们需要将数据插入队尾,也就是单链表头插,我们可以做到直接链接。在出队的时候,我们需要删除队头的数据,即单链表尾删,熟悉单链表的小伙伴们都知道,单链表尾删是需要尾结点前一个结点的(需要改变倒数第二个结点的next,使其为空指针),所以在选取这种方式时,我们使用指针指示的就不该是尾结点了,而应该是尾结点的前一个结点。

? ? ? ? 在这篇博客中,我们采取第一种方式(单链表头结点为队头,以尾结点为队尾)。

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

? ? ? ? 首先定义出单链表的结点结构体,然后再定义出队列的结构体,队列结构体之中看似有三个成员,实际上都是对队列载体——单链表的信息描述,分别是链表头结点(队头),链表尾结点(队尾),链表节点个数(队列长度)。

2.2 队列的函数接口

2.2.1 队列的初始化

? ? ? ? 新建了一个队列后,我们首先需要对其进行初始化,将队列结构体中队头、队尾指针置空,将size置为0。

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.2.2 队列的数据插入(入队)

? ? ? ? 通过我们刚才的分析,入队可以简单的视为尾插,所以我们按照尾插的逻辑来写入队函数即可。

????????首先需要开辟空间创建新结点,然后熟悉单链表的小伙伴又知道了,在我们链接结点之前需要对特殊情况进行特殊处理。一般而言,单链表的特殊情况就是空链表和只有一个结点的链表。当链表为空时,队列中phead和ptail指针均为空指针,直接链接肯定会出错,所以当为空链表时,需要特殊处理一下。当链表仅有一个结点时,其ptail就是尾结点,所以不需要特殊考虑,和其余情况一样,可以直接链接。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->next = NULL;
	newnode->val = x;

	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

2.2.3 队列的数据删除(出队)

? ? ? ? 出队操作在这里就相当于头删。对于删除操作我们要做最基本的判断排除空链表的情况,这里我使用了assert断言。然后考虑特殊情况,当链表只有一个结点时,头删后链表为空,队头指针和队尾指针都需要置空,其余情况都是只需要改变队头指针即可。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	QNode* del = pq->phead;
	if (pq->phead == pq->ptail)
	{
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		pq->phead = pq->phead->next;
	}
	free(del);
	del = NULL;

	pq->size--;
}

2.2.4 取队头数据

????????很简单的操作,取出队头指针所指结点的保存的值即可。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

2.2.5 取队尾数据

? ? ? ? 取队尾数据在某些场景下会被使用,其方法和取队头数据一样。

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}

2.2.6 判断队列是否为空

? ? ? ? 队列为空的特征很多,包括队头指针、队尾指针为空,队列长度为0,任取一个作为判断依据即可。

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

2.2.7 队列长度统计

? ? ? ? 队列的长度由成员size指出,将其作为返回值即可。

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

2.2.8 队列的销毁

? ? ? ? 队列实际上是一个链表+一个记录链表信息的结构体,所以在销毁链表的时候,我们需要按照销毁单链表的方式先释放单链表所占用的空间,然后将记录信息的结构体其中的值置0、指针置空,防止野指针。

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* tmp = cur;
		cur = cur->next;
		free(tmp);
		tmp = NULL;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

?3.队列总结反思

? ? ? ? 栈和队列都是比较简单的数据结构,分别采取数组和链表实现了“先进后出,后进先出和“先进先出,后进后出”的功能。只要能熟练的控制应用单链表,我觉得队列应该不在话下。队列在具体实际中的用途也很广泛,在广度优先搜索中队列会作为数据存储方式,对所有出现的情况进行记录与拓展。

文章来源:https://blog.csdn.net/XLZ_44847/article/details/135460720
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。