堆、栈和队列(数据结构)

news/2024/9/18 20:45:16/ 标签: 数据结构

堆、栈和队列(数据结构

这里写目录标题

  • 堆、栈和队列(数据结构
      • **栈**
      • **队列**
      • 堆(Heap)()
      • 队列(Queue)(FIFO)
      • 栈(Stack)(LIFO)
      • 总结
    • 堆、队列和栈的内存管理
      • 堆(Heap)
      • 堆内存管理
      • 队列(Queue)
      • 队列内存管理
      • 栈(Stack)
      • 栈内存管理
      • 总结

堆、栈和队列是三种常见的数据结构

标题
堆就像一个可以随时增减的垃圾箱。你可以随时往里面扔东西,也可以随时把不需要的东西拿出来。堆的大小可以根据需要进行扩展或收缩,这使得它非常适合用来存储那些大小不固定的数据,比如动态数组、链表、树和图等。堆的内存管理需要程序员手动进行,使用 malloc()calloc()realloc()free() 函数来分配和释放内存。

栈就像一叠盘子,你只能从最上面的盘子开始取盘子。这就是栈的工作原理。在栈中,数据是按照“最后放入的元素先被取出”的原则进行访问的。栈主要用于存储函数调用相关的数据,如局部变量、返回地址和参数等。栈的大小是固定的,由操作系统或编译器在程序启动时分配。栈的内存管理由编译器自动进行,程序员不需要手动分配和释放栈内存。

队列

队列就像一个排队的地方,新来的排在队伍的后面,先来的排在队伍的前面。这就是队列的工作原理。在队列中,元素按照它们被添加的顺序进行访问。队列主要用于实现先进先出(FIFO)的数据结构,常用于任务调度和消息传递。队列的内存通常是固定的,由操作系统或编译器管理。队列的内存管理也是由编译器自动进行的,程序员不需要手动分配和释放队列内存。

下面是对这三种数据结构的比较:

堆(Heap)()

  • 用途:堆主要用于实现优先队列和动态数据结构,如最大堆和最小堆。
  • 特性:堆是一种树形的数据结构,其中每个节点都有子节点。堆通常用于实现排序和优先级调度算法。
  • 操作:堆的操作包括插入(增加节点)和删除(减少节点)。
  • 访问顺序:堆中的元素可以根据其优先级进行访问,优先级高的元素先被访问。
  • 使用场景:优先队列、动态排序、算法实现(如Dijkstra算法)。

队列(Queue)(FIFO)

  • 用途:队列主要用于实现先进先出(FIFO)的数据结构,常用于任务调度和消息传递。
  • 特性:队列是一种线性数据结构,元素按顺序排列,新元素在队列的一端插入,而旧元素在另一端移除。
  • 操作:队列的操作包括入队(在队尾添加元素)和出队(在队头移除元素)。
  • 访问顺序:队列中的元素按照它们被添加的顺序进行访问。
  • 使用场景:任务调度、消息队列、缓存。
  • 两种常见的实现方式:
    1. 数组队列
      • 使用一个数组来存储队列中的元素。
      • 队头和队尾是数组中的两个指针,分别指向队列中第一个元素和最后一个元素的下一个位置。
      • 当队列满时,无法再添加新元素;当队列空时,没有元素可以取出。
    2. 链表队列
      • 使用链表来存储队列中的元素。
      • 链表中的每个节点包含一个数据元素和一个指向下一个节点的指针。
      • 队头和队尾也是两个指针,分别指向队列中第一个元素和最后一个元素的下一个位置。
      • 队列的大小可以根据需要动态变化,不像数组队列那样受限于数组的大小。

栈(Stack)(LIFO)

  • 用途:栈主要用于实现后进先出(LIFO)的数据结构,常用于函数调用、表达式求值和数据暂存。
  • 特性:栈是一种线性数据结构,元素按顺序排列,新元素在栈顶添加,旧元素在栈顶移除。
  • 操作:栈的操作包括压栈(在栈顶添加元素)和弹栈(从栈顶移除元素)。
  • 访问顺序:栈中的元素按照它们被添加的顺序进行访问。
  • 使用场景:函数调用、递归、后缀表达式求值。

总结

  • :用于实现优先队列和动态数据结构,操作复杂,适用于需要优先级排序的场景。
  • 队列:用于实现先进先出(FIFO)的数据结构,操作简单,适用于需要顺序处理的场景。
  • :用于实现后进先出(LIFO)的数据结构,操作简单,适用于需要后入先出的场景。
    每种数据结构都有其特定的应用场景和优势。在实际编程中,选择合适的数据结构可以大大提高程序的效率和性能。

堆、队列和栈的内存管理

堆(Heap)

  • 内存管理:堆是动态分配的内存区域,它允许程序在运行时请求任意大小的内存。堆上的内存由程序员手动管理,包括分配和释放。
  • 内存泄漏:由于堆上的内存需要程序员负责管理,如果程序员忘记释放不再需要的内存,就会导致内存泄漏。
  • 避免内存泄漏:为了避免内存泄漏,程序员应该在不再需要动态分配的内存时,使用 free() 函数将其释放。

堆内存管理

#include <stdio.h>
#include <stdlib.h>int main() {int *ptr;// 分配内存ptr = (int *)malloc(10 * sizeof(int));if (ptr == NULL) {// 内存分配失败exit(1);}// 使用内存for (int i = 0; i < 10; i++) {ptr[i] = i; // 初始化内存}// 释放内存free(ptr); // 释放内存return 0;
}

队列(Queue)

  • 内存管理:队列通常是基于数组或链表实现的,它们的内存管理方式与堆不同。队列的内存通常是固定的,由操作系统或编译器管理。
  • 内存泄漏:由于队列的内存通常是固定的,因此不太可能发生内存泄漏。
  • 避免内存泄漏:对于基于数组或链表的队列,通常不需要担心内存泄漏,因为它们的内存是由操作系统或编译器管理的。

队列内存管理

#include <stdio.h>
#include <stdlib.h>struct Node {int data;struct Node *next;
};int main() {struct Node *head = NULL, *newNode, *temp;// 动态分配内存newNode = (struct Node *)malloc(sizeof(struct Node));newNode->data = 1;newNode->next = NULL;head = newNode;// 使用队列while (1) {// 模拟队列操作}// 释放队列内存while (head != NULL) {temp = head;head = head->next;free(temp);}return 0;
}

栈(Stack)

  • 内存管理:栈是后进先出(LIFO)的数据结构,它由操作系统自动管理。栈的大小通常是固定的,不会在运行期间改变。
  • 内存泄漏:由于栈的内存是自动管理的,因此不太可能发生内存泄漏。
  • 避免内存泄漏:对于栈,通常不需要担心内存泄漏,因为它的内存是由操作系统管理的。

栈内存管理

#include <stdio.h>int main() {int a, b, c;// 局部变量a = 1;b = 2;c = a + b;// 栈上的变量在函数返回时自动销毁printf("c = %d\n", c);return 0;
}

总结

堆上的内存需要程序员手动管理,容易发生内存泄漏。为了避免内存泄漏,程序员应该在不再需要动态分配的内存时,使用 free() 函数将其释放。队列和栈的内存通常是自动管理的,因此不太可能发生内存泄漏。

在实际编程中,避免内存泄漏的最佳实践包括:

  • 对于堆内存,使用 malloc()calloc()realloc()free() 函数进行管理。
  • 对于队列和栈,通常不需要担心内存泄漏,因为它们的内存是由操作系统或编译器管理的。
  • 编写良好的代码,确保在不再需要内存时及时释放。
  • 使用内存泄漏检测工具来发现潜在的问题。
  • 遵循良好的编程习惯,如避免全局变量和静态变量,尽量使用局部变量和动态内存分配。

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

相关文章

【C++】15.二叉搜索树

一、二叉搜索树的概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值它的左…

vue中缩放比的使用

大屏适用性比较大&#xff0c;后台系统不推荐 抽组件&#xff0c;scaleScreen <template><divid"screen":style"{width: ${style.width}px,height: ${style.height}px,transform: ${style.transform},}"><slot ></slot></div&g…

leetcode:2833. 距离原点最远的点(python3解法)

难度&#xff1a;简单 给你一个长度为 n 的字符串 moves &#xff0c;该字符串仅由字符 L、R 和 _ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。 你的初始位置就在原点&#xff08;0&#xff09;&#xff0c;第 i 次移动过程中&#xff0c;你可以根据对应字符选择…

debian固定ip

debian固定ip 前言 安装好的Debian系统后&#xff0c;为了确保每次登陆的ip不变&#xff0c;需要固定 方法 命令如下 ip addr | grep inet因为有有线网和无线网 2 种连接方式&#xff0c;因此需要区别。 其中 enp 的是有线&#xff0c;wlp 的是无线 查看网关 IP 命令如下 …

Jenkins中Node节点与构建任务

目录 节点在 Jenkins 中的主要作用 1. 分布式构建 分布式处理 负载均衡 2. 提供不同的运行环境 多平台支持 特殊环境需求 3. 提高资源利用率 动态资源管理 云端集成 4. 提供隔离和安全性 任务隔离 权限控制 5. 提高可扩展性 横向扩展 高可用性 Jenkins 主服务…

Elasticsearch索引管理和生命周期管理

在大数据和搜索引擎技术日益成熟的今天&#xff0c;Elasticsearch作为一款基于Lucene构建的开源搜索引擎&#xff0c;凭借其强大的全文搜索能力、分布式架构以及可扩展性&#xff0c;在日志分析、实时监控、应用搜索等多个领域得到了广泛应用。然而&#xff0c;随着数据量的不断…

前端框架入门之Vue _el和data的两种写法 分析MVVM模型

目录 _el与data的两种写法 MVVM模型 _el与data的两种写法 查看vue的实例对象 我们在这边注释掉了el属性 这样的话div容器就绑定不了vue实例 当我们可以在这里写一个定时任务 然后再回头指定 这个mount有挂载的意思 就是把容器对象交给vue实例后 去给他挂载指定的对象 &…

网络基础:Vlan原理与配置

VLAN&#xff08;Virtual Local Area Network&#xff0c;虚拟局域网&#xff09;是一种将一个物理网络划分为多个逻辑子网的技术。它通过在网络交换机上配置&#xff0c;使得不同VLAN中的设备即使连接在同一个物理交换机上&#xff0c;也不能直接进行通信&#xff0c;从而实现…

10校大满贯!中国内地高校2024年1-6月CNS发文统计出炉

随着全球科研竞争的日趋激烈&#xff0c;CNS&#xff08;Cell、Nature、Science&#xff09;作为科学领域的三大顶级期刊&#xff0c;不仅是科研成果的展示平台&#xff0c;更是各国科研实力比拼的重要战场。近年来&#xff0c;中国高校在国际科研舞台上的表现愈发抢眼&#xf…

vuepress 配置文件分类管理

背景 在.vuepress的config.js配置文件中&#xff0c;我们需要设置head, plugins, nav三项主要配置。 如果都写在config.js就会显得很臃肿&#xff0c;不便于维护。 代码 config.js const headConf require("./config/headConf"); const pluginsConf require(&q…

Hadoop3:HDFS-集群安全模式

一、基本介绍 1、安全模式 文件系统只接受读数据请求&#xff0c;而不接受删除、修改等变更请求 2、 二、进入安全模式场景 1、NameNode在加载镜像文件和编辑日志期间处于安全模式&#xff08;就是启动集群的时候&#xff09;&#xff1b; 2、NameNode再接收DataNode注册时…

深入解析HTTP与HTTPS:定义、架构、原理、应用场景及实战指南

前言 在互联网技术飞速发展的今天&#xff0c;HTTP&#xff08;Hypertext Transfer Protocol&#xff09;和HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;已经成为Web通信的基础协议。无论是浏览网页、提交表单&#xff0c;还是进行数据交互&#xff0c;HT…

Apache Omid TSO 组件源码实现原理

Apache Omid TSO 组件实现原理 作用 独立进程&#xff0c;处理全局事务之间的并发冲突。 流程 TSOChannelHandler#channelRead -> AbstractRequestProcessor -> PersistenceProcessorHandler 总体流程 thread1TSOChannelHandler#channelReadAbstractRequestProcess…

c语言唯一一个三目运算符

条件表达式由两个符号&#xff08;&#xff1f;和&#xff1a;&#xff09;组成&#xff0c;必须一起使用。要求有三个操作对象&#xff0c;称为三目运算符。 一般形式为 表达式1&#xff1f;表达式2&#xff1a;表达式3 理解如下&#xff1a; a>b?(maxa):(maxb); //相当…

微调 Florence-2 - 微软的尖端视觉语言模型

Florence-2 是微软于 2024 年 6 月发布的一个基础视觉语言模型。该模型极具吸引力&#xff0c;因为它尺寸很小 (0.2B 及 0.7B) 且在各种计算机视觉和视觉语言任务上表现出色。 Florence 开箱即用支持多种类型的任务&#xff0c;包括: 看图说话、目标检测、OCR 等等。虽然覆盖面…

Win10+Docker环境使用YOLOv8 TensorRT推理加速

这一部分内容和WSL-Ubuntu20.04环境使用YOLOv8 TensorRT推理加速-CSDN博客 是基本相同的,有细微差别我也会在文中指出来。 1.TensorRTX下载 这里使用Wang-xinyu大佬维护的TensorRTX库来对YOLOv8进行推理加速的演示,顺便也验证一下前面环境配置的成果。 github地址:GitHub -…

【STM32 ARM】操作寄存器控制led

文章目录 前言GPIO操作方法led原理图设置时钟APB的概念 设置APB设置输出引脚设置引脚高低电平寄存器寻找寄存器地址 总结 前言 STM32是STMicroelectronics&#xff08;意法半导体&#xff09;公司的一款32位Flash微控制器产品&#xff0c;基于ARM Cortex™-M内核。STM32系列微…

NDK R25b 交叉编译FFMpeg4,项目集成,附库下载地址

1.准备工作 文件下载&#xff1a; NDK R25b下载地址&#xff1a;Android NDK历史版本下载网址 - 君*邪 - 博客园 (cnblogs.com) FFmpeg4.4.4 下载地址&#xff1a;https://ffmpeg.org/releases/ffmpeg-4.4.4.tar.xz 环境配置&#xff1a; 本次编译环境是在PC虚拟机中使用U…

【LeetCode力扣】006. Z 字形变换(Python)

最快解法 参考了运行时间最短的代码&#xff0c;其使用的思路就是按列排序后连接。 class Solution:def convert(self, s: str, numRows: int) -> str:if numRows < 2 : # numRows1时候&#xff0c;对应输出为原字符串return sn len(s)lst [ for _ in range(numRows…

“论软件维护方法及其应用”写作框架,软考高级论文,系统架构设计师论文

论文真题 软件维护是指在软件交付使用后&#xff0c;直至软件被淘汰的整个时间范围内&#xff0c;为了改正错误或满足 新的需求而修改软件的活动。在软件系统运行过程中&#xff0c;软件需要维护的原因是多种多样的&#xff0c; 根据维护的原因不同&#xff0c;可以将软件维护…