数据结构秘籍(一)线性数据结构

1.数组

数组(Array)是一种很常见的数据结构。它由相同类型的元素(element)组成,并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引(index)计算出该元素对应的存储地址。

数组的特地那是:提供随机访问并且容量有限。

假如数组的长度为 n。
访问:O(1)//访问特定位置的元素
插入:O(n )//最坏的情况发生在插入发生在数组的首部并需要移动所有元素时
删除:O(n)//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

2.链表

2.1 链表简介

链表(LinkedList)虽然是一种线性表,但是并不会按线性的顺序存储数据,使用的不是连续的内存空间来存储数据。

链表的插入和删除操作的复杂度为O(1),只需要知道目标位置元素的上一个元素即可。但是,在查找一个节点或者访问特定位置的节点的时候复杂度为O(n).

使用链表结构可以克服数组需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间,相比于数组会占用更多的空间,因为链表中每个节点存放的还有指向其他节点的指针。除此之外,链表不具有数组随机读取的优点

2.2 链表分类

常见链表分类:

1.单链表

2.双向链表

3.循环链表

4.双向循环链表

假如链表中有n个元素。
访问:O(n)//访问特定位置的元素
插入删除:O(1)//必须要要知道插入元素的位置
2.2.1 单链表

单链表 单向链表只有一个方向,点解只有一个后继指针next指向后面的节点。因此,链表这种数据结构通常在物理内存上不是连续的。我们习惯性地把第一个结点叫头结点,链表通常有一个不保存任何值的head节点(头结点),通过头结点我们可以遍历整个链表。为节点通常指向null。

2.2.2 循环链表

循环链表其实是一种特殊的单链表,和单链表不同的是循环链表的尾结点不是指向null。而是指向链表的头结点。

 

2.2.3 双向链表

双向链表 包含两个指针,一个prev指向前一个结点,一个next指向后一个结点。

 2.2.4 双向循环链表

双向循环链表 最后一个结点的next指向head,而head的prev指向最后一个结点,构成一个环。

 2.3 应用场景

  • 如果需要支持随机访问的话,链表没办法做到。
  • 如果需要存储的数据元素的个数不确定,并且需要经常添加和删除数据的话,使用链表比较合适。
  • 如果需要存储的数据元素的个数确定,并且不需要经常添加和删除数据的话,使用数组比较合适。

 2.4 数组vs链表

  • 数组支持随机访问,而链表不支持。
  • 数组使用的是连续内存空间对 CPU 的缓存机制友好,链表则相反。
  • 数组的大小固定,而链表则天然支持动态扩容。如果声明的数组过小,需要另外申请一个更大的内存空间存放数组元素,然后将原数组拷贝进去,这个操作是比较耗时的!

3.栈

3.1 栈简介 

 栈(Stack)只允许在有序的线性数据集合的一端(称为栈顶top)进行加入数据(push)和移除数据(pop)。因而按照 后进先出(LIFO, Last In First Out) 的原理运作。在栈中,push和pop的操作都发生在栈顶。

栈常用一维数组或链表来实现,用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。

假设堆栈中有n个元素。
访问:O(n)//最坏情况
插入删除:O(1)//顶端插入和删除元素

3.2 栈的常见应用场景

当我们要处理的数据只涉及在一端插入和删除数据,并且满足 后进先出(LIFO, Last In First Out) 的特性时,我们就可以使用栈这个数据结构。


3.2.1. 实现浏览器的回退和前进功能


       我们只需要使用两个栈(Stack1 和 Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面,我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看 2 这个页面的时候,你点击回退按钮,我们依次把 4,3 这两个页面从 Stack1 弹出,然后压入 Stack2 中。假如你又想回到页面 3,你点击前进按钮,我们将 3 页面从 Stack2 弹出,然后压入到 Stack1 中。示例图如下:

3.3.2 检查符号是否成对出现

 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断该字符串是否有效。
有效字符串需满足:
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
比如 "()"、"()[]{}"、"{[]}" 都是有效字符串,而 "(]"、"([)]" 则不是。

 这个问题实际是 Leetcode 的一道题目,我们可以利用栈 Stack 来解决这个问题。

  • 首先我们将括号间的对应规则存放在 Map 中,这一点应该毋容置疑;
  • 创建一个栈。遍历字符串,如果字符是左括号就直接加入stack中,否则将stack 的栈顶元素与这个括号做比较,如果不相等就直接返回 false。遍历结束,如果stack为空,返回 true
public boolean isValid(String s){// 括号之间的对应规则HashMap<Character, Character> mappings = new HashMap<Character, Character>();mappings.put(')', '(');mappings.put('}', '{');mappings.put(']', '[');Stack<Character> stack = new Stack<Character>();char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {if (mappings.containsKey(chars[i])) {char topElement = stack.empty() ? '#' : stack.pop();if (topElement != mappings.get(chars[i])) {return false;}} else {stack.push(chars[i]);}}return stack.isEmpty();
}
3.2.3 反转字符串

 将字符串中的每个字符先入栈再出栈就可以了。

3.2.4 维护函数调用

最后一个被调用的函数必须先完成执行,符合栈的 后进先出(LIFO, Last In First Out) 特性。
例如递归函数调用可以通过栈来实现,每次递归调用都会将参数和返回地址压栈。

3.2.5深度优先遍历 

在深度优先搜索过程中,栈被用来保存搜索路径,以便回溯到上一层。

 3.3 栈的实现

栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。
下面我们使用数组来实现一个栈,并且这个栈具有push()、pop()(返回栈顶元素并出栈)、peek() (返回栈顶元素不出栈)、isEmpty()、size()这些基本的方法。

public class MyStack {private int[] storage;//存放栈中元素的数组private int capacity;//栈的容量private int count;//栈中元素数量private static final int GROW_FACTOR = 2;//不带初始容量的构造方法。默认容量为8public MyStack() {this.capacity = 8;this.storage=new int[8];this.count = 0;}//带初始容量的构造方法public MyStack(int initialCapacity) {if (initialCapacity < 1)throw new IllegalArgumentException("Capacity too small.");this.capacity = initialCapacity;this.storage = new int[initialCapacity];this.count = 0;}//入栈public void push(int value) {if (count == capacity) {ensureCapacity();}storage[count++] = value;}//确保容量大小private void ensureCapacity() {int newCapacity = capacity * GROW_FACTOR;storage = Arrays.copyOf(storage, newCapacity);capacity = newCapacity;}//返回栈顶元素并出栈private int pop() {if (count == 0)throw new IllegalArgumentException("Stack is empty.");count--;return storage[count];}//返回栈顶元素不出栈private int peek() {if (count == 0){throw new IllegalArgumentException("Stack is empty.");}else {return storage[count-1];}}//判断栈是否为空private boolean isEmpty() {return count == 0;}//返回栈中元素的个数private int size() {return count;}}

验证:

MyStack myStack = new MyStack(3);
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.push(7);
myStack.push(8);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//报错:java.lang.IllegalArgumentException: Stack is empty.

4 队列

4.1 队列简介

队列是先进先出 (FIFO,First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现,用数组实现的队列叫作 顺序队列 ,用链表实现的队列叫作 链式队列 。队列只允许在后端(rear)进行插入操作也就是入队 enqueue,在前端(front)进行删除操作也就是出队 dequeue
队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

假设队列中有n个元素。
访问:O(n)//最坏情况
插入删除:O(1)//后端插入前端删除元素

 4.2 队列分类

4.2.1 单队列

单队列就是常见的队列, 每次添加元素时,都是添加到队尾。单队列又分为 顺序队列(数组实现)链式队列(链表实现)

顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。

假设下图是一个顺序队列,我们将前两个元素 1,2 出队,并入队两个元素 7,8。当进行入队、出队操作的时候,front 和 rear 都会持续往后移动,当 rear 移动到最后的时候,我们无法再往队列中添加数据,即使数组中还有空余空间,这种现象就是 ”假溢出“ 。除了假溢出问题之外,如下图所示,当添加元素 8 的时候,rear 指针移动到数组之外(越界)。

为了避免当只有一个元素的时候,队头和队尾重合使处理变得麻烦,所以引入两个指针,front 指针指向对头元素,rear 指针指向队列最后一个元素的下一个位置,这样当 front 等于 rear 时,此队列不是还剩一个元素,而是空队列。——From 《大话数据结构》

4.2.2 循环队列

循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是:从头开始,这样也就会形成头尾相接的循环,这也就是循环队列名字的由来。
还是用上面的图,我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候, rear 向后移动。

顺序队列中,我们说 front==rear 的时候队列为空,循环队列中则不一样,也可能为满,如上图所示。解决办法有两种:

  1. 可以设置一个标志变量 flag,当 front==rear 并且 flag=0 的时候队列为空,当front==rear 并且 flag=1 的时候队列为满。
  2. 队列为空的时候就是 front==rear ,队列满的时候,我们保证数组还有一个空闲的位置,rear 就指向这个空闲位置,如下图所示,那么现在判断队列是否为满的条件就是:(rear+1) % QueueSize==front
4.2.3 双端队列

双端队列 (Deque) 是一种在队列的两端都可以进行插入和删除操作的队列,相比单队列来说更加灵活。

一般来说,我们可以对双端队列进行 addFirstaddLastremoveFirstremoveLast 操作。

4.2.4 优先队列

优先队列 (Priority Queue) 从底层结构上来讲并非线性的数据结构,它一般是由堆来实现的。

  1. 在每个元素入队时,优先队列会将新元素其插入堆中并调整堆。
  2. 在队头出队时,优先队列会返回堆顶元素并调整堆。

关于堆的具体实现可以看堆这一节。

总而言之,不论我们进行什么操作,优先队列都能按照某种排序方式进行一系列堆的相关操作,从而保证整个集合的有序性

虽然优先队列的底层并非严格的线性结构,但是在我们使用的过程中,我们是感知不到的,从使用者的眼中优先队列可以被认为是一种线性的数据结构:一种会自动排序的线性队列。

4.3 队列的常见应用场景

当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。

  • 阻塞队列: 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候,出队操作阻塞,当队列满的时候,入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。
  • 线程池中的请求/任务队列: 线程池中没有空闲线程时,新的任务请求线程资源时,线程池该如何处理呢?答案是将这些请求放在队列中,当有空闲线程的时候,会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列,除非系统资源耗尽,比如:FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了,当队列满的话后面再有任务/请求就会拒绝,在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。
  • 栈:双端队列天生便可以实现栈的全部功能(push、pop 和 peek),并且在 Deque 接口中已经实现了相关方法。Stack 类已经和 Vector 一样被遗弃,现在在 Java 中普遍使用双端队列(Deque)来实现栈。
  • 广度优先搜索(BFS),在图的广度优先搜索过程中,队列被用于存储待访问的节点,保证按照层次顺序遍历图的节点。
  •  Linux 内核进程队列(按优先级排队)
  • 现实生活中的派对,播放器上的播放列表;
  • 消息队列
  • 等等……

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/24726.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WiFi IEEE 802.11协议精读:IEEE 802.11-2007,6,MAC service definition MAC服务定义

继续精读IEEE 802.11-2007 6&#xff0c;MAC service definition MAC服务定义 6.1 MAC服务概述 6.1.1 数据服务 此服务为对等逻辑链路控制&#xff08;LLC&#xff09;实体提供交换MAC服务数据单元&#xff08;MSDU&#xff09;的能力。为支持此服务&#xff0c;本地媒体访…

QT基于mmap文件映射机制实现的内存池方法总结

在现代计算机系统中&#xff0c;高效的内存管理对于程序性能有着至关重要的影响。尤其是在处理大量数据或频繁分配和释放小块内存的应用场景下&#xff0c;传统的内存分配方式&#xff08;如malloc和free&#xff09;可能会导致显著的性能开销和内存碎片化问题。为了克服这些问…

车载DoIP诊断框架 --- 连接 DoIP ECU/车辆的故障排除

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活,除了生存温饱问题之外,没有什么过多的欲望,表面看起来很高冷,内心热情,如果你身…

0—QT ui界面一览

2025.2.26&#xff0c;感谢gpt4 1.控件盒子 1. Layouts&#xff08;布局&#xff09; 布局控件用于组织界面上的控件&#xff0c;确保它们的位置和排列方式合理。 Vertical Layout&#xff08;垂直布局&#xff09; &#xff1a;将控件按垂直方向排列。 建议&#xff1a;适…

普中单片机-51TFT-LCD显示屏(1.8寸 STM32)

普中官方论坛&#xff1a; http://www.prechin.cn/gongsixinwen/208.html 普中科技-各型号开发板资料链接&#xff1a;https://www.bilibili.com/read/cv23681775/?spm_id_from333.999.0.0 27-TFTLCD显示实验_哔哩哔哩_bilibili 2.程序烧录 2.1设置彩屏驱动 3.实验效果

嵌入式开发工程师笔试面试指南-Linux系统移植

1 Linux内核启动流程 引导加载阶段 计算机通电后&#xff0c;首先由 BIOS 或 UEFI 进行初始化&#xff0c;完成硬件自检等操作。 找到可启动设备&#xff0c;读取其第一个扇区的 MBR&#xff0c;MBR 中的引导加载程序&#xff08;如 GRUB&#xff09;被加载到内存并运行。 内…

图扑数字孪生:解锁压缩空气储能管控新高度

​在能源转型的关键时期&#xff0c;压缩空气储能凭借其独特优势&#xff0c;成为解决可再生能源间歇性问题、保障可靠能源供应的重要技术。图扑软件&#xff08;Hightopo&#xff09;充分发挥其在 Web 2D&3D 可视化领域的技术专长&#xff0c;打造出先进的数字孪生压缩空气…

Redis 高可用性:如何让你的缓存一直在线,稳定运行?

&#x1f3af; 引言&#xff1a;Redis的高可用性为啥这么重要&#xff1f; 在现代高可用系统中&#xff0c;Redis 是一款不可或缺的分布式缓存与数据库系统。无论是提升访问速度&#xff0c;还是实现数据的高效持久化&#xff0c;Redis 都能轻松搞定。可是&#xff0c;当你把 …

AI 编码 2.0 分析、思考与探索实践:从 Cursor Composer 到 AutoDev Sketch

在周末的公司【AI4SE 效能革命与实践&#xff1a;软件研发的未来已来】直播里&#xff0c;我分享了《AI编码工具 2.0 从 Cursor 到 AutoDev Composer》主题演讲&#xff0c;分享了 AI 编码工具 2.0 的核心、我们的思考、以及我们的 AI 编码工具 2.0 探索实践。 在这篇文章中&am…

Qt Creator + CMake 构建教程

此教程基于: Qt 6.7.4Qt Creator 15.0.1CMake 3.26.4 Qt 6 以下的版本使用 CMake 构建可能会存在一些问题. 目录 新建窗体工程更新翻译添加资源软件部署(Deploy) 此教程描述了如何一步步在 Qt Creator 中使用 CMake 构建应用程序工程. 涉及 新建窗体工程, 更新翻译, 添加资源, …

锂电池保护板测试仪:电池安全的守护者与创新驱动力

在新能源产业蓬勃发展的今天&#xff0c;锂电池以其高能量密度、长循环寿命和环保特性&#xff0c;成为电动汽车、无人机、便携式电子设备等领域不可或缺的能量来源。然而&#xff0c;锂电池的安全性和稳定性一直是行业关注的焦点。为了确保锂电池在各种应用场景下的可靠运行&a…

岳阳市美术馆预约平台(小程序论文源码调试讲解)

第4章 系统设计 一个成功设计的系统在内容上必定是丰富的&#xff0c;在系统外观或系统功能上必定是对用户友好的。所以为了提升系统的价值&#xff0c;吸引更多的访问者访问系统&#xff0c;以及让来访用户可以花费更多时间停留在系统上&#xff0c;则表明该系统设计得比较专…

【Java】I/O 流篇 —— 转换流与序列化流

目录 转换流原理InputStreamReader 转换输入流构造方法代码示例 OutputStreamWriter 转换输出流构造方法代码示例 练习 序列化流序列化流反序列化流**serialVersionUID**基本概念作用使用方式transient 关键字注意事项 转换流 原理 转换流属于字符流&#xff0c;是字符流和字节…

Mac 版 本地部署deepseek ➕ RAGflow 知识库搭建流程分享(附问题解决方法)

安装&#xff1a; 1、首先按照此视频的流程一步一步进行安装&#xff1a;(macos版&#xff09;ragflowdeepseek 私域知识库搭建流程分享_哔哩哔哩_bilibili 2、RAGflow 官网文档指南&#xff1a;https://ragflow.io 3、RAGflow 下载地址&#xff1a;https://github.com/infi…

计算机三级网络技术备考

#subtotal 1Mbps1024kb128KB12.8M/s #1024B1KB 1024KB1MB 1024MB1GB #路由器的5G信号和平常的波长不同&#xff08;5G的穿墙性能差&#xff09; #局域网LAN&#xff08;一公里内——构成集线机、交换机、同轴电缆&#xff09; #城域网MAN&#xff08;几公里到几十公里——光…

IDEA 2024.1 最新永久可用(亲测有效)

今年idea发布了2024.1版本&#xff0c;这个版本带来了一系列令人兴奋的新功能和改进。最引人注目的是集成了更先进的 AI 助手&#xff0c;它现在能够提供更复杂的代码辅助功能&#xff0c;如代码自动补全、智能代码审查等&#xff0c;极大地提升了开发效率。此外&#xff0c;用…

30 分钟从零开始入门 CSS

前言 最近也是在复习&#xff0c;把之前没写的博客补起来&#xff0c;之前给大家介绍了 html&#xff0c;现在是 CSS 咯。 30分钟从零开始入门拿下 HTML_html教程-CSDN博客 一、CSS简介&#xff1a;给网页“化妆”的神器 CSS&#xff08;层叠样式表&#xff09;就像“化妆“&a…

Game Maker 0.11更新:构建社交竞速游戏并增强玩家互动

在这三部分系列中&#xff0c;我们将介绍如何实现Game Maker 0.11中一些最激动人心的新功能。 欢迎来到我们系列文章的第一篇&#xff0c;重点介绍了The Sandbox Game Maker 0.11更新中的新特性。 The Sandbox Game Maker 0.11是一个多功能工具&#xff0c;帮助创作者通过游戏…

软件供应链安全工具链研究系列——RASP自适应威胁免疫平台(上篇)

1.1 基本能力 RASP是一种安全防护技术&#xff0c;运行在程序执行期间&#xff0c;使程序能够自我监控和识别有害的输入和行为。也就是说一个程序如果注入或者引入了RASP技术&#xff0c;那么RASP就和这个程序融为一体&#xff0c;使应用程序具备了自我防护的能力&#xff0c;…

2024信息技术、信息安全、网络安全、数据安全等国家标准合集共125份。

2024信息技术、信息安全、网络安全、数据安全等国家标准合集&#xff0c;共125份。 一、2024信息技术标准&#xff08;54份&#xff09; GB_T 17966-2024 信息技术 微处理器系统 浮点运算.pdf GB_T 17969.8-2024 信息技术 对象标识符登记机构操作规程 第8部分&#xff1a;通用…