当前位置: article > 正文

队列——（c语言实现）_c语言实现队列

作者：天景科技苑 | 2024-07-26 10:55:11

踩

c语言实现队列

一、队列的概念

队列，是一种先进先出（first in first out 简称FIFO）的数据结构，是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，在队列中，进行插入的一端称为队尾，进行删除的一端称为队头。

二、队列的相关操作

初始化队列：
        创建一个新的空队列的过程。
销毁队列：
        释放队列使用的资源并使队列不再可用的过程。
入队：
        将一个元素添加到队列。

出队：
弹出队头元素。

取队头元素：
得到队头元素，但是不改变原队列。
取队尾元素：
得到队尾元素，但是不改变原队列。
判断队列是否为空：
判断队列里面有没有元素。
求队列的大小：
返回队列中元素的数量。

三、队列的实现

队列也可以数组和链表的结构实现，但使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率比较低。又因为只在队头和队尾进行操作，因此使用单链表即可。

为了能够灵活使用，不浪费空间，因此使用动态队列。在插入元素时会自动进行扩容。

我们将栈的全部代码分在三个文件内完成：

一个头文件：Queue.h（定义队列）

两个源文件：Queue.c(实现队列中的操作）

test.c（测试队列）

定义队列的结构

typedef int DataType; 是C语言中的类型定义（typedef）语句，用于创建一个新的类型名称。在这里它定义了 DataType 作为 int 类型的别名，也就是在队列中存储整型，如果想存储其他类型的数据，改变int为其他类型即可。

QNode 结构体：这是队列中节点的定义，包含了两个部分：
- DataType data：数据域，存储队列中的数据。
- struct QueueNode* next：指针域，指向队列中下一个节点。
Que 结构体：这是队列的主体结构，包含了三个部分：
- QNode* head：头指针，指向队列的第一个元素。
- QNode* tail：尾指针，指向队列的最后一个元素。
- int size：队列的大小，即队列中元素的数量。


typedef int DataType;
//队列的结构体
typedef struct QueueNode
{
	DataType data;
	//数据域
	struct QueueNode* next;
	//指针域
}QNode;
typedef struct Queue
{
	QNode* head;
	//头指针
	QNode* tail;
	//尾指针
	int size;
	//队列的大小
}Que;

初始化队列

assert(q)：使用 assert 函数来确保传入的队列指针 q 不是 NULL。确保这个队列正确存在，在后面也会多次使用。

我们需要以下步骤：

1、初始化头尾指针

2、初始化队列大小


void QueueInit(Que* q)
{
	assert(q);
	q->head = q->tail = NULL;
	//初始化头指针和尾指针
	q->size = 0;
	//初始化队列大小为0
}

入队

向队列中添加一个新元素。我们需要分为两种情况，一种是队列为空，另一种是队列不为空。

我们需要以下步骤：

内存申请：为新节点分配内存，若申请失败则打印错误并退出。
设置数据和指针：将传入的数据赋给新节点的数据域，将新节点的下一个指针设置为 NULL。
更新队列指针：队列为空，则新节点同时作为头节点和尾节点。队列不为空，则添加到尾部并更新尾指针。
更新队列大小：队列大小加1。


void QueuePush(Que* q, DataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//申请新节点空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//如果队列为空
	if (q->tail == NULL)
	{
	q->head=q->tail = newnode;
	}
	//如果队列不为空
	else
	{
	q->tail->next = newnode;
	q->tail = newnode;
	}
	q->size++;
}

出队

从队列中移除一个元素。同样分为两种情况，一种是队列为空，另一种是队列不为空。

我们需要以下步骤：

断言检查：确保队列不为空。
释放头节点：如果队列只有一个元素，则直接释放该元素，如果队列有多个元素，则释放头节点。
更新队列指针和大小：如果队列只有一个元素，同时更新尾指针，如果队列有多个元素，则更新头指。队列大小减1。


void QueuePop(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//如果队列只有一个元素
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	//如果队列有多个元素
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;
}

取队头元素、取队尾元素

要求队列非空，返回队列的第一个元素的值或者最后一个函数值，因为有头尾指针，因此很简单，只需要直接返回即可。

我们需要以下步骤：

断言检查：确保队列不为空。
返回值：返回头节点或尾节点的数据。


//头节点元素
DataType QueueFront(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//尾节点元素
DataType QueueBack(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

判断队列是否为空、求队列元素个数

如果队列的大小为0，则返回 true。因为有size，直接返回队列大小是否为0的比较结果就行。获取元素个数就直接返回size个数就行。

这里注意，bool需要引入头文件#include<stdbool.h>


//判断队列是否为空
bool QueueEmpty(Que* q)
{
	assert(q);
	return q->size == 0;
}
//求队列元素个数
int QueueSize(Que* q)
{
	assert(q);
	return q->size;
}

销毁队列

因为是单链表实现，销毁队列需要释放队列中所有节点的内存，并将队列的头、尾指针以及大小重置。

我们需要以下步骤：

断言检查：确保传入的队列指针不是 NULL。
遍历释放：从头节点开始，遍历每个节点，并释放其内存。
重置指针和大小：将头指针、尾指针设置为 NULL，队列大小设置为0，表示队列为空并且没有内存泄漏。


void QueueDestroy(Que* q)
{
	assert(q);
	QNode* cur = q->head;
	//从头指针开始释放
	while (cur)
	{
		//保存下一个节点的地址
		QNode* next = cur->next;
		//释放当前节点
		free(cur);
		//更新当前节点
		cur = next;
	}
	q->head = q->tail = NULL;
	q -> size = 0;
}

四、完整代码

Queue.h ：


#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef int DataType;
//队列的结构体
typedef struct QueueNode
{
	DataType data;
	//数据域
	struct QueueNode* next;
	//指针域
}QNode;
typedef struct Queue
{
	QNode* head;
	//头指针
	QNode* tail;
	//尾指针
	int size;
	//队列的大小
}Que;
 
//初始化
void QueueInit(Que* q);
//销毁
void QueueDestroy(Que* q);
//入队
void QueuePush(Que* q,DataType x);
//出队
void QueuePop(Que* q);
//取队首元素
DataType QueueFront(Que* q);
//取队尾元素
DataType QueueBack(Que* q);
//判断队列是否为空
bool QueueEmpty(Que* q);
//求队列的大小
int QueueSize(Que* q);

Queue.c：


#include"Queue.h"
//队列初始化
void QueueInit(Que* q)
{
	assert(q);
	q->head = q->tail = NULL;
	//初始化头指针和尾指针
	q->size = 0;
	//初始化队列大小为0
}
//销毁队列
void QueueDestroy(Que* q)
{
	assert(q);
	QNode* cur = q->head;
	//从头指针开始释放
	while (cur)
	{
		//保存下一个节点的地址
		QNode* next = cur->next;
		//释放当前节点
		free(cur);
		//更新当前节点
		cur = next;
	}
	q->head = q->tail = NULL;
	q -> size = 0;
}
//入队
void QueuePush(Que* q, DataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//申请新节点空间
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//如果队列为空
	if (q->tail == NULL)
	{
	q->head=q->tail = newnode;
	}
	//如果队列不为空
	else
	{
	q->tail->next = newnode;
	q->tail = newnode;
	}
	q->size++;
}
//出队
void QueuePop(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	//如果队列只有一个元素
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	//如果队列有多个元素
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	q->size--;
}
//取队首元素
DataType QueueFront(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
//取队尾元素
DataType QueueBack(Que* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
//判断队列是否为空
bool QueueEmpty(Que* q)
{
	assert(q);
	return q->size == 0;
}
//求队列元素个数
int QueueSize(Que* q)
{
	assert(q);
	return q->size;
}

test.c:


#include"Queue.h"
void test()
{
	Que qp ;
	QueueInit(&qp);
	QueuePush(&qp, 1);
	QueuePush(&qp, 2);
	QueuePush(&qp, 3);
	QueuePush(&qp, 4);
	QueuePush(&qp, 5);
	QueuePush(&qp, 6);
	printf("入队1-6\n");
	printf("头元素:");
	printf("%d\n",QueueFront(&qp));
	printf("尾元素:");
	printf("%d\n", QueueBack(&qp));
	printf("\n");
 
	QueuePush(&qp, 7);
	printf("入队7\n");
	printf("头元素:");
	printf("%d\n", QueueFront(&qp));
	printf("尾元素:");
	printf("%d\n", QueueBack(&qp));
	printf("\n");
 
	QueuePush(&qp, 8);
	printf("入队8\n");
	printf("头元素:");
	printf("%d\n", QueueFront(&qp));
	printf("尾元素:");
	printf("%d\n", QueueBack(&qp));
	printf("\n");
 
	QueuePop(&qp);
	printf("出队\n");
	printf("头元素:");
	printf("%d\n", QueueFront(&qp));
	printf("尾元素:");
	printf("%d\n", QueueBack(&qp));
	printf("\n");
 
	printf("出队\n");
	QueuePop(&qp);
	printf("头元素:");
	printf("%d\n", QueueFront(&qp));
	printf("尾元素:");
	printf("%d\n", QueueBack(&qp));
	QueueDestroy(&qp);
 
}
int main()
{
	test();
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/天景科技苑/article/detail/884908

队列——（c语言实现）_c语言实现队列

一、队列的概念

二、队列的相关操作

三、队列的实现

定义队列的结构

初始化队列

入队

出队

取队头元素、 取队尾元素

判断队列是否为空、求队列元素个数

销毁队列

四、完整代码

Queue.h ：

Queue.c：

test.c:

取队头元素、取队尾元素