概念与结构

概念：只允许在⼀端进行插⼊数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
⼊队列：进行插⼊操作的⼀端称为队尾
出队列：进行删除操作的⼀端称为队头

底层结构的选择

数据：
入队列时间复杂度：O（1）
出队列时间复杂度：O（N）
链表（两个指针分别指向头节点与尾节点）：
入队列时间复杂度：O（1）
出队列时间复杂度：O（1）
综合比较链表的结构实现更优⼀些，因为如果使用数组的结构，出队
列在数组头上出数据，效率会比较低。

队列的实现

队列头文件（queue.h）

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;}QN;typedef struct Queue
{QN* phead;//队列头节点QN* ptail;//队列尾节点int size;//队列有效数据个数
}Q;void QueueInit(Q* pq);void QueuePush(Q* pq, QDataType x);//入队列void QueuePop(Q* pq);// 出队列，队头bool QueueEmpty(Q* pq);//检查队列是否为空QDataType QueueFront(Q* pq);//队列第一个数据QDataType QueueBack(Q* pq);//队列最后一个数据int QueueSize(Q* pq);//查看队列的有效数据个数void QueueDestry(Q* pq);//销毁队列

队列初始化

思路：
给队列结构体赋初值。
代码：

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

队列的销毁

思路：
因为底层结构式链表，所以队列销毁也就是链表销毁。
从头节点依次遍历释放节点空间。
最后给结构体还原为初值。
代码：

void QueueDestry(Q* pq)
{assert(pq);//遍历销毁QN* pcur = pq->phead;while (pcur){QN* tmp = pcur->next;free(pcur);pcur = tmp;}//还原为初值pq->phead = pq->ptail = NULL;pq->size = 0;
}

入队列

思路：
再队列结构体里我们定义了两个指针分别指向头节点与尾节点。
根据队列先进先出的特性，我们要从尾节点插入数据，也就是链表尾插。

这里尾插要分情况讨论，当队列为空时，phead与ptail都是指向NULL。
当插入一个数据，phead和ptail都要更改。
当不为空，只需要更改ptail。
代码：

//创建新节点
QN* BuyNode(QDataType x)
{QN* new = (QN*)malloc(sizeof(QN));if (new == NULL){perror("malloc fail!");exit(1);}new->next = NULL;new->val = x;return new;
}
//入队列
void QueuePush(Q* pq, QDataType x)
{assert(pq);QN* newnode = BuyNode(x);//新节点地址if (pq->phead == NULL)//当队列为空{pq->phead = newnode;pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;//有效数据个数加一
}

检查队列是否为空

思路：
当初始化结束后，队列就是空队列。
所以我们只需要判断结构体的值与我们的初值是否与初值相等，相等就是空队列，反之则不是。
代码：

bool QueueEmpty(Q* pq)//返回类型为bool
{return pq->phead == NULL && pq->ptail == NULL;
}

bool类型：
true：代表1；false：代表0.

出队列

思路：
删除头节点，让phead向后挪动一位。
根据队列的特性，经过分析可得就是链表的头删。

注：
当队列为空时就不能再出队列了。

代码：

void QueuePop(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QN* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}--pq->size;
}

查询队列第一个数据

直接返回phead指向的节点数据。

QDataType QueueFront(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->val;
}

查询队列末尾数据

QDataType QueueBack(Q* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->val;
}

查询队列有效数据个数

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

代码试运行

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void QueueTest01()
{Q q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);printf("head:%d\n", QueueFront(&q));printf("tail:%d\n", QueueBack(&q));printf("size:%d\n", QueueSize(&q));QueueDestroy(&q);
}int main()
{QueueTest01();return 0;
}

入队列检查：

获取队列相关数据检查：

队列销毁检查：

出队列操作检查：

四次正常运行，当第五次时队列为空，assert断言报错。

由这几幅图可得函数运行正常。

---

感谢观看，制作不易，给个三连吧看官老爷们。