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

devtools/2024/9/19 13:30:55/ 标签: 数据结构

堆、栈和队列(数据结构

这里写目录标题

  • 堆、栈和队列(数据结构
      • **栈**
      • **队列**
      • 堆(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/devtools/59444.html

相关文章

搜维尔科技:通过 Xsens MVN Link 套装测试动作捕捉动画,由虚幻引擎5渲染

通过Xsens MVN Link套装测试动作捕捉动画&#xff0c;由虚幻引擎5渲染 搜维尔科技&#xff1a;通过 Xsens MVN Link 套装测试动作捕捉动画&#xff0c;由虚幻引擎5渲染

FPGA实训报告DAY 1(Verilog HDL)

实习日志与总结 日期&#xff1a;2024 年 7 月 10 日 星期三 姓名&#xff1a;XXX 一、实习日志 上午 9:00 - 9:30 按时到达工位&#xff0c;参加部门早会&#xff0c;了解了今天的实习任务和目标&#xff0c;即初步学习 FPGA 简介和 Verilog 基础语法知识。 9:30 - 10:30…

Flask 静态文件处理

1. 静态文件目录 Flask 默认会在应用的根目录下寻找一个名为 static 的文件夹&#xff0c;并将其作为静态文件的存储目录。你可以通过 static_folder 参数来指定不同的静态文件目录路径。 from flask import Flask app Flask(__name__, static_foldermy_static) 2. 静态文件 …

图扑低代码数字孪生 Web SCADA 智慧钢厂

2024 年 4 月&#xff0c;中国钢铁工业协会发布了《钢铁行业数字化转型评估报告&#xff08;2023年&#xff09;》&#xff08;以下简称《报告》&#xff09;。《报告》指出&#xff0c;绝大部分钢铁企业建立了数字化转型相关管理组织和团队&#xff0c;并加强其规划落实&#…

LDAPWordlistHarvester:基于LDAP数据的字典生成工具

关于LDAPWordlistHarvester LDAPWordlistHarvester是一款功能强大的字典列表生成工具&#xff0c;该工具可以根据LDAP中的详细信息生成字典列表文件&#xff0c;广大研究人员随后可以利用生成的字典文件测试目标域账号的非随机密码安全性。 工具特征 1、支持根据LDAP中的详细信…

CentOS 7 网络配置

如想了解请查看 虚拟机安装CentOS7 第一步&#xff1a;查看虚拟机网络编辑器、查看NAT设置 &#xff08;子网ID&#xff0c;网关IP&#xff09; 第二步&#xff1a;配置VMnet8 IP与DNS 注意事项&#xff1a;子网掩码与默认网关与 第一步 保持一致 第三步&#xff1a;网络配置…

初学者指南:如何搭建和配置 Nginx 服务器

初学者指南&#xff1a;如何搭建和配置 Nginx 服务器 Nginx 是一个高性能的 HTTP 和反向代理服务器&#xff0c;也是一个 IMAP/POP3/SMTP 代理服务器。本文将详细介绍如何在 Linux 上安装、配置和管理 Nginx 服务器。 一、安装 Nginx Nginx 可以安装在多种操作系统上&#x…

Window -- redis 服务注册、Mysql 服务注册

Windows 服务注册 cd 进入 Redis 主目录 cd /d F:\Redis-x64-5.0.14.1注册 Redis 为系统服务&#xff0c;并指定配置文件 redis-server --service-install redis.windows.conf --loglevel verbose开启服务 redis-server --service-start停止服务 redis-server --service-s…

关于HDFS 和HBase

Apache HBase 被设计为在 Hadoop 分布式文件系统 (HDFS) 上运行的一个特殊类型的数据库。大白话&#xff1a; 想象一下&#xff0c;你有一个巨大的图书馆&#xff0c;这个图书馆就像 HDFS&#xff0c;它的架子上堆满了各种各样的书籍&#xff0c;每本书都非常厚&#xff0c;而…

安防监控视频平台LntonCVS视频融合共享平台智慧消防实现远程集中视频监控方案

近年来&#xff0c;电力系统内变电站着火事件频发&#xff0c;这对消防安全管理提出了严峻挑战。我国消防安全基础设施不完善、管理机制不健全、应急处置能力不足及公众消防安全意识淡薄等问题&#xff0c;严重制约了消防安全的提升。因此&#xff0c;加强变电站的消防安全管理…

HashMap源码解析

目录 一:put方法流程 二&#xff1a;get方法 三&#xff1a;扩容机制 一&#xff1a;put方法流程 public V put(K key, V value) {return putVal(hash(key), key, value, false, true); }final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {No…

Qcom平台通过Hexagon IDE 测试程序性能指导

Qcom平台通过Hexagon IDE 测试程序性能指导 1 安装Hexagon IDE工具2 测试工程2.1 打开Hexagon IDE2.2 新建工程2.3 添加测试案例2.3.1 方法一&#xff1a;新建2.3.2 方法二&#xff1a;拷贝 2.4 配置测试环境2.4.1 包含头文件2.4.2 添加程序优化功能(需先bulid一下)2.4.3 添加g…

79. UE5 RPG 创建技能冷却和消耗

在这一篇里面&#xff0c;我们接着优化技能&#xff0c;现在角色添加的主动技能能够同步到ui上面。我们在这一篇文章里面&#xff0c;完善技能的消耗&#xff08;释放技能减少蓝量&#xff09;和冷却机制。 我们可以看到&#xff0c;在技能类默认值这里&#xff0c;可以设置它的…

分类题解清单

目录 简介MySQL题一、聚合函数二、排序和分组三、高级查询和连接四、子查询五、高级字符串函数 / 正则表达式 / 子句 算法题一、双指针二、滑动窗口三、模拟四、贪心五、矩阵六、排序七、链表八、设计九、前缀和十、哈希表十一、字符串十二、二叉树十三、二分查找十四、回溯十五…

LabVIEW红外热波图像缺陷检

开发使用LabVIEW开发的红外热波图像缺陷检测系统。该系统结合红外热像仪、工业相机和高效的数据采集硬件&#xff0c;实现对工件表面缺陷的自动检测和分析。通过LabVIEW的强大功能&#xff0c;系统能够实时采集、处理和显示红外热波图像&#xff0c;有效提高了检测的精度和效率…

Windows 11预览补丁KB5040527影响火绒驱动加载的解决办法

7 月 11 日&#xff0c;微软更新Windows 11 预览版本补丁 KB5040527&#xff0c;补丁安装后会影响火绒驱动加载导致火绒安全软件服务异常&#xff0c;补丁相关信息如下&#xff1a; https://blogs.windows.com/windows-insider/2024/07/11/releasing-windows-11-builds-22621-…

如何在Java中处理空集合和空指针

文章目录 概要示例代码详细解释如下正确处理集合的技巧总结 概要 在Java开发中&#xff0c;我们经常需要处理集合&#xff08;如ArrayList&#xff09;的情况。为了确保程序的稳定性和正确性&#xff0c;我们必须妥善处理空集合和空指针。 示例代码 public class Main {publ…

大语言模型(Large Language Model, LLM)——初步详细了解!!!

LLM 1.1 **基本概念**1.2. **主要特点**1.3. **主要应用**1.4. **著名大语言模型**1.5. **挑战和局限**1.6. **未来发展**2.1. 文献综述与资料收集2.2. 数据分析与预处理2.3. 实验设计与优化2.4. 结果分析与解释2.5. 科研写作与报告6. 知识扩展与创新2.7. 具体工具与平台2.8 示…

装修设计行业全屋定制类小程序源码系统 带完整的安装代码包以及搭建部署教程

系统概述 装修设计行业全屋定制类小程序源码系统是基于现代技术栈开发的&#xff0c;专为装修设计行业量身定制。该系统采用了模块化架构设计&#xff0c;使得开发者能够根据需要灵活选择和组合功能模块&#xff0c;从而快速构建出符合自己业务需求的小程序。 该系统主要面向…

【Qt 常用控件】基础的常用控件(下)

文章目录 1. QDateTimeEdit1.1 日期计算器 2. QDial3. QSlider3.1 通过滑动条来控制窗口大小3.2 给滑动条添加快捷键使用 1. QDateTimeEdit 1.1 日期计算器 2. QDial 3. QSlider 3.1 通过滑动条来控制窗口大小 3.2 给滑动条添加快捷键使用