【数据结构与算法】使用单链表实现队列：原理、步骤与应用
目录
一、引言
🎄队列的概念
队列（Queue）是一种特殊类型的线性数据结构，它遵循特定的操作顺序。队列的基本操作通常是在一端添加元素（称为入队或enqueue），在另一端移除元素（称为出队或dequeue）。这种操作特性使得队列符合“先进先出”（FIFO, First In First Out）的原则。
基本概念：
先进先出（FIFO）原则：这是队列的核心特性。它意味着最早被添加到队列中的元素将是第一个被移除的元素。这个原则确保了数据处理的顺序性。
队头（Front）：队列中第一个被添加的元素位于队头，但它不是永远位于队列的第一个位置，而是指按照入队顺序，最先应该被出队的元素的位置。在出队操作中，总是从队头移除元素。
队尾（Rear）或队末：新元素总是被添加到队列的这一端。在入队操作中，新元素总是被放置在队尾。
队列为空：当队列中没有元素时，称队列为空队列。
队列满：在某些实现中，特别是使用静态数组实现的队列，当队列无法再添加新元素时，称为队列满。但在使用链表实现的队列中，通常不会遇到队列满的情况，因为链表可以动态扩展。
队列提供了一种有效的方式来管理和处理需要按照特定顺序执行的任务或数据项。通过使用队列，可以确保数据项按照它们被接收或生成的顺序进行处理，这是许多应用中非常关键的要求。
🎄为什么要用单链表实现队列
动态内存分配：
单链表节点是动态分配的，这意味着队列的大小可以根据需要动态地增长和缩小。与静态数组实现的队列不同，单链表队列不需要预先定义最大的容量，从而避免了因队列容量不足而导致的内存溢出问题。高效操作：
在单链表队列中，入队（enqueue）操作通常只需要在链表尾部添加一个节点，时间复杂度为O(1)。出队（dequeue）操作也只需要删除链表头部的节点，时间复杂度同样为O(1)。这使得单链表队列在处理大量数据时具有较高的效率。而数组不方便头插或头删，不管将数组的首部当作队首还是队尾都会降低效率内存利用率：
单链表队列在添加和删除元素时，只需要分配或释放单个节点的内存，而不需要像数组那样可能需要分配或释放整个数据块的内存。这有助于减少内存碎片，提高内存利用率。另外队列只需要对首尾元素进行操作，带尾指针的单链表已经足够高效的进行插入删除，相比双向链表节省了一半的指针空间。灵活性：
单链表队列在结构上相对灵活，可以根据具体需求进行扩展或修改。例如，可以在节点中添加额外的信息以支持更复杂的操作，或者在链表中插入或删除节点以实现特定的功能。易于实现：
单链表的基本操作（如添加节点、删除节点等）相对简单，因此使用单链表实现队列也相对容易。这使得初学者能够更容易地理解和实现队列数据结构。适应性强：
在实际应用中，队列可能会遇到各种复杂的情况，如并发访问、数据异常等。单链表队列由于其动态性和灵活性，能够较好地适应这些复杂情况。例如，在并发环境下，可以使用锁或其他同步机制来确保队列操作的原子性；在数据异常时，可以通过遍历链表来检查和处理异常情况。
二、单链表前情回顾
参考文章：
前置文章：单链表详解
三、队列的结构定义
🍃单个元素的结构定义
- 数据部分
- 指向下一个元素的指针next
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
🍃队列的结构定义
- 指向队首元素的指针phead
- 指向队尾元素的指针ptail
- 队列的元素个数size
// 队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
将队列的首尾指针封装成一个结构体，可以方便函数调用，统一接口
另外使用一个整型变量记录元素个数，利于其他函数功能实现
🍃图解单链表与队列的关系
四、队列的接口实现
🌾初始化
- 对形参判空（接收的地址必须是有效的（队列必须存在）
- 队列的首尾指针初始化为NULL
- size变量初始化为0
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);//接收的地址必须是有效的（队列必须存在）
q->head = q->tail = NULL;
q->size = 0;
}
🌾销毁
- 对形参判空
- 创建指针循环遍历链表: 每次记录下指针的下一个节点，释放指针指向的节点，指针指向下一个节点
- 出循环后，将首尾指针指向NULL
- size置0
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->head)//释放所有节点
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->head = q->tail = NULL;
q->size = 0;
}
🌾入队列（队尾插入）
- 接收两个参数，队列的地址和要插入的数据
- 首先，对形参指针判空
- 然后申请新节点，next指针指向NULL，数据部分为要插入的数据
- 接下来，对空队列和非空队列分别处理:
- 空队列直接让首尾指针都指向新节点
- 非空队列:尾指针指向节点的next指针指向新节点，尾指针再指向新节点
- 完成插入之后，size++
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//判定是否申请成功
{
perror("newnode error\n");
exit(1);
}
newnode->data = data;
newnode->next = NULL;
if (q->head == NULL)//对空队列入队的处理
{
q->head = q->tail = newnode;
}
else //对非空队列入队的处理
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
🌾出队列（队头删除）
- 对形参判空
- 对队列判空
- 队首删除分两种情况
- 队列只有一个元素的情况: 释放该元素空间，首尾指针都指向NULL
- 队列有多个元素的情况: 记录下第二个节点地址，释放首节点，首指针指向第二个节点
- 删除完节点之后，size--
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
if (q->head == q->tail)//对只有一个元素的队列的出队处理
{
free(q->head);
q->head = q->tail = NULL;
}
else //对存在多个元素的队列的出队处理
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
🌾获取队首元素
- 形参判空
- 队列判空
- 返回队首元素的数据
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
return q->head->data;
}
🌾获取队尾元素
- 形参判空
- 队列判空
- 返回队尾元素的数据
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->head);
return q->tail->data;
}
🌾获取队列元素个数
- 形参判空
- 返回size
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
🌾队列判空
- 形参判空
- 返回size==0的结果
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
五、C语言实现代码
Queue.h 队列头文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c 队列实现文件
#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);//接收的地址必须是有效的（队列必须存在）
q->head = q->tail = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//判定是否申请成功
{
perror("newnode error\n");
exit(1);
}
newnode->data = data;
newnode->next = NULL;
if (q->head == NULL)//对空队列入队的处理
{
q->head = q->tail = newnode;
}
else //对非空队列入队的处理
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
if (q->head == q->tail)//对只有一个元素的队列的出队处理
{
free(q->head);
q->head = q->tail = NULL;
}
else //对存在多个元素的队列的出队处理
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->head);
return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->head)//释放所有节点
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->head = q->tail = NULL;
q->size = 0;
}
test.c main函数测试文件
#include"Queue.h"
void test1()
{
Queue Q;
QueueInit(&Q);//创建队列并初始化
if (QueueEmpty(&Q))
printf("队列空\n");
else
printf("队列非空\n");
QueuePush(&Q, 1);//队列插入四个数据
QueuePush(&Q, 2);
QueuePush(&Q, 3);
QueuePush(&Q, 4);
if (QueueEmpty(&Q))
printf("队列空\n");
else
printf("队列非空\n");
printf("%d\n", QueueBack(&Q));//取队尾数据
while (Q.size)//队列不为空时，每次取队首数据，再出队列
{
printf("%d ", QueueFront(&Q));
QueuePop(&Q);
}
printf("\n");
if (QueueEmpty(&Q))
printf("队列空\n");
else
printf("队列非空\n");
QueueDestroy(&Q);//队列销毁
}
int main()
{
test1();
return 0;
}
测试结果
六、应用场景
单链表队列的应用场景非常广泛，几乎在所有需要按照特定顺序处理数据的情况下都可以看到它的身影。以下是一些具体的应用场景示例：
操作系统中的任务调度：在操作系统中，任务（如进程或线程）经常需要按照某种顺序（如优先级、到达时间等）被调度执行。队列可以很好地满足这种需求，确保任务按照预定的顺序被处理。使用单链表实现的队列能够动态地添加和删除任务，非常适合这种场景。
数据包缓冲处理：在网络通信中，数据包经常需要在一个缓冲区中等待处理。队列结构能够确保数据包按照接收的顺序被处理，避免了乱序问题。单链表队列可以方便地添加新接收的数据包到队尾，并从队头取出数据包进行处理。
打印机任务队列：在打印多个文档时，打印机会按照接收文档的顺序进行打印。使用队列可以确保文档按照正确的顺序被处理。单链表队列可以动态地添加新的打印任务，并从队头取出任务进行打印。
事件驱动编程：在事件驱动编程模型中，事件（如用户输入、定时器事件等）会被放入一个事件队列中等待处理。使用队列可以确保事件按照发生的顺序被处理，避免了并发事件导致的混乱。单链表队列可以方便地添加新事件到队尾，并从队头取出事件进行处理。
游戏开发：在游戏中，经常需要处理大量的游戏对象（如玩家、怪物、子弹等）。使用队列可以确保这些对象按照特定的顺序（如创建顺序、优先级等）被更新或渲染。单链表队列可以动态地添加和删除游戏对象，提高游戏的性能和响应速度。
七、总结
通过本文的介绍，我们了解了如何使用单链表来实现队列，并探讨了其在实际应用中的重要性和应用场景。单链表队列具有动态分配内存、无需预先定义大小等优点，能够方便地添加和删除元素，满足各种按照顺序处理数据的需求。无论是在操作系统、网络通信、打印机任务处理、事件驱动编程还是游戏开发中，我们都可以看到单链表队列的身影。因此，掌握单链表队列的实现原理和应用方法对于程序员来说是非常有必要的。希望本文能够帮助读者更好地理解单链表队列的概念和应用，并在实际项目中灵活运用。
- 点赞
- 收藏
- 关注作者
评论（0）