目录

前言

1. 队列

1.1 队列的概念

1.2 队列的结构

2. 队列的实现

2.1 队列的定义

2.2 队列的初始化

2.3 入队

2.4 出队

2.5 获取队头元素

2.6 获取队尾元素

2.7 判断空队列

2.8 队列的销毁

3. 队列完整源码

Queue.h

Queue.c

---

• 🎈个人主页：库库的里昂
•  🎐C/C++领域新星创作者
•  🎉欢迎 👍点赞✍评论⭐收藏
• ✨收录专栏：数据结构与算法
• 🤝希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！🤗

前言

在前几期的学习中，我们认识了顺序表、链表和栈这三种线性表，而在本期学习中，我们将会认识别的线性表。跟随我们的脚本，看看队列有怎样的特点。

1. 队列

1.1 队列的概念

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

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

1.2 队列的结构

2. 队列的实现

2.1 队列的定义

在入队时相当于尾插，我们可以定义一个尾指针来记录尾的位置。这就使我们传指针时，要传递两个指针，我们可以把指针放到结构体中，这样在插入第一个时也可以解决要传递二级指针的问题。

定义尾指针可以避免每次尾插时要遍历一遍链表。

typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

2.2 队列的初始化

这里的 size 用来记录队列中数据的个数。

void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}

2.3 入队

入队相当于尾插，在入队时我们要考虑链表是否为空。

void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

2.4 出队

出队相当于头删,与之前不同的是，当我们删除最后一个节点，还要记得处理尾指针。

void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}

2.5 获取队头元素

队头元素就是头指针指向的节点的数据域。

QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.6 获取队尾元素

我们通过尾指针可以直接找到队尾，不用遍历链表。

QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}

2.7 判断空队列

利用bool的函数判断队列是否为空，当尾指针为空时，返回true；当尾指针不为空时，返回false。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

2.8 队列的销毁

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

3. 队列完整源码

Queue.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueType* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);void QueueDstroy(Queue* pq);void QueuePush(Queue* pq, QDateType x);void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);QDateType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);int QueueSize(Queue* pq);

Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDstroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}QDateType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。