前言
在前几期的学习中，我们认识了顺序表、链表和栈这三种线性表，而在本期学习中，我们将会认识别的线性表。跟随我们的脚本，看看队列有怎样的特点。
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; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
