数据结构——队列（Queue）

目录

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.队列总结反思

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