【数据结构】从数据结构角度深入探究队列

news/2024/11/20 23:33:40/

队列是计算机科学中的一种基本数据结构，用于存储和管理数据。在计算机程序中，队列被广泛应用于任务调度、进程管理等场景。本文将介绍队列的概念、特点、常见操作以及应用。

文章目录

  • 队列的概念
  • 队列的应用
  • 队列的存储结构
  • 队列接口的实现
    • 队列的初始化
    • 队尾入队列
    • 队头出队列
    • 获取队列头部元素
    • 获取队列队尾元素
    • 获取队列中有效元素个数
    • 检测队列是否为空
    • 销毁队列
  • 总结

队列的概念

你们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算reset时，突然它像酒醒了一样，把你刚才单击的所有操作全部都按顺序执行了一遍,这是因为操作系统在当时可能CPU一时忙不过来，等前面的事忙完后，后面多个指令需要通过一个通道输出，按先后次序排队执行造成的结果。所以在这操作系统中，是应用了一种数据结构来实现刚才提到的先进先出的排队功能，这就是队列。

  • 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头.
  • 队列的特点

队列具有以下几个特点：

  1. 先进先出。最早进入队列的元素在队列中排在最前面，最后进入队列的元素排在最后面。
  2. 只能在队列的前端执行出队操作，在队列的后端执行入队操作。

在这里插入图片描述

队列的应用

队列在计算机程序中有很多应用场景，下面介绍其中几个常见的应用。

  1. 消息传递:
    在消息传递模型中，消息被发送到队列中等待接收方进行处理。发送方可以通过入队操作向队列发送消息，而接收方则通过出队操作从队列中获取消息。
  2. 缓存
    在网络通信中，缓存被广泛应用于加速数据传输。当一个请求到达时，它可能需要从远程服务器中获取数据，这个过程需要等待一定时间。为了避免每次请求都需要重新获取数据，可以将数据缓存在本地队列中。当下一次请求到达时，可以直接从队列中获取数据，避免了等待时间。
  3. 任务调度
    在许多系统中，任务必须按照一定的顺序进行处理。例如，操作系统中的进程调度就是一种任务调度。当一个进程被创建时，它会被添加到系统的任务队列中等待处理。调度器通过出队操作从队列中选择下一个要执行的进程，并将其分配给CPU执行。
  • 总的来说队列是计算机科学中非常重要的一种数据结构，具有先进先出的特点。队列通过入队和出队操作管理数据，常见的应用场景包括任务调度、消息传递和缓存等。对于程序员来说，了解队列的基本概念和常见操作是非常必要的。

队列的存储结构

队列可以使用数组或者链表的结构来实现，那哪一个存储结构更加优呢？下面我们来分析他们在队列中存储各自的优缺点。

  • 数组存储结构的优点：
    1 . 数组在内存中是连续存储的，因此访问元素时速度较快。CPU高速缓存命中率会更高。
    2 . 数组实现相对简单，不需要额外的指针来维护元素之间的关系。
  • 数组存储结构的缺点
    1 . 需要事先确定队列的最大长度，这可能会导致性能下降。
    2 . 需要移动元素来保持队列的顺序.
  • 链式存储的优点
    1 . 不需要事先确定队列的最大长度，可以动态扩展.
    2 . 插入和删除操作只需要修改指针，不需要移动元素.
    3 . 可以实现多个队列共享一个链表
  • 链式存储的缺点
    1 . CPU高速缓存命中率会更低,不是连续存储的，因此访问元素时速度较慢。
    2 .实现相对复杂。
  • 终言： 使用链表的结构实现更优一些,因为数据存储有一个致命的缺点就是大量挪动元素。

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针head指向链队列的头结点，而队尾tail尾指针指向终端结点.。

// 定义队列节点结构体
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next; // 指向下一个节点的指针QDataType data; // 节点数据
}QNode;// 定义队列结构体
typedef struct Queue
{QNode* phead; // 队列头指针，指向第一个节点QNode* ptail; // 队列尾指针，指向最后一个节点int size; // 队列大小，即节点数量
}Queue;

在这个链表中，每个节点包含两个成员变量：指向下一个节点的指针和节点数据。队列结构体中包含头指针、尾指针和节点数量三个成员变量。头指针指向队列的第一个节点，尾指针指向队列的最后一个节点，节点数量表示队列中节点的数量。由于是单向链表，所以只需要维护头指针和尾指针就可以实现入队和出队操作。

队列接口的实现

队列的初始化

  • 先把队列元素全部置空，size置0.
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

队尾入队列

在这里插入图片描述

  • 详细步骤已放代码注释,以下是该入队列核心思路.
    1. 如果队列为空，将头指针和尾指针都指向新节点。
    2. 如果队列不为空，将尾指针指向新节点，并将前一个节点的指向下一个节点的指针更新为新节点。
void QueuePush(Queue* pq, QDataType x)
{assert(pq); // 断言：如果传入的队列 pq 为空，程序将停止运行并提示错误。// 创建新节点 newnode 并为其分配内存空间。QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n"); // 如果分配空间失败，则程序将输出一条错误信息。return;}// 设置新节点的数据和指针值。newnode->data = x; // 新节点中储存的数据值为变量 x。newnode->next = NULL; // 新节点的指向下一个节点的指针初始值设为 NULL。// 将新节点加入队列末尾。if (pq->ptail == NULL) // 如果队列为空（没有节点），则头指针和尾指针均指向新节点。{assert(pq->phead == NULL); // 确认队首指针也为 NULL。pq->phead = pq->ptail = newnode;}else // 否则，仅将尾指针指向新节点，并将前一个节点的指向下一个节点的指针更新为新节点。{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++; // 队列长度加一。
}

队头出队列

  • 详细步骤已放代码注释,以下是该入队列核心思路.
    1 . 出队列前要判断该队列是否为空.
    2 . 如果队列中只有一个节点，即头指针和尾指针指向同一个节点，则释放头结点.并将将头指针和尾指针均置为NULL.
    3 . 如果队列中有不止一个节点，即头指针和尾指针指向不同的节点，则保存头结点的下一个节点，释放头结点，将头指针指向下一个节点.
void QueuePop(Queue* pq)
{assert(pq);  // 判断参数pq是否为空assert(!QueueEmpty(pq));  // 判断队列是否为空if (pq->phead->next == NULL)  // 如果队列中只有一个节点{free(pq->phead);  // 释放头结点pq->phead = pq->ptail = NULL;  // 将头指针和尾指针均置为NULL}else  // 如果队列中有不止一个节点{QNode* next = pq->phead->next;  // 保存头结点的下一个节点free(pq->phead);  // 释放头结点pq->phead = next;  // 将头指针指向下一个节点}pq->size--;  // 减小队列的大小
}

获取队列头部元素

  • 需要注意的是要判断该队列是否为空.如不为空，则返回队列头节点的数据域。
QDataType QueueFront(Queue* pq)
{assert(pq);  // 判断参数pq是否为空assert(!QueueEmpty(pq));  // 判断队列是否为空return pq->phead->data;  // 返回头结点所指向节点的数据值
}

获取队列队尾元素

  • 需要注意的是要判断该队列是否为空…如不为空，则返回队列尾节点的数据域。
QDataType QueueBack(Queue* pq)
{assert(pq);  // 判断参数pq是否为空assert(!QueueEmpty(pq));  // 判断队列是否为空return pq->ptail->data;  // 返回尾结点所指向节点的数据值
}

获取队列中有效元素个数

  • 返回队列的成员变量size的值即可.
int QueueSize(Queue* pq)
{assert(pq);  // 判断参数pq是否为空return pq->size;  // 返回队列的成员变量size的值
}

检测队列是否为空

  • 判断队列的成员变量size是否为0，如果为0则说明队列为空，返回true，否则返回false。
bool QueueEmpty(Queue* pq)
{assert(pq);  // 判断参数pq是否为空return pq->size == 0;  // 如果队列为空，返回true，否则返回false
}

销毁队列

  • 详细步骤已放代码注释，需要注意的是每次销毁节点时，要保存它下一个节点。
void QueueDestroy(Queue* pq)
{assert(pq);  // 判断参数pq是否为空QNode* cur = pq->phead;  // 定义一个指针cur指向队列头结点pq->phead。while (cur)  // 利用while循环遍历链表{QNode* next = cur->next;  // 定义一个指针next指向当前节点的下一个节点。free(cur);  // 释放当前节点的内存。cur = next;  // 将cur指向next节点。}pq->phead = pq->ptail = NULL;  // 将队列头结点和尾结点置为NULL。pq->size = 0;  // 将队列大小设置为0。
}

总结

  • 链式队列不需要移动元素，因此相比于顺序队列，链式队列的空间利用率更高。. 链式队列的缺点是需要额外的空间存储指针，因此相比于顺序队列，链式队列的空间复杂度更高。总之，链式队列是一种高效、灵活的队列数据结构，适用于需要频繁进行入队和出队操作的场景。

  • 队列是一种简单但非常有用的数据结构，掌握它的基本概念、操作和实现方式对于编程学习和刷题，后面的面试都非常重要。


http://www.ppmy.cn/news/81966.html

相关文章

从传统开发到低代码：这是一次技术革命

从传统开发到低代码：这是一次技术革命

近年来，随着人工智能等新兴技术的快速发展，软件开发行业也在不断演变。传统的软件开发流程需要大量的编程知识和时间，而且往往需要复杂的架构和开发环境。然而，随着低/无代码平台的出现，软件开发变得更加高效、简单和普…
阅读更多...
电表及配电监控系统的智能化发展

电表及配电监控系统的智能化发展

安科瑞虞佳豪 在电力领域，AI渗透率近年来也持续提升。今年3月，国家能源局发布《关于加快推进能源数字化智能化发展的若干意见》，文件中针对电力、、油气等行业数字化智能化转型，明确了指导思想和基本原则，从加快行业转…
阅读更多...
NVDIA GPU参数列表： 3090，4090， A40， A30，V100， A100， A800性能参数

NVDIA GPU参数列表： 3090，4090， A40， A30，V100， A100， A800性能参数

GeForce RTX 4090 GeForce RTX 3090 Ti （左） GeForce RTX 3090（右） A40： The NVIDIA A40 accelerates the most demanding visual computing workloads from the data center, combining the latest NVIDIA Ampere …
阅读更多...
设计模式之开闭原则(内附代码展示)

设计模式之开闭原则(内附代码展示)

开闭原则是面向对象设计中最基本的原则之一，它的核心思想是一个软件实体应该对扩展开放，对修改关闭。换句话说，当需要扩展一个模块的功能时，应该通过增加代码来实现，而不是修改原有的代码。 开闭原则的实现需要遵循以…
阅读更多...
day18 - 使用直方图提高图像对比度

day18 - 使用直方图提高图像对比度

本期将使用图像直方图的相关知识来提高图像对比度，对图像进行优化，从而提高图像清晰度。 完成本期内容，你可以： 了解图像直方图的定义和计算方法了解直方图均衡化的原理学会使用直方图均衡化优化图像 若要运行案例代码&#xf…
阅读更多...
快手新财报：曙光就在冲刺路上？

快手新财报：曙光就在冲刺路上？

自短视频爆火以来，短视频行业的头部玩家——抖音和快手就迎来了飞速发展，甚至一度成为了国民“杀时间利器”。然而，随着互联网红利逐渐见顶，短视频行业竞争加剧，哪怕作为头部玩家，快手的日子也并不好过。 …
阅读更多...
随想011：关于编程

随想011：关于编程

1945 年时，刚开始有计算机，那时候使用二进制数编程到了40年代末期，出现了汇编器，可以自动将汇编程序转换为二进制数序列1951 年 Grace Hopper 发明了编译器1957 年，Fortran，第一个高级语言，首次…
阅读更多...
Flutter 笔记 | Flutter 布局组件

Flutter 笔记 | Flutter 布局组件

布局类组件都会包含一个或多个子组件，布局类组件都是直接或间接继承SingleChildRenderObjectWidget 和MultiChildRenderObjectWidget的Widget，它们一般都会有一个child或children属性用于接收子 Widget。 不同的布局类组件对子组件排列（layo…
阅读更多...
最新文章

Copyright @ 2022~2023