C语言 之【队列的简介、队列的实现(初始化、销毁、入队、出队、判空、元素个数、元素的访问)】
目录
1.队列的简介
2.队列的实现
2.1实现须知
2.2 头文件预览
2.2.1 头文件细节
2.3 队列的初始化
2.4 队列的销毁
2.5 入队
2.6出队
2.7 判空
2.8 队列的元素个数
2.9队首元素与队尾元素
2.10 队列的打印
1.队列的简介
队列是一种数据结构，也是一种特殊的线性表
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作
进行插入数据操作的一端叫作队尾， 进行删除数据操作的一端叫作队头
队列遵守先进先出 FIFO(First In First Out)原则
就像生活中顾客按到达顺序排队到超市收银员处结账一样，
新顾客加入队尾，服务从队头开始，排在队头的顾客先结账离开
插入数据操作，简称入队；删除数据操作，简称出队
2.队列的实现
2.1实现须知
前面说了，队列是是一种线性表，所以既可以用数组实现队列也可以用链表实现队列
注意到：
(1)数组、链表(给定尾指针的情况下)，尾插的效率均为O(1)，
但链表只需按需申请空间，数组却要进行预分配空间，进行扩容操作还可能造成空间浪费
(2)数组、链表头删同样是
O(1)（数组不移动数据得情况下）所以队列的实现方式得基于具体场景，根据链表和数组的特性而定
下面使用链表实现的队列
(1)给定一个头指针head和一个尾指针tail就能实现尾插(入队)，头删(出队)
所以，无头单向不循环链表就可实现队列
2.2 头文件预览
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QNode;
//队列不仅需要实现单链表的头删，还要知晓元素个数，那么就是多个数据用结构体存储
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QueueDataType val);
//出队
void QueuePop(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//大小
int QueueSize(Queue* pq);
//队首元素
QueueDataType QueueFront(Queue* pq);
//队尾元素
QueueDataType QueueBack(Queue* pq);2.2.1 头文件细节
(1)防止头文件内容在同一个编译单元内被多次展开
#pragma once(2)包含必要的头文件(库函数、开空间、断言、布尔值)
(3)数据类型重命名，(以后只改这一处，就可以改变栈所存储的数据类型)
typedef int QueueDataType;(4)为了简洁与区分度，将队列的节点命名为QNode，
(5)在实现无头单向不循环链表时，只需要一个头指针head就可以完成一系列操作
但是这样会导致尾插效率低、无法直接获取队尾元素(效率均为O(N),因为需要找尾)
实现队列时，我们再定义一个结构体Queue，存储
变量head, 指向对头
变量tail，指向队尾
变量size，记录队列的元素个数
这样之后，就无需在接口中设置多个参数，让用户传多个参数，
达到用一个队列类型的指针管理队列所有节点的目的，也提高了尾插的效率
2.3 队列的初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;}(1)队列指针一定不为空，所以断言队列指针
(1)空队列的状态就是 "空"
2.4 队列的销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = pq->head->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
(1)队列指针一定不为空，所以断言队列指针
(1)队列中，需要主动释放的空间就是节点所占据的空间
遍历队列，逐个释放，并还原成空队列状态即可
2.5 入队
void QueuePush(Queue* pq, QueueDataType val)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = val;newnode->next = NULL;//尾插注意判空if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}++(pq->size);
}(1)队列指针一定不为空，所以断言队列指针
(2)用户只传入数据，函数体内部需要创建新节点存储数据
(2)入队就是尾插，分两种情况进行尾插
1.队列为空时，head、tail都要指向新节点
2.不为空时，先将新节点链接到链表中，再改变节点的位置
(3)++size
2.6出队
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));QNode* next = pq->head->next;free(pq->head);pq->head = next;//注意一个节点时的出队if (pq->head == NULL){pq->tail = NULL;}--(pq->size);
}(1)队列指针一定不为空，所以断言队列指针
(1)出队时，队列一定不为空，所以断言队列
(1) 出队就是头删，但是需要注意只有一个节点时的头删
此时需要改变尾指针的指向
(3)--size
2.7 判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}(1)队列指针一定不为空，所以断言队列指针
（2）直接判断size即可
2.8 队列的元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
(1)队列指针一定不为空，所以断言队列指针
（2）直接返回size即可
2.9队首元素与队尾元素
//队首元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}
//队尾元素
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}(1)队列指针一定不为空，所以断言队列指针
(1)访问元素时，队列一定不为空(队列为空时访问是无效操作)，所以断言队列
(1)直接返回对应节点存储的数据
2.10 队列的打印
队列并不支持遍历访问，只支持访问队头元素和队尾元素，即不提供遍历访问的接口
想要知道所有元素
只能边访问队头元素，边出队
当然，如果需要保留元素，可提前保存一下
Queue pq;QueueInit(&pq);QueuePush(&pq, 1);QueuePush(&pq, 2);QueuePush(&pq, 3);QueuePush(&pq, 4);QueuePush(&pq, 5);QueuePush(&pq, 6);while (!QueueEmpty(&pq)){printf("%d ", QueueFront(&pq));QueuePop(&pq);}