1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列遵循先进先出FIFO(First In First Out) ，与栈的后进先出相反。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，对于队列的实现，我们使用的是链表。
标准库的包含
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>队列结构体的设计
在这里关于结构的选择就不是双选题了，因为无论选左边还是右边作为队尾，数组总是逃不过需要挪动数据的结果。反观链表就显得相对自由。
typedef int QDatatype;
typedef struct QueueNode
{
struct QueueNode* next;
QDatatype data;
}QNode;结构体QNode表示链表节点，其中包含data域和next指针
但只使用链表结构也不够完善，对于链表来说最痛苦的莫非是尾结点的访问了，但这里要频繁地对尾节点进行访问，不妨再使用一个结构体存储头尾结点，来表示一整个队列。这样处理后，若我们要对头结点进行更改也不需要使用到二级指针了，因为只是对结构体内的数据进行更改因此只需要结构体指针。为了统计大小更加方便也需要一个 size 表示大小。
typedef struct Queue//队列中,多个数据,如头指针尾指针,最好用结构体封装一个函数,不然不好传参
{//单链表给尾指针不能解决问题,尾删还需要前一个tailprev
QNode* head;
QNode* tail;
int size;
}Queue;结构体Queue包括了两个永远指向队列的队首和队尾的指针
需要实现的接口
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq,QDatatype x);
//队头出队列
void QueuePop(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
// 获取队列头部元素
QDatatype QueueFront(Queue* pq);
// 获取队列队尾元素
QDatatype QueueBack(Queue* pq);初始化队列
一开始的队列本为空，只需要将头尾结点制空， size 归零。就完成了插入数据前的准备。
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}判空
为空的判定就相对简单，头尾结点正常情况下是同时为空的，也为了避免特殊情况即二者其中一个为空就可以判断整个队列是空的。
// 检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head = NULL && pq->tail = NULL;
}入队
传入数值前先断言(养成好习惯)，之后像链表那样开辟一个新节点并对其赋值。之后就要面临一个分岔口，队列是否为空，贸然地对头结点解引用就会出现错误，若为空则新节点就变成头结点，非空就链接在尾结点后，这之后自身成为尾结点。
//队尾入队列
void QueuePush(Queue* pq,QDatatype x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;//传入数据
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++;
}出队
断言后出队需要做到的是：事先将下一结点保存起来，不然当前头结点释放后便无法访问到下一结点了。之后释放头结点，下一结点就变成了头结点，同时 size-- ，保证空间数量的准确避免越界访问。
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
//方法一
//QNode* next = pq->head->next;
//free(pq->head);
//pq->head = next;
//pq->size--;
////当剩最后一个结点时,tail可能是野指针
//if (pq->head == NULL)
// pq->tail = NULL;
//方法二
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}获取队列头部/尾部元素
// 获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// 获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}获取队列中有效元素个数
这里需要感谢我们在前面在结构内就存储了大小，不然还需要遍历链表才能得到队列的大小。
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
//带头双向循环链表的头结点不可以存放size,因为链表的数据类型是不确定的,如果存放的是char类型的数据,当size加到128链表会溢出
//这时可以给哨兵位的头结点单独定义一个结构体,但是没必要
////带头双向循环链表的补充
//int LTSize(LTNode * phead);//需要遍历
////简化 多个数据定义结构体
//struct List
//{
// LTNode* phead;
// int size;
//};
}队列的销毁
同样有 malloc 就有 free ，在这里我们每个结点都是动态开辟出来的，所以都需要释放。就像链表释放那样，一边遍历一边释放。最后再把队列的结构体初始化就完成了。
//队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}源码：
Queue.h 头文件 结构体的定义 函数声明
#pragma once
#include<stdio.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//队列中,多个数据,如头指针尾指针,最好用结构体封装一个函数,不然不好传参
{//单链表给尾指针不能解决问题,尾删还需要前一个tailprev
QNode* head;
QNode* tail;
int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq,QDatatype x);
//队头出队列
void QueuePop(Queue* pq);
// 获取队列中有效元素个数
int QueueSize(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* pq);
// 获取队列头部元素
QDatatype QueueFront(Queue* pq);
// 获取队列队尾元素
QDatatype QueueBack(Queue* pq);Queue.c
#include"Queue.h"
//队列的初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq,QDatatype x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;//传入数据
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++;
}
//队头出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head != NULL);
//方法一
//QNode* next = pq->head->next;
//free(pq->head);
//pq->head = next;
//pq->size--;
////当剩最后一个结点时,tail可能是野指针
//if (pq->head == NULL)
// pq->tail = NULL;
//方法二
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
//带头双向循环链表的头结点不可以存放size,因为链表的数据类型是不确定的,如果存放的是char类型的数据,当size加到128链表会溢出
//这时可以给哨兵位的头结点单独定义一个结构体,但是没必要
////带头双向循环链表的补充
//int LTSize(LTNode * phead);//需要遍历
////简化 多个数据定义结构体
//struct List
//{
// LTNode* phead;
// int size;
//};
}
// 检测队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head = NULL && pq->tail = NULL;
}
// 获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// 获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}Test.c
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
return 0;
}