目录
1 队列的概念
队列是一种线性表，它只能在一端插入数据，在另一端删除数据，插入数据的那一端被称为队尾，删除数据的那一端被称为队头，队列遵循 “先进先出” 原则，也就是说，先进入队列的元素会优先出队
2 队列的结构
队列可以用链表和顺序表来实现，但是普通的队列一般通过链表来实现，因为链表插入删除较方便
由于队列的队头，队尾，元素个数都需要记录，所以队列的结构体如下：
typedef int QDataType;
//队列中的结点
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead; //队首指针
QNode* ptail; //队尾指针
int size; //队列元素个数
}Queue;
3 队列的操作
3.1 队列的初始化
初始化队列，只需要把头尾指针置为空，元素个数设置为 0 即可
代码实现
void QueueInit(Queue* q)
{
assert(q);
q->phead = NULL;
q->ptail = NULL;
q->size = 0;
}
3.2 入队
入队时要往队尾插入元素，由于是用单链表实现的队列，因此入队就是进行单链表尾插，在尾插时，可以使用带头结点或不带头结点的方式，这边使用的是不带头结点的方式
队列为空
队列不为空
代码实现
void QueuePush(Queue* q, QDataType val)
{
assert(q);
QNode* node = (QNode*)malloc(sizeof(QNode));
if (!node)
{
perror("malloc");
return;
}
node->next = NULL;
node->val = val;
if (q->phead == NULL) //链表为空
{
q->phead = node;
q->ptail = node;
}
else //链表不为空
{
q->ptail->next = node;
q->ptail = node;
}
q->size++;
}
3.3 出队
在实现出队操作时，由于队头是链表头，所以进行头删，若队列只剩下一个元素，则需要特殊处理
队列不止一个元素
队列只有一个元素
代码实现
void QueuePop(Queue* q)
{
assert(q);
assert(q->size > 0);
if (q->phead->next == NULL) //只有一个结点
q->ptail = NULL;
QNode* cur = q->phead;
q->phead = cur->next;
free(cur);
cur = NULL;
q->size--;
}
3.4 获取队头元素
由于 phead 就指向了队头，所以获取队头元素直接使用 phead 即可
代码实现
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->size > 0);
return q->phead->val;
}
3.5 获取队尾元素
由于 ptail 指向了队尾，所以直接使用 ptail 就可以获取队尾元素
代码实现
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->size > 0);
return q->ptail->val;
}
3.6 获取队列中元素的个数
由于在队列的结构体 Queue 中，已经使用了 size 来记录元素的个数，所以直接返回 size 即可，若没有定义 size ，则需要遍历结点并计数，较为繁琐
代码实现
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
3.7 判空
检查队列元素个数 size 是否为 0 即可
代码实现
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
3.8 销毁队列
由于队列是使用单链表实现的，所以在销毁队列时，需要将单链表的结点一个个释放
代码实现
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->phead = NULL;
q->ptail = NULL;
q->size = 0;
}
4 队列的整体实现
Queue.h
#pragma once
//结构体定义，函数声明
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
//避免二级指针和多个形参的问题
typedef struct Queue
{
QNode* phead; //队首指针
QNode* ptail; //队尾指针
int size; //队列元素个数
}Queue;
//队列初始化
void QueueInit(Queue* q);
//入队
void QueuePush(Queue* q, QDataType val);
//出队
void QueuePop(Queue* q);
//获取队头元素
QDataType QueueFront(Queue* q);
//获取队尾元素
QDataType QueueBack(Queue* q);
//获取队列中元素个数
int QueueSize(Queue* q);
//判空
bool QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);
Queue.c
//函数实现
#include "Queue.h"
//队列初始化
void QueueInit(Queue* q)
{
assert(q);
q->phead = NULL;
q->ptail = NULL;
q->size = 0;
}
//入队
void QueuePush(Queue* q, QDataType val)
{
assert(q);
QNode* node = (QNode*)malloc(sizeof(QNode));
if (!node)
{
perror("malloc");
return;
}
node->next = NULL;
node->val = val;
if (q->phead == NULL) //链表为空
{
q->phead = node;
q->ptail = node;
}
else //链表不为空
{
q->ptail->next = node;
q->ptail = node;
}
q->size++;
}
//出队
void QueuePop(Queue* q)
{
assert(q);
assert(q->size > 0);
if (q->phead->next == NULL) //只有一个结点
q->ptail = NULL;
QNode* cur = q->phead;
q->phead = cur->next;
free(cur);
cur = NULL;
q->size--;
}
//获取队头元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->size > 0);
return q->phead->val;
}
//获取队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->size > 0);
return q->ptail->val;
}
//获取队列中元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
//判空
bool QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
//销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
q->phead = NULL;
q->ptail = NULL;
q->size = 0;
}