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

这篇具有很好参考价值的文章主要介绍了数据结构-队列的实现（C语言版）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

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

1.队列的特性

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

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

如图：数据结构-队列的实现（C语言版）,数据结构,c语言,链表

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);
        cur = cur ->next;//迭代继续向后走
	}
}
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.测试部分

文章来源地址https://www.toymoban.com/news/detail-647425.html

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

到了这里，关于数据结构-队列的实现（C语言版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！