定义

定义：队列是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的线性标，简称FIFO。允许插入的一段称为队尾，允许删除的一端称为队头。

队列要实现的接口

//初始化
QueueType QueueInit(Queue* pq);
//进队
void QueuePush(Queue* pq, int x);
//出队
void QueuePop(QNodepq);
//返回队头
QueueType QueueFront(Queue* pq);
//返回队尾
QueueType QueueBack(Queue* pq);
//返回对列的长度
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列的销毁
void QueueDsetory(Queue* pq);

队列的创建

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QueueType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueType data;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

初始化
QueueType QueueInit(Queue* pq);

QueueType QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

进队
void QueuePush(Queue* pq, int x);

void QueuePush(Queue* pq, int x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("内存开辟失败\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

出队
void QueuePop(QNodepq);

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;
	}
}

返回队头
QueueType QueueFront(Queue* pq);

QueueType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

返回队尾
QueueType QueueBack(Queue* pq);

QueueType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

返回对列的长度
int QueueSize(Queue* pq);

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}

判断队列是否为空
bool QueueEmpty(Queue* pq);

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

队列的销毁
void QueueDsetory(Queue* pq);

void QueueDsetory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}