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