当前位置：首页 > news >正文

用链表实现的C语言队列

news 来源：原创 2024/9/30 11:22:54

一、队列概述

在数据结构中，队列是一种先进先出（FIFO）的线性表。它在许多应用场景中非常有用，例如任务调度、进程管理、资源管理等。队列是一种重要的数据结构，其主要特点是先进先出（FIFO, First In First Out）。这意味着在队列中，最先进入队列的元素将最先被移出。队列的这种特性使得它在许多实际应用中非常有用，例如打印队列、任务调度、进程管理等。

队列的基本操作包括：

入队（Enqueue）：将元素加入到队列的末尾。
出队（Dequeue）：将队列最前面的元素移出队列。
获取队首元素（Front）：查看队列最前面的元素，但不移出。
检查队列是否为空（IsEmpty）：判断队列是否为空。
获取队列大小（Size）：获取队列中的元素个数

今天我将会用链表实现队列：

二、队列基本操作

队列的结点定义

首先，我们定义一个节点结构体来存储每个元素及其指向下一个节点的指针。

#define eleType int //定义队列元素数据类型//定义结点
typedef struct Node
{eleType data; //数据域struct Node* next; //指针域
} Node;

队列结构体

接下来，我们定义一个队列结构体，包含指向队首和队尾的指针以及队列中的元素个数。

//定义队列结构体
typedef struct
{Node* front; //链表头队列首元素指针Node* rear;  //队尾元素指针size_t size; //队列元素个数
} Quene;

队列的创建

初始化一个队列，需要将队首和队尾指针都设置为NULL，并将队列的大小初始化为0。、

void QueneCreat(Quene *q)
{q->front = q->rear = NULL;q->size = 0; //初始化为零
}

队列的销毁

销毁队列需要释放所有节点的内存，并将队首和队尾指针设置为NULL，队列的大小重置为0。

void QueneDestroy(Quene* q)
{while (q->front) //队首元素开始遍历{Node* temp = q->front; //每次遍历将队首指针存入到temp变量中q->front = q->front->next; //将队首指向后继free(temp); //删除游离出来的原来的队首结点}q->rear = NULL; //遍历完成后，将队尾指向空q->size = 0; //将队列重置为0，表示已经清空
}

入队操作

在队尾插入一个新元素。首先为新元素分配内存，然后根据队列是否为空更新队首和队尾指针。

void QuenePush(Quene* q, eleType element)
{//分配一个Node类型的空间，将其地址赋给newNode变量Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = element; //将要添加的元素赋值给新结点的数据域newNode->next = NULL; //将新结点的后继结点指向空if (q->rear == NULL) //判断当前队列是否为空，只需要判断队尾是否为空q->front = q->rear = newNode; //如果为空，将队首和队尾都指向新结点else //如果不为空{q->rear->next = newNode; //将新结点排入队尾q->rear = newNode; //更新队尾结点}q->size++; //队列大小加1
}

出队操作

在队首删除一个元素。首先检查队列是否为空，然后更新队首指针并释放原队首节点的内存。

eleType QuenePop(Quene* q)
{if (q->rear == NULL) //判断队列是否为空{printf("Quene is empty!\n");exit(1); //如果为空，退出程序}eleType element = q->front->data; //将队首元素赋值给element，用于返回Node* temp = q->front; //将队首指针存储到temp变量中q->front = q->front->next; //更新队首，游离出来原来的队首free(temp); //删除原来的队首q->size--; //队列大小减1if (q->size == 0) //如果队列空了的话q->rear = NULL; //将队尾指向空return element; //
}

获取队首元素

获取队首元素的数据，而不删除队首元素。

eleType QueneFront(Quene* q)
{if (q->rear == NULL) //判断队列是否为空{printf("Quene is empty!\n");exit(1); //如果为空，退出程序}return q->front->data; //返回队首元素
}

获取队列大小

获取队列中元素的个数。

size_t QueneSize(Quene* q)
{return q->size; //返回队列大小
}

三、完整代码

#define  _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdlib.h>
#define eleType int //定义队列元素数据类型//定义结点
typedef struct Node
{eleType data; //数据域struct Node* next; //指针域
} Node;//定义队列结构体
typedef struct
{Node* front; //链表头队列首元素指针Node* rear;  //队尾元素指针size_t size; //队列元素个数
} Quene;//队列的创建
void QueneCreat(Quene *q)
{q->front = q->rear = NULL;q->size = 0; //初始化为零
}//队列的销毁
void QueneDestroy(Quene* q)
{while (q->front) //队首元素开始遍历{Node* temp = q->front; //每次遍历将队首指针存入到temp变量中q->front = q->front->next; //将队首指向后继free(temp); //删除游离出来的原来的队首结点}q->rear = NULL; //遍历完成后，将队尾指向空q->size = 0; //将队列重置为0，表示已经清空
}//入队
void QuenePush(Quene* q, eleType element)
{//分配一个Node类型的空间，将其地址赋给newNode变量Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = element; //将要添加的元素赋值给新结点的数据域newNode->next = NULL; //将新结点的后继结点指向空if (q->rear == NULL) //判断当前队列是否为空，只需要判断队尾是否为空q->front = q->rear = newNode; //如果为空，将队首和队尾都指向新结点else //如果不为空{q->rear->next = newNode; //将新结点排入队尾q->rear = newNode; //更新队尾结点}q->size++; //队列大小加1
}//出队
eleType QuenePop(Quene* q)
{if (q->rear == NULL) //判断队列是否为空{printf("Quene is empty!\n");exit(1); //如果为空，退出程序}eleType element = q->front->data; //将队首元素赋值给element，用于返回Node* temp = q->front; //将队首指针存储到temp变量中q->front = q->front->next; //更新队首，游离出来原来的队首free(temp); //删除原来的队首q->size--; //队列大小减1if (q->size == 0) //如果队列空了的话q->rear = NULL; //将队尾指向空return element; //
}//获取队首元素
eleType QueneFront(Quene* q)
{if (q->rear == NULL) //判断队列是否为空{printf("Quene is empty!\n");exit(1); //如果为空，退出程序}return q->front->data; //返回队首元素
}//获取队列大小
size_t QueneSize(Quene* q)
{return q->size; //返回队列大小
}

今天介绍了如何使用链表在C语言中实现一个队列，并详细解释了每个步骤的实现方法。通过这种方式实现的队列，不仅可以动态扩展，还能高效地进行插入和删除操作。在实际应用中，这种链表实现的队列可以用于任务调度、进程管理等场景。