现在做网站用什么,wordpress怎样上传目录本,制作网站网络科技公司,wordpress 主题 the7在计算机科学中#xff0c;**队列#xff08;Queue#xff09;**是一种常见的数据结构#xff0c;它遵循先进先出#xff08;FIFO#xff0c;First In First Out#xff09;的原则。队列的应用非常广泛#xff0c;例如任务调度、资源管理、进程通信等。本篇文章旨在为计…在计算机科学中**队列Queue**是一种常见的数据结构它遵循先进先出FIFOFirst In First Out的原则。队列的应用非常广泛例如任务调度、资源管理、进程通信等。本篇文章旨在为计算机专业的初学者详细讲解队列的多种实现方式并通过 C 的代码示例让读者更好地理解和掌握这些概念和底层原理及优缺点。 本篇文章需要读者具有队列的基本知识文内会简略介绍若不清楚什么是队列可参考以下文章 【计算机科学】深入理解队列有序的数据之道【数据结构】快慢指针探秘理解链表与数组中的环结构 全文共计4020字耗时5天缝缝补补完成若能够让你学到新知识你可以给我点个或者关注。 文章目录 队列的作用队列的基本操作队列的多种手动实现方式**1. 基于纯数组的简单实现****特点****手动实现时的注意事项** **2. 基于数组的循环队列****特点****手动实现时的注意事项** **3. 基于链表的队列****特点****手动实现时的注意事项** **4. 基于带头节点的链表队列****特点****手动实现时的注意事项** **5. 基于数组的循环队列无额外标志位实现****特点****手动实现时的注意事项****代码** **6. 基于数组的循环队列带标志位实现****特点****手动实现时的注意事项****代码** 总结 队列的作用
队列的主要作用是按照顺序存储和管理数据其常见应用包括
任务调度 队列可用于管理任务执行的先后顺序例如操作系统中的进程调度。数据缓冲 在流式数据处理中队列用于暂存数据。广度优先搜索BFS 在图或树的遍历中队列是关键的数据结构。 我们会在后期的内容中带来队列应用的实战内容。 队列的基本操作
一个队列通常包含以下几个操作
enqueue入队 将元素加入队列尾部。dequeue出队 从队列头部移除并返回元素。isEmpty判空 判断队列是否为空。isFull判满可选 判断队列是否已满通常适用于基于数组的实现。 若对队列的概念还是比较模糊强烈再去复习一下队列的基本知识 【计算机科学】深入理解队列有序的数据之道 队列的多种手动实现方式 1. 基于纯数组的简单实现
这种实现方式是队列的最基础版本直接用一个固定大小的数组来存储队列元素按照先进先出的顺序操作。队列的front和rear指针分别指向队头和队尾所有元素插入到队尾从队头取出。
特点 优点 实现简单逻辑清晰适合入门学习队列概念。内存分配静态化不依赖额外数据结构直接在数组上操作。 缺点 空间浪费问题 由于数组不循环当rear到达数组末尾时即使front前面有空余空间队列也会被认为已满。大小固定 必须在初始化时确定数组的大小缺乏灵活性。
手动实现时的注意事项
边界判断 要确保在插入时判断队列是否已满在删除时判断队列是否为空否则可能会导致数组越界或错误访问。队列空判断 通常通过front rear判断队列为空。队列满判断 当rear maxSize时需要提示队列已满。动态调整难度 该实现不支持动态扩展数组大小需要手动扩展时增加实现难度。
#include iostream
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize size;arr new int[size];front rear 0;}~Queue() {delete[] arr;}bool isEmpty() {return front rear;}bool isFull() {return rear maxSize; // 队列满的条件}void enqueue(int x) {if (isFull()) {cout Queue is full! endl;return;}arr[rear] x;}int dequeue() {if (isEmpty()) {cout Queue is empty! endl;return -1;}return arr[front];}
};2. 基于数组的循环队列
循环队列是对纯数组实现的改进通过将数组逻辑上看作是环形结构解决了纯数组实现中空间浪费的问题。
特点 优点 高效利用内存 通过循环的方式重新利用之前已释放的空间提高数组的空间利用率。操作简单 只需要在插入和删除操作中使用模运算即可实现循环。 缺点 逻辑复杂度增加 需要通过模运算来控制数组的循环需要仔细处理front和rear的关系。固定大小 和纯数组一样循环队列的大小也是固定的无法动态扩展。
手动实现时的注意事项
队列满和空的判断 无标志位实现 通常通过(rear 1) % maxSize front判断队列已满rear front判断队列为空。需要注意这种实现中队列最多只能使用maxSize - 1个空间。带标志位实现 引入tag标志位后可以清楚区分队列满和空的状态rear front 时配合tag判断队列状态。 模运算的正确性 循环队列依赖模运算控制指针确保数组不会越界。初始化边界条件 在队列为空或刚初始化时front和rear应该相等。特殊情况的处理 需要处理rear追上front的情况以及空队列状态下访问的错误提示。
#include iostream
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize size;arr new int[size];front rear 0;}~Queue() {delete[] arr;}bool isEmpty() {return front rear;}bool isFull() {return (rear 1) % maxSize front; // 循环条件}void enqueue(int x) {if (isFull()) {cout Queue is full! endl;return;}arr[rear] x;rear (rear 1) % maxSize;}int dequeue() {if (isEmpty()) {cout Queue is empty! endl;return -1;}int res arr[front];front (front 1) % maxSize;return res;}
};3. 基于链表的队列
基于链表的队列是动态存储的实现方式不依赖固定大小的数组通过链表的动态特性解决了内存限制问题。
特点 优点 灵活性强 队列大小不固定可以根据需求动态分配和释放内存。无队列满的情况 只要系统内存允许就可以插入任意多的元素。 缺点 复杂性增加 需要维护链表的动态分配和释放逻辑代码实现比数组队列复杂。内存开销 每个节点需要额外的指针存储整体占用内存比数组略高。
手动实现时的注意事项
链表初始化 确保front和rear指针正确初始化为空。边界条件 在插入第一个元素时需要同时更新front和rear指针。内存管理 每次插入时动态分配内存删除时释放内存避免内存泄漏。空队列判断 当front nullptr时队列为空。队列尾处理 当删除最后一个元素后需要将rear指针置为空。
#include iostream
using namespace std;struct Node {int value;Node *next;Node(int v) : value(v), next(nullptr) {}
};struct Queue {
private:Node *front, *rear;
public:Queue() {front rear nullptr;}~Queue() {while (front ! nullptr) {Node *temp front;front front-next;delete temp;}}bool isEmpty() {return front nullptr;}void enqueue(int x) {Node *newNode new Node(x);if (isEmpty()) {front rear newNode;} else {rear-next newNode;rear newNode;}}int dequeue() {if (isEmpty()) {cout Queue is empty! endl;return -1;}int res front-value;Node *temp front;front front-next;delete temp;if (!front) rear nullptr; // 更新rearreturn res;}
};4. 基于带头节点的链表队列
在链表实现的基础上加入一个不存储数据的头节点用来简化操作逻辑。
特点 优点 边界处理简化 由于头节点始终存在可以统一插入和删除操作的逻辑不需要处理链表为空时的特殊情况。灵活性 与普通链表队列一样支持动态扩展内存利用高。 缺点 稍微增加内存占用 需要额外的头节点占用少量额外内存。实现复杂度增加 需要手动维护头节点和尾节点的指针。
手动实现时的注意事项
头节点初始化 确保头节点的next指针初始化为空头节点本身可以设置一个哨兵值。插入操作 在队列为空时需要同时更新front-next和rear。删除操作 从front-next开始删除节点当删除最后一个节点后需要将rear置为空。内存管理 同样需要确保每次操作后正确释放删除节点的内存。
#include iostream
using namespace std;struct Node {int value;Node *next;Node(int v) : value(v), next(nullptr) {}
};struct Queue {
private:Node *front, *rear;
public:Queue() {front new Node(-1); // 带头节点rear nullptr;}~Queue() {while (front ! nullptr) {Node *temp front;front front-next;delete temp;}}bool isEmpty() {return rear nullptr;}void enqueue(int x) {Node *newNode new Node(x);if (isEmpty()) {front-next newNode;rear newNode;} else {rear-next newNode;rear newNode;}}int dequeue() {if (isEmpty()) {cout Queue is empty! endl;return -1;}Node *temp front-next;int res temp-value;front-next temp-next;if (!front-next) rear nullptr; // 更新reardelete temp;return res;}
};5. 基于数组的循环队列无额外标志位实现
循环数组队列无标志位的实现是一种改进版的队列数组逻辑上被看作环形。它通过模运算实现“循环”效果从而提高了数组的空间利用率。
特点 优点 空间利用率高 不会像纯数组实现那样浪费数组前端的可用空间。实现较为简单 通过模运算控制指针即可实现循环逻辑清晰。 缺点 浪费一个存储单元 为了区分队列空和满的情况最多只能使用maxSize - 1个存储单元。固定大小 和所有数组实现一样大小固定无法动态扩展。
手动实现时的注意事项
边界条件 通过(rear 1) % maxSize front判断队列已满通过rear front判断队列为空。模运算正确性 插入和删除时需要使用模运算来实现循环效果避免指针越界。初始化 队列初始化时front和rear均指向数组的起始位置队列为空。大小限制 实际可用空间为maxSize - 1需要特别注意数组容量的计算和使用。
代码
#include iostream
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize size;arr new int[size];front rear 0;} ~Queue() {delete[] arr;}bool isFull() {return (rear 1) % maxSize front; // 判断队列满}bool isEmpty() {return front rear; // 判断队列空}void enqueue(int x) {if (isFull()) {cout Queue is full. endl;return;}arr[rear] x; // 在队尾插入rear (rear 1) % maxSize; // 更新 rear模运算实现循环}int dequeue() {if (isEmpty()) {cout Queue is empty. endl;return -1; }int res arr[front]; // 取出队头元素front (front 1) % maxSize; // 更新 front模运算实现循环return res;}
};6. 基于数组的循环队列带标志位实现
循环数组队列带标志位的实现是在无标志位版本的基础上引入一个tag标志位来明确区分队列空和满的情况。这种实现避免了浪费一个存储单元的问题。
特点 优点 空间利用率最高 不会像无标志位版本那样浪费一个存储单元可以使用整个数组存储数据。状态区分清晰 通过tag标志位清楚地表示当前队列是空还是满。 缺点 实现稍复杂 相比无标志位版本多了tag标志位的更新逻辑。固定大小 依然受数组大小限制无法动态扩展。
手动实现时的注意事项
标志位的维护 在enqueue时如果插入后rear front需要将tag置为1表示队列满。在dequeue时如果删除后rear front需要将tag置为0表示队列空。 边界条件 队列空的判断条件front rear tag 0。队列满的判断条件front rear tag 1。 初始化 front和rear指针初始化为0tag初始化为0表示队列为空。模运算 和无标志位版本类似通过模运算实现循环效果。
代码
#include iostream
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize, tag;
public:Queue(int size) {maxSize size;arr new int[size];front rear 0;tag 0; // 初始状态为空}~Queue() {delete[] arr;}bool isEmpty() {return front rear tag 0; // 队列空front rear 且 tag 为 0}bool isFull() {return front rear tag 1; // 队列满front rear 且 tag 为 1}void enqueue(int x) {if (isFull()) {cout Queue is full. endl;return;}arr[rear] x; // 在队尾插入rear (rear 1) % maxSize; // 更新 rearif (rear front) tag 1; // 如果 rear 追上 front则队列满tag 置为 1}int dequeue() {if (isEmpty()) {cout Queue is empty. endl;return -1;}int res arr[front]; // 取出队头元素front (front 1) % maxSize; // 更新 frontif (rear front) tag 0; // 如果 front 追上 rear则队列空tag 置为 0return res;}
};总结
实现方式优点缺点适用场景纯数组队列1. 实现简单适合入门学习。2. 适合小规模的简单场景。1. 空间利用率低出队后前部空间不可复用。2. 数组固定大小无法动态扩展。小型队列数据量较少且操作较简单的场景。循环数组队列无标志位1. 空间利用率高支持循环操作。2. 实现逻辑相对清晰易于理解。1. 浪费一个存储单元最大可用容量为maxSize - 1。2. 边界条件复杂容易出错。小型队列数据量适中且对空间利用有一定要求。循环数组队列带标志位1. 空间利用率最高无存储浪费。2. 状态明确通过标志位区分队列空与满的状态。1. 实现稍复杂需要维护标志位的逻辑。2. 数组固定大小仍无法动态扩展。数据量较大且对空间利用率有高要求的场景。链表队列无头节点1. 动态分配空间无需固定大小支持数据量变化。2. 空间利用率高无浪费。1. 实现稍复杂需要手动管理内存。2. 操作链表时可能存在额外的时间和内存开销。数据量不确定或需要动态调整大小的场景。链表队列带头节点1. 动态分配空间支持大小变化。2. 带头节点的设计简化了插入和删除操作逻辑。1. 实现复杂度高需要维护链表和头节点。2. 内存利用率高但链表操作较慢。数据动态变化且需要更高鲁棒性的场景。链表队列带尾指针1. 通过尾指针优化入队操作性能更高。2. 动态空间分配适应数据量变化。1. 内存分配和释放较复杂容易出现内存泄漏问题。2. 指针操作复杂度较高需小心处理边界。数据量较大需频繁插入删除的场景。
推荐选择依据
如果你是初学者或实现简单队列纯数组队列是一个不错的起点。如果需要循环结构并注重空间利用率选择循环数组队列无标志位**或**循环数组队列带标志位根据是否需要完整利用空间来决定。如果需要动态扩展且操作数据频繁链表队列是最佳选择根据是否需要头节点或尾指针进一步优化。
理解每种实现的原理和优缺点是学习数据结构的重要步骤。希望本文能够帮助你掌握队列的基本概念及实现方式同时若本文帮助到了你你可以给我点个赞和关注以支持我继续创作。
