目录
队列的概念以及示意图
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
队列具有先进先出的逻辑
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列结构示意图：
数组队列和链式队列
数组队列：
把首元素当作队头，尾元素当作队尾
那么出队列就需要删除首元素，在把后面的元素向前挪动，降低了效率
且当空间不够时需要扩容，就存在异地扩容的问题，也会降低效率
链式队列：
把头节点当作队头，尾节点当作队尾
那么出队列只需要将指向头节点的指针指向下一个节点，在释放头节点即可，效率为O(1)
入队列只需要在尾节点尾插即可，所以选择实现链式队列
链式队列的结构
// 数据类型
typedef int QDataType;
// 链式队列每个节点的结构
typedef struct QueueNode
{
struct QueueNode* next; //指向下一个节点的指针
QDataType data; //当前节点的数据
}QNode;
// 链式队列的结构
typedef struct Queue
{
QNode* phead; //指向队头节点的指针
QNode* ptail; //指向队尾节点的指针
int size; //队列的总数据个数
}Queue;实现链式队列的准备工作
创建3个文件
test.c 文件：用来测试增删查改功能是否完善
Queue.h 文件：用来声明动态顺序表的结构以及声明增删查改函数
Queue.c 文件：用来实现动态顺序表的增删查改及功能函数
实现链式队列
1. 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}2. 打印队列的所有数据
void QueuePrint(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
printf("head<-");
while (cur != NULL)
{
printf("%d<-", cur->data);
cur = cur->next;
}
printf("tail\n\n");
}3. 数据入队列（尾插）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
// 开辟节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
// 判断是否开辟成功
if (newnode == NULL)
{
assert(pq->ptail == NULL);
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->phead == NULL)
{
// 双重判断，更保险
assert(pq->ptail);
pq->phead = newnode;
pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}分两种情况判断：
当队列没有节点时：直接将指向头尾节点的指针指向新节点
当队列有节点时：pq->ptail 就是指向最后一个节点的指针，那么 pq->ptail->next 就是节点的 next，直接指向新节点，再将 pq->ptail指向新节点
数据成功入队列，最后 size 自增1
测试代码：
4. 数据出队列（头删）
void QueuePop(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可出队列\n");
return;
}
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = NULL;
pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}分三种情况判断：
队列没有节点时：直接报错并返回
队列只有一个节点时：释放头节点，并将指向头尾节点的指针都置空
队列有多个节点时：保存下一个节点，再释放头节点，最后将指向头节点的指针指向保存的下一个节点
数据成功出队列，最后 size 自减1
测试代码：
5. 访问队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可访问\n");
return;
}
return pq->phead->data;
}6. 访问队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->ptail == NULL)
{
printf("无数据可访问\n");
return;
}
return pq->ptail->data;
}7. 队列数据总个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}8. 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}9. 释放队列的所有节点
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}10. 以队列逻辑遍历所有数据
Queue q;
QueueInit(&q);
for (int i = 1; i <= 5; i++)
{
QueuePush(&q, i);
}
printf("head<-");
while (!QueueEmpty(&q))
{
// 访问当前队头数据
printf("%d<-", QueueFront(&q));
// 移除当前队头数据
QueuePop(&q);
}
printf("tail\n\n");测试代码：
Queue.h 的所有代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
// 数据类型
typedef int QDataType;
// 链式队列每个节点的结构
typedef struct QueueNode
{
struct QueueNode* next; //指向下一个节点的指针
QDataType data; //当前节点的数据
}QNode;
// 链式队列的结构
typedef struct Queue
{
QNode* phead; //指向队头节点的指针
QNode* ptail; //指向队尾节点的指针
int size; //队列的总数据个数
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 打印
void QueuePrint(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 的所有代码
#include"Queue.h"
// 初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
// 打印
void QueuePrint(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
printf("head<-");
while (cur != NULL)
{
printf("%d<-", cur->data);
cur = cur->next;
}
printf("tail\n\n");
}
// 数据入队列（尾插）
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->phead == NULL)
{
// 双重判断，更保险
assert(pq->ptail == NULL);
pq->phead = newnode;
pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
// 数据出队列（头删）
void QueuePop(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可出队列\n");
return;
}
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = NULL;
pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
// 访问队头的数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->phead == NULL)
{
printf("无数据可访问\n");
return -1;
}
return pq->phead->data;
}
// 访问队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
// 队列没有数据时
if (pq->ptail == NULL)
{
printf("无数据可访问\n");
return -1;
}
return pq->ptail->data;
}
// 队列数据总个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
// 是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return (pq->phead == NULL) && (pq->ptail == NULL);
}