队列
1.队列的概念
队列 和栈一样，是一个 特殊的线性表。
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。进行 插入操作 的一端称为 队尾，进行 删除操作 的一端称为队头。
队列中的元素遵守 先进先出(First In First Out) 的原则。就和排队一样，队列是绝对公平的，先来的先到队头，不存在插队行为，只能后面排队，前面离开。
2.队列的结构
队列的结构可以用 数组 或 链表 来实现。哪个结构更好？
数组：
数组左边为队头右边为队尾：队尾(右)插入数据 为 顺序表尾插 很方便，但是 队头(左)删除数据 需要挪动数据，很麻烦。
数组左边为队尾右边为队头：队头(右)删除数据 为尾删，队尾(左)插入数据 需要挪动数据，也很麻烦。
所以 数组结构 并不适合队列。
链表：
结构选择：单/双 循环/非循环 带头/不带头
带不带头？可要可不要，带头就是方便尾插，少一层判断，没什么影响。
双向吗？没必要找前一个元素，队列只需要队头队尾出入数据。
循环吗？价值不大。双向循环可以找尾，但是没有必要。
双向链表：
可以使用双向链表，但是没必要，小题大做了，使用单链表就可以。
3.队列的实现
3.1结构设计
上面确定了用 单链表实现，所以就一定要有结构体表示 节点：
typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode;
由于链表的尾插比较麻烦，而队列的入数据为尾插。所以定义队列的结构体时，可以定义两个指针 head 和 tail 分别对应 队头 和 队尾 ，tail 的引入就是方便尾插，再在给定一个 sz 实时记录队列的 大小
typedef struct Queue { QNode* head; QNode* tail; int sz; }Queue;
大小
typedef struct Queue { QNode* head; QNode* tail; int sz; }Queue;
3.2接口总览
void QueueInit(Queue* pq); // 初始化 void QueueDestroy(Queue* pq); // 销毁 void QueuePush(Queue* pq, QDataType x); // 入队列 void QueuePop(Queue* pq); // 出队列 QDataType QueueFront(Queue* pq); // 取队头元素 QDataType QueueBack(Queue* pq); // 取队尾元素 bool QueueEmpty(Queue* pq); // 判空 int QueueSize(Queue* pq); // 计算队列大小
3.3初始化
队列初始化，就只需要结构中指针初始化为 NULL，并将 sz 初始化为0。
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->sz = 0; }
这里是通过结构体的地址来找到结构体中的两个指针，通过结构体来改变指针的。
3.4销毁
我们实现的队列结构为 链式 的，所以本质为一条 单链表。
那么销毁时，就需要迭代销毁链表的节点。
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; pq->sz = 0; }
3.5入队列
对于单链表的尾插，需要创建节点，找尾，然后链接。
但是我们设计队列结构时，给定了一个 tail 作为队尾，这时插入就比较方便了。但是需要注意一下 第一次尾插 的情况。
在 入队列 之后，记得调整 sz。
而且队列只会从队尾入数据，所以创建节点的一步，并没有必要封装一个接口专门调用，直接在函数中创建即可。
void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; //不置空newnode->next是随机值，会出问题 } // 尾插 if (pq->head == NULL) { assert(pq->tail == NULL); //头为空，尾却没为空，警告 pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->sz++; }
3.6 出队列
首先明确，队列为空不能出队列，出队列是从 队头 出数据。
其次，需要考虑删除时会不会有什么特殊情况。
一般删除时，可以记录 head 的下一个节点，然后释放 head ，再重新为 head 赋值。
但是，当 只有一个节点 呢？此刻 head == tail，它们的地址相同，如果此时仅仅释放了 head，最后head走到 NULL，但是tail 此刻指向被释放的节点，且没有置空，此刻风险就产生了，tail就变成野指针了。
之后一旦我 入队列 时，tail != NULL，那么必定就会走到 else 部分，对 tail 进行访问，此刻程序就会奔溃，所以需要处理一下，将 tail 也置空。
同样的，出队列 成功后 sz 需要发生调整。
void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); // 一个节点时删除的特殊情况 // 需要将头尾都变为空 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* newhead = pq->head->next; free(pq->head); pq->head = newhead; } pq->sz--; }
3.7取对头数据
队列非空，取 head 出数据
QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
3.8 取队尾数据
队列非空，取 tail 处数据。
QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
3.9 判空
当 head 和 tail 都为空指针时，说明队列中无元素。
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL && pq->tail == NULL; }
3.10 计算队列大小
从这个接口处，就可以看出设计结构时，设计的还是很精妙的，因为有 sz 直接返回即可。
int QueueSize(Queue* pq) { assert(pq); return pq->sz; }
试想一下，如果没有这个 sz，我们如何计算队列大小？是不是又得遍历链表了？这样接口的时间复杂度就为O(N)，而其他接口几乎都是O(1)的复杂度，是不是不太理想？所以结构设计时加上一个 sz 的效果是极好的！
下面贴上没有 sz 时的代码：
int QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; int size = 0; while (cur) { cur = cur->next; ++size; } return size; }
4. 完整代码
Queue.h
#pragma once #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int sz; }Queue; void QueueInit(Queue* pq); // 初始化 void QueueDestroy(Queue* pq); // 销毁 void QueuePush(Queue* pq, QDataType x); // 入队列 void QueuePop(Queue* pq); // 出队列 QDataType QueueFront(Queue* pq); // 取队头元素 QDataType QueueBack(Queue* pq); // 取队尾元素 bool QueueEmpty(Queue* pq); // 判空 int QueueSize(Queue* pq); // 计算队列大小
Queue.c
#include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; pq->sz = 0; } 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; pq->sz = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } else { newnode->data = x; newnode->next = NULL; //不置空newnode->next是随机值，会出问题 } // 尾插 if (pq->head == NULL) { assert(pq->tail == NULL); //头为空，尾却没为空，警告 pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->sz++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); // 一个节点时删除的特殊情况 // 需要将头尾都变为空 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* newhead = pq->head->next; free(pq->head); pq->head = newhead; } pq->sz--; } QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//防止空指针 return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); //return pq->size==0; return pq->head == NULL && pq->tail == NULL; } int QueueSize(Queue* pq) { assert(pq); return pq->sz; }
test.c
#include "Queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q,1); QueuePush(&q,2); QueuePush(&q,3); QueuePush(&q,4); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); system("pause"); return 0; }
7.总结：
今天我们认识并学习了队列的相关概念、结构与接口实现，并且针对每个常用的功能接口进行了实现。总体来说，链队列的结构相比于之前的数据结构是比较简单的，之后将介绍和讲解栈与队列的相关OJ题。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
