数据结构——队列（Queue）
目录
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
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！