引言
数据结构之路经过栈后，就来到了与栈联系紧密的兄弟——队列（Queue）
队列的概念与结构
队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作 的特殊线性表，队列具有 先进先出 FIFO(First In First Out)
入队列： 进行插入操作的一端称为 队尾
出队列： 进行删除操作的一端称为 队头
队列的实现
队列 也可以 数组和链表的结构 实现 ，使用 链表的结构实现更优 一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
定义
队列的实现，需要定义两个结构体，一个代表节点的信息，另一个代表队列的信息，因为队列的特性要在一端入，另一端出，所以要记录头尾指针（要不然找尾效率太低了） ，而size代表当前队列元素个数（可加可不加，加上更好）
初始化
头尾指针置为NULL，size置为0
销毁
队列的销毁，本质上就是链表的销毁 ，创建cur变量，循环释放每一个节点，直到cur为空，最后再将头尾指针置为NULL，size置为0
入队
入队时 ，先生成新节点（因为这里只有入队用到生成新节点，所以不用抽离成函数），再要分空链表和非空链表进行讨论
空链表判断时，加入assert断言，防止外部操作错误，造成头指针不为空，尾指针为空
链表为空时，则头尾指针都指向新节点；链表不为空时，则正常尾插
判断队列是否为空
专门写一个函数判断，增强复用性和可读性 。如果size为0，则队列为空，返回真；反之，则不为空，返回假
出队
出队时，先判断队列是否为空（保证phead不为NULL，防止为空指针的解引用），再分单个节点和多个节点来讨论
单个节点，则释放头指针指向的节点后，头尾指针置为NULL；多个节点，则正常头删
获取队头元素
获取队尾元素
检测队列中有效元素个数
这里很多函数实现都很简单，有些操作直接外部对结构体都可以直接实现，但最后还是写成函数封装，防止别人使用时对该数据结构不够熟悉，导致使用错误
元素访问
队列中元素访问（打印），不是用函数实现。因为它的特殊结构，决定了它的元素不能从任意位置访问 ，必须符合先进先出原则才可以。所以，我们通常用循环的方式进行访问，同时每访问一个元素，就将它弹出队列，再进行下一个元素的访问。
运行结果
队列与栈有所不同，因为它先进先出的特性，导致顺序只能是1 2 3 4
这样我们就实现了队列的增删等功能
源代码
queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }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); //检测队列中有效元素个数 int QueueSize(Queue* pq); //检测队列是否为空 bool QueueEmpty(Queue* pq);
queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } void QueueDestroy(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, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; if (pq->ptail == NULL) { assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); return pq->phead->data; } QDataType QueueBack(Queue* pq) { assert(pq); return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"queue.h" void TestQueue1() { 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); } //销毁 QueueDestroy(&q); } int main() { TestQueue1(); return 0; }
