欢迎来到 Claffic 的博客 💞💞💞 

“海色温柔，波浪缓慢，似乎在静静期待着新的一天。”

前言：
上期我们讲了栈，它的特点是“后入先出”。这次我们再来学习一个新的数据结构：队列，它的特点是“先入先出，后入后出”，准备好了吗？开始！ 

Part1: 何为队列 

1.队列的概念 

 队列队列，顾名思义，就像排队买饭，排在前面的人买到饭先走，排到后面的人需要等待... ...

下面是队列的正经概念： 

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出原则(First In First Out) 。

进行插入操作的一端称为 队尾，

进行删除操作的一端称为 队头。

嗯，还是蛮好理解的。

2.队列的结构

它的结构也很清晰了：

我是图示 

Part2: 队列的实现 

1.前期准备

1.1创建项

不解释：

Queue.h：头文件，声明所有函数；

Queue.c：源文件，实现各函数；

Test.c：  源文件，主函数所在项，可调用各函数。

1.2队列结构

仍然是那个问题：用什么结构来实现队列较好？

数组：？删除元素要整体移动，时间复杂度高，且动态扩容比较麻烦，不推荐；

链表：插入删除数据后无需修改中间部分的元素，方便在队头和队尾操作，推荐。

那么选双链表还是单链表呢？

若选择双链表，的却方便找尾，但是仅仅为了找尾方便而选择它，未免会显得臃肿；

选择单链表呢，轻巧简洁，只需解决找到尾部的问题即可，有一个巧妙的方法就是：

在队列的结构中 定义尾指针 。

我们捋一遍： 

就队列的整体来说：需要首尾指针和大小（长度）；

就队列中的一个结点来说：需要下一个结点的指针和要存储的数据。

欸？相比栈来说，是不是结构更加复杂了？

是的，这意味着要多定义一个结构体，两个结构体之间是包含关系：

我是图示 

上代码：

typedef int QDataType;
//队列中的结点
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
//队列整体
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;

1.3队列初始化 

要从整体上把握，把首尾指针初始化为空，大小初始化为 0 即可：

// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
 
pq->head = pq->tail = NULL;
pq->size = 0;
}

2.功能实现

2.1队头出队列

队头出队列，队列中是一定至少有一个结点的，但其实还是要分两种情况考虑的： 

一是只有一个结点，直接把这个结点释放掉，再将首尾置空即可；

二是有两个及以上个结点，除了释放头部的结点，还需要把队头指针指向下一个结点；

最后莫忘大小减一。

// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);
 
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
//pq->head = NULL;
pq->head = next;
}
pq->size--;
}

2.2队尾入队列

要入队列，首先要先申请一个新的结点（注意是结点，不是队列）；

再申请完并初始化后，就需要插入了：

也是两种情况：

一是链表为空，此时只要将首尾指针修改为新结点指针即可；

二是链表不为空，就要用到尾指针，将尾结点的下一个结点修改为新结点，并且更新尾结点指针；

最后莫忘大小加一。

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
 
QNode* tailNode = (QNode*)malloc(sizeof(QNode));
if (tailNode == NULL)
{
perror("malloc fail");
return;
}
tailNode->next = NULL;
tailNode->data = x;
 
if (pq->head == NULL)
{
pq->head = pq->tail = tailNode;
}
else
{
pq->tail->next = tailNode;
pq->tail = tailNode;//掉
}
pq->size++;
}

2.3获取队列头部元素

进行了插入操作，当然要看看数据怎么样啦

这个比较简单，直接返回头部数组即可

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
 
return pq->head->data;//NULL
}

2.4获取队列尾部元素

同上：

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
 
return pq->tail->data;
}

2.5获取队列中有效元素个数

还记得之前定义的 size 吗？
在这里它就展现出重要作用了：

// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}

2.6判断队列是否为空 

为空返回非 0 ，不是空就返回 0；

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* pq)
{
return pq->size == 0;
}

2.7销毁队列

思路就是把整个队列遍历一遍，释放每个结点，再把首尾指针置空，大小归 0 即可：

// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
free(cur);
cur = cur->next;
}
 
pq->head = pq->tail = NULL;
pq->size = 0;
}

代码已上传至 我的gitee

拿走不谢~ 

总结：
其实相比栈来说，队列只是在结构上复杂了一些，其他的操作与单链表的操作就非常相似了。

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗