一、队列是什么？
队列本质上一个一个特殊的线性结构。和栈相似，主要在插入删除位置上有所区别，都可以用顺序结构或者链式结构实现。在实际使用中我们经常是用链表来实现队列。通常我们要实现先进先出（FIFO）的操作。在队列中，新元素插入到队列的尾部，已有元素从队列的头部删除。接下来我来介绍一下队列的实现。
二、队列的结构
我们规定：出数据的一端叫队头，操作叫出队 （pop）。
入数据的一端叫队尾，操作叫入队（push）。
个人理解：
队列就是链表操作的简化版本，只进行头删（出队），尾插（入队）。不可以中间插入和删除，保证了队列的逻辑顺序和结构。
三、队列的实现
3.1定义结点结构
首先，我们需要定义一个结点结构体来表示队列中的每个节点：
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
} QNode;指针域：每一个结点包含一个next结构体指针指向下一个结构体的地址或NULL 。
数值域： data ，可直接访问。
3.2定义一个包含结点的结构体
接着，我们定义一个队列结构体，其中包含头结点指针、尾结点指针以及队列中元素的个数：
typedef struct QNode
{
QNode* head; //头结点指针
QNode* tail; //尾结点指针
int size; //队列元素个数
} Queue;头结点指针 head 指向队列最前面的一个节点，尾结点指针 tail 指向队列最后面的一个节点，队列中元素的个数 size 表示队列中当前元素的数量。
3.3 初始化队列
void QueueInit(Queue* pq) //用结构体指针就可以修改该结构体内的成员 修改的不是结点
{
assert(pq);
pq->head = NULL; // 头尾结点指针都置空
pq->tail = NULL;
pq->size = 0;
}注意：这里没有传二级指针是因为我改变的是我定义的队列结构内成员的内容，没有改变这个结构体的值，如果要修改那么就要传二级指针或者设一个返回值来修改。
3.4销毁队列
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;
}因为队列是链表的物理存储结构，每个结点位置不连续，所以必须一个个的释放。释放完了之后再重新将头尾结点指针置空，养成习惯防止野指针。
3.5入队操作
将新生成的结点插入队列的队尾，涉及到生成一个新结点和结点之间逻辑关系的改变。
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* tmp =(QNode*) malloc(sizeof(QNode)); //生成一个新结点
if (tmp == NULL) //创建失败
{
perror("malloc fail"); //打印错误
return;
}
//生成新的结点成功
tmp->data = x; //赋值
tmp->next = NULL; //给指针赋成NULL 防止野指针
if (pq->head == NULL) //当头结点指针是NULL时那么就是空队列
{
assert(pq->tail == NULL);
pq->head = pq->tail = tmp; //空队列头尾结点指针都指向tmp
}
else //队列里面有元素
{
pq->tail->next = tmp;
pq->tail = tmp;
}
pq->size++; //最后size++
}注意：一定要判断为空队列的情况，这个情况头尾结点指针都要进行改动，都指向新生成的结点。当队列不为空时，只要修改尾结点指针。
3.6出队操作
void QueuePop(Queue* pq) //头部删
{
assert(pq);
assert(pq->head);
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--;
}注意：出队操作需要注意的是在当整个队列只有一个元素的时候，直接就删除这个结点，然后头尾结点指针都置NULL；因为如果队列元素>1,我们统一的操作是先保存头结点下一个结点的地址，那么当队列元素为1，那么头结点下一个就是NULL ，操作无法统一。
3.7队列元素个数
int QueueSize(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->size;
}注意：一定要先判空。
3.8判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->size == 0;
return pq->head == NULL && pq->tail == NULL;
}3.9取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}这个时候头结点指针的优势就出来了，可以直接找到然后返回这个值，前提一定要先判空，如果整个队列的元素个数都为0了，那么就没有可返回的值。
3.10取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}和取队头一样的注意事项，一定要判空。
四、队列测试
我们使用testStack1函数对实现的队列进行测试：
void testStack1()
{
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);
}
printf("\n");
QueueDestroy(&q);
}该函数创建了一个队列 q，并向队列中插入4个元素，然后从队列头部开始逐一删除元素并输出。
输出截图：
五、队列实现整个代码
头文件 Queue.h 用来函数声明和定义结点结构
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct QNode
{
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);
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 = NULL;
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)
{
assert(pq);
QNode* tmp =(QNode*) malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("malloc fail");
return;
}
tmp->data = x;
tmp->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = tmp;
}
else
{
pq->tail->next = tmp;
pq->tail = tmp;
}
pq->size++;
}
void QueuePop(Queue* pq) //头部删
{
assert(pq);
assert(pq->head);
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--;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->size == 0;
return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return 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;
}主函数 调用来测试队列的实现
test.c
#include"Queue.h"
void testStack1()
{
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);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
testStack1();
return 0;
}