数据结构-队列的实现（C语言版）

前言

队列是一种特殊的线性表，它只允许在一端对数据进行插入操作，在另一端对数据进行删除操作的特殊线性表，队列具有先进先出的（FIFO）的特性，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

1.队列的特性

队尾：元素在队尾入队。插入操作。

队头：元素在队头出对。删除操作。

如图：

2.队列的实现

队列可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，需要挪动数据，因此这里采用链表的方式来进行队列的实现。

//queue.h

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* _next;
	QDataType _data;
}QueueNode;
typedef struct  Queue//队列的结构
{
	QueueNode* _head;//头指针
	QueueNode* _tail;//尾指针
}Queue;

void QueueInit(Queue* qu);//初始化栈

void QueueDestory(Queue* qu);//摧毁栈

void QueuePush(Queue* qu,QDataType data);//入队

void QueuePop(Queue* qu);//出队

QDataType QueueFront(Queue* qu);//返回队头元素
QDataType QueueBack(Queue* qu);//返回队尾元素

size_t QueueSize(Queue* qu);//队列长度

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

//queue.c

void QueueInit(Queue* qu)//初始化栈
{
	qu->_head = qu->_tail = NULL;
}
void QueueDestory(Queue* qu)//摧毁栈
{
	//确保指针有效
	assert(qu);
	QueueNode* cur = qu->_head;
	while (cur)
	{
		QueueNode* next = cur->_next;
		free(cur);
	}
}
void QueuePush(Queue* qu,QDataType data)//入队
{
	if (qu->_head == NULL)
	{
		qu->_head = (QueueNode*)malloc(sizeof(QueueNode));
		qu->_tail = qu->_head;
		qu->_head->_next = NULL;
		qu->_head->_data = data;
	}
	else
	{
		//尾部入数据
		QueueNode* cur = qu->_tail;
		QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
		cur->_next = newNode;
		newNode->_next = NULL;
		qu->_tail = newNode;
		newNode->_data = data;
	}
}
void QueuePop(Queue* qu)//出队
{
	//队头出数据
	QueueNode* head = qu->_head;
	qu->_head = head->_next;
	free(head);
}
QDataType QueueFront(Queue* qu)//返回队头元素
{
	return qu->_head->_data;
}
QDataType QueueBack(Queue* qu)//返回队尾元素
{
	return qu->_tail->_data;
}
size_t QueueSize(Queue* qu)//队列长度
{
	assert(qu);//确保指针存在
	QueueNode* cur = qu->_head;
	size_t size = 0;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}
bool QueueEmpty(Queue* qu)//判断队列是否为空
{
	return !qu->_head;
}

3.测试部分

void TestQueue()
{
	Queue qu;
	QueueInit(&qu);
	QueuePush(&qu, 1);
	QueuePush(&qu, 2);
	QueuePush(&qu, 3);
	QueuePush(&qu, 4);
	QueuePush(&qu, 5);
	QueuePush(&qu, 6);
	QueuePush(&qu, 7);
	QueuePush(&qu, 8);
	while (!QueueEmpty(&qu))
	{
		printf("%d ", QueueFront(&qu));
		QueuePop(&qu);
	}
	QueueDestory(&qu);
}