1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

• 入队列：进行插入操作的一端称为队尾
• 出队列：进行删除操作的一端称为队头

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。

我们可以用单链表来实现：

2.1创建一个队列

先创建一个结构体封装数据之间的关系

再创建一个结构体封装队列的头和尾

2.2初始化

2.3销毁

2.4入队列

2.5出队列

2.6取队列头数据

2.7取队列尾数据

2.8判空

2.9返回队列有效元素个数

2.10访问

当队列不为空的时候，访问队头数据，访问一个pop一个

3.总代码 

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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 QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
		//防止ptail成为野指针
	}
	pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{
	Queue Q;
	QInit(&Q);
	QPush(&Q, 1);
	QPush(&Q, 2);
	QPush(&Q, 3);
	QPush(&Q, 4);
	QPush(&Q, 5);
	int size = QSize(&Q);
	printf("%d\n", size);
	while (!QEmpty(&Q))
	{
		printf("%d ", QFront(&Q));
		QPop(&Q);
	}
	QDestroy(&Q);
	return 0;
}