数据结构 - 4（栈和队列6000字详解）

一：栈

1.1 栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

  • 压栈（push）：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
  • 出栈（pop）：栈的删除操作叫做出栈。出数据在栈顶。

在这里插入图片描述
在这里插入图片描述

栈这种结构在现实生活中也很常见：
在这里插入图片描述
在这里插入图片描述

1.2 栈的使用

方法功能
Stack()构造一个空的栈
E push(E e)将e入栈，并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空

下面是这些方法的使用示例：

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());  // 获取栈中有效元素个数---> 4System.out.println(s.peek());  // 获取栈顶元素---> 4s.pop();  // 4出栈，栈中剩余1  2  3，栈顶元素为3System.out.println(s.pop());  // 3出栈，栈中剩余1 2  栈顶元素为3if(s.empty()){System.out.println("栈空");}else{System.out.println(s.size());}}

1.3栈的模拟实现

在这里插入图片描述
从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

public class MyStack {int[] array;  // 数组用于存储栈元素int size; // 记录栈中元素的个数// 构造方法，创建一个初始容量为3的数组作为栈的存储空间public MyStack(){array = new int[3];}// 入栈操作，将元素 e 加入到栈顶，并返回入栈的元素public int push(int e){ensureCapacity();// 确保栈的容量足够array[size++] = e;// 将元素 e 加入到数组中，更新 size 的值return e;// 返回入栈的元素}// 出栈操作，将栈顶元素移出并返回该元素public int pop(){int e = peek(); // 调用 peek 方法获取栈顶元素，并记录在变量 e 中size--; // 栈中元素个数减少1return e;// 返回出栈的元素}// 返回栈顶元素的值，但不删除栈顶元素public int peek(){if(empty()){ // 如果栈为空，则抛出异常throw new RuntimeException("栈为空，无法获取栈顶元素");}return array[size-1];// 返回栈顶元素的值}// 返回栈中元素的个数public int size(){return size;}// 判断栈是否为空public boolean empty(){return 0 == size;}// 确保栈的容量足够，如果栈已满，则将栈的容量扩大为原来的2倍private void ensureCapacity(){if(size == array.length){array = Arrays.copyOf(array, size*2);}}
}

二：队列

2.1 队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

在这里插入图片描述

2.2 队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。
在这里插入图片描述
下面是队列中常用的方法：

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

注意：

  • Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

下面是这些方法的使用示例：

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);         System.out.println(q.size());// 获取队头元素System.out.println(q.peek()); q.poll();System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

2.3队列的模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构 和 链式结构。所以队列的实现也可以采用这两种方式，但是具体采用哪种实现方式取决于具体的需求和场景。

  1. 顺序结构：使用数组或列表等连续的内存空间来存储队列元素。顺序结构实现队列的优点是简单、易于理解和实现，并且访问元素的时间复杂度为 O(1)。缺点是在插入和删除操作时可能需要进行元素的搬移，这会造成时间复杂度为 O(n)。

  2. 链式结构：使用链表的形式来存储队列元素。链式结构实现队列的优点是插入和删除操作的时间复杂度为 O(1)，无需进行元素的搬移。缺点是需要额外的指针来维护节点之间的连接，且节点的分配和释放可能会引起额外的内存开销和碎片问题。

所以说如果你以访问为主，那么采用顺序结构，如果你以插入和删除为主，那么采用链式结构

在这里插入图片描述

2.3.1顺序结构实现队列

因为我以及在代码中通过注释进行了详细的解答，在此就不过多赘述了。

public class Queue {private int capacity;           // 队列的容量private int[] elements;         // 存储队列元素的数组private int front;              // 队列的头指针private int rear;               // 队列的尾指针private int size;               // 队列的当前大小// 队列的构造方法public Queue(int capacity) {this.capacity = capacity;this.elements = new int[capacity];this.front = 0;this.rear = -1;this.size = 0;}// 入队列---向队尾插入新元素public void offer(int element) {// 检查队列是否已满if (size == capacity) {throw new IllegalStateException("Queue is full");}// 队尾指针移动到下一个位置rear = (rear + 1) % capacity;// 将新元素插入队尾elements[rear] = element;// 队列大小加1size++;}// 出队列---将队头元素删除并返回public int poll() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 获取队头元素int element = elements[front];// 队头指针移动到下一个位置front = (front + 1) % capacity;// 队列大小减1size--;// 返回队头元素return element;}// 获取队头元素---返回队头元素的值，但不删除public int peek() {// 检查队列是否为空if (isEmpty()) {throw new IllegalStateException("Queue is empty");}// 返回队头元素return elements[front];}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}
}

2.3.2链式结构实现队列

public class Queue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;// 双向链表节点的构造方法ListNode(int value){this.value = value;}}ListNode first;  // 队头ListNode last;   // 队尾int size = 0;// 入队列---向双向链表尾部插入新节点public void offer(int e){ListNode newNode = new ListNode(e);if (first == null) {// 如果队列为空，新节点同时成为队头和队尾first = newNode;} else {// 如果队列不为空，将新节点插入到队尾last.next = newNode;newNode.prev = last;}// 更新队尾为新节点last = newNode;// 队列大小加1size++;}// 出队列---将双向链表第一个节点删除public int poll(){// 队列为空，返回nullif (first == null) {return null;} else if (first == last) {// 队列中只有一个元素，将队头和队尾设置为null即可last = null;first = null;} else {// 队列中有多个元素，将第一个节点删除int value = first.value;first = first.next;// 删除节点的引用关系，避免内存泄漏first.prev.next = null;first.prev = null;return value;}// 队列大小减1--size;// 返回删除的值return value;}// 获取队头元素---获取双向链表的第一个节点的值public int peek(){// 如果队列为空，返回nullif (first == null) {return null;}// 返回队头的值return first.value;}// 返回队列的大小public int size() {return size;}// 判断队列是否为空public boolean isEmpty(){return first == null;}
}

2.4 循环队列

2.4.1索引公式

循环队列的视图如下：

在这里插入图片描述

我们该如何去实现一个循环队列呢？答案是通过 %取模

举个例子：

int a = b % 7；

在这个例子中，我们不管b取何值，a的取值返回是不是始终在0到6之间，所以我们通过这个性质就可以很好的把队列的首和尾建立关联，即尾向后走一步就到了头，因此我们就可以很好的去实现一个循环队列了

在循环队列中，(index + offset) % array.length 和 (index + array.length - offset) % array.length 是我们常用的索引计算方式。其中：

  • index 是当前元素的索引。
  • offset 是偏移量，它决定了要添加/访问的元素在当前索引的基础上偏移了多少个位置。
  • array.length 是数组的长度，它表示整个循环队列的大小。

下面我们对这两个公式进行解释：

  1. (index + offset) % array.length：
    • 当我们需要向循环队列的下一个位置插入元素时，我们使用这种索引计算方式。
    • 假设队列在索引5处结束，我们需要向后移动1个位置，即在索引7处插入元素。使用 (5 + 1) % 8，得到的值是6，即有效的索引。

在这里插入图片描述

  1. (index + array.length - offset) % array.length：
    • 当我们需要从循环队列的上一个位置移除元素时，我们使用这种索引计算方式。
    • 假设队列在索引2处结束，我们需要向前移动1个位置，即从索引1处移除元素。使用 (2 + 8 - 1) % 8，得到的值是1，即有效的索引。

在这里插入图片描述

这两种计算方式都确保了索引在循环队列中的有效范围内，因为它们会通过取模运算将索引限制在数组长度范围内。这样，我们可以在循环队列中正确地插入和移除元素。

2.4.2 队列区分空和满

当我们使用一个固定大小的数组作为队列的底层数据结构。在循环队列中，我们使用两个指针，一个指向队列的头部，即出队列的位置，另一个指向队列的尾部，即入队列的位置。

当队列为空时，这两个指针指向同一个位置，即头部与尾部指针相等。而当队列满时，尾部指针的下一个位置就是头部指针所在的位置。

那么我们该怎么区分队列是空还是满呢？

为了区分队列是空还是满，我们可以采用三种常用的方法：

  1. 使用 size 属性记录:

通过添加一个 size 属性来记录队列中的元素数量，可以方便地判断队列是空还是满。当队列为空时，size 的值为 0，当队列满时，size 的值等于队列的容量。

  1. 保留一个位置:

在循环队列的实现中，可以将一个位置始终空置不用，用于区分队列是空还是满。例如，当队列为空时，头部指针和尾部指针都指向同一个位置；当队列满时，尾部指针的下一个位置就是头部指针所在的位置。通过查看这个空置位置是否为空，可以判断队列是空还是满。

  1. 使用标记:

可以在循环队列中使用一个额外的标记来区分队列是空还是满。这个标记可以是一个布尔值或者一个特殊的值，用于表示队列的状态。例如，当队列为空时，可以将标记设置为 true；当队列满时，可以将标记设置为 false。通过判断标记的值，可以确定队列的状态。

这些方法都可以用于区分队列是空还是满，具体选择哪种方法取决于个人偏好和实际需求。

2.5 Deque双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

在这里插入图片描述
Deque是一个接口，使用时必须创建LinkedList的对象。
在这里插入图片描述
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

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

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

相关文章

JVM三色标记

JVM三色标记

三色标记 什么是三色标记法 三色标记法&#xff0c;也被称为Tri-color Marking Algorithm&#xff0c;是一种用于追踪对象存活状态的垃圾回收算法。它基于William D. Hana和Mark S. McCulleghan在1976年提出的两色标记法的基础上进行了改进。 与两色标记法只能将对象标记为“…
阅读更多...
[GSEP202306 一级] C++ 时间规划

[GSEP202306 一级] C++ 时间规划

题目描述 小明在为自己规划学习时间。现在他想知道两个时刻之间有多少分钟&#xff0c;你通过编程帮他做到吗? 输入格式 输入4行&#xff0c;第一行为开始时刻的小时&#xff0c;第二行为开始时刻的分钟&#xff0c;第三行为结束时刻的小时&#xff0c;第四行为结束时刻的分…
阅读更多...
笔记本Win10系统一键重装操作方法

笔记本Win10系统一键重装操作方法

笔记本电脑已经成为大家日常生活和工作中必不可少的工具之一&#xff0c;如果笔记本电脑系统出现问题了&#xff0c;那么就会影响到大家的正常操作。这时候就可以考虑给笔记本电脑重装系统了。接下来小编给大家介绍关于一键重装Win10笔记本电脑系统的详细步骤方法。 推荐下载 系…
阅读更多...
【Linux学习笔记】代码编译工具gcc/g++

【Linux学习笔记】代码编译工具gcc/g++

1. 程序的翻译1.1. 预处理1.2. 编译1.3. 汇编1.4. 链接 2. 动态链接和静态链接2.1. 动态链接2.2. 静态链接2.3. 动态链接和静态链接的区别2.4. 动态链接和静态链接的验证 3. make/makefile3.1. 依赖方法和依赖关系3.2. 写一个makefile文件3.3. PHONY的意义3.4. makefile的推导规…
阅读更多...
无人机电力巡检：国网安徽实际案例解析

无人机电力巡检：国网安徽实际案例解析

在科技快速发展的今天&#xff0c;传统行业正在经历前所未有的转型。电力巡检&#xff0c;这一看似传统且乏味的任务&#xff0c;却因为无人机技术的介入而焕发新生。今天&#xff0c;让我们深入了解一个具体的案例&#xff0c;探索无人机如何革新电力巡检。 案例背景&#xff…
阅读更多...
【Machine Learning】03-Unsupervised learning

【Machine Learning】03-Unsupervised learning

03-Unsupervised learning 3. Unsupervised Learning3.1 无监督学习&#xff08;Unsupervised Learning&#xff09;3.1.1 聚类&#xff08;Clustering&#xff09;3.1.2 K-均值聚类算法&#xff08;K-means Clustering&#xff09;3.1.3 高斯分布&#xff08;Gaussian distrib…
阅读更多...
深度学习入门（一）之感知机

深度学习入门（一）之感知机

文章目录 前言什么是感知机简单的逻辑电路与门与非门和或门 感知机的实现简单的实现导入权重和偏置 感知机的局限性异或门线性和非线性 多层感知机已有门电路的组合异或门的实现 代码合集 前言 感知机是由美国学者1957年提出来&#xff0c;作为神经网络的起源算法。因此学习感…
阅读更多...
新增Node.js运行环境、新增系统缓存清理功能，1Panel开源面板v1.7.0发布

新增Node.js运行环境、新增系统缓存清理功能，1Panel开源面板v1.7.0发布

2023年10月16日&#xff0c;现代化、开源的Linux服务器运维管理面板1Panel正式发布v1.7.0版本。 在这个版本中&#xff0c;1Panel新增Node.js运行环境&#xff1b;新增系统缓存清理功能&#xff1b;应用安装时支持选择远程数据库。此外&#xff0c;我们进行了40多项功能更新和…
阅读更多...
阿里云云服务器实例使用教学

阿里云云服务器实例使用教学

目录 云服务器免费试用 详细步骤 Xshell 远程连接 云服务器免费试用 阿里云云服务器网址&#xff1a;阿里云免费试用 - 阿里云 详细步骤 访问阿里云免费试用。单击页面右上方的登录/注册按钮&#xff0c;并根据页面提示完成账号登录&#xff08;已有阿里云账号&#xff09;…
阅读更多...
配置hpa后，target显示＜unknown＞/50%

配置hpa后，target显示＜unknown＞/50%

背景&#xff1a; 有两个服务&#xff0c;server 负责主要后端请求&#xff0c;bill 负责计量计费请求。服务都是使用 helm 部署。测试提了一个缺陷&#xff0c;说全部服务没有配置hpa。 解决一 按照之前的代码结构添加了hpa后&#xff0c;发现&#xff1a; ➜ kubectl get…
阅读更多...
软件外包开发团队人员构成

软件外包开发团队人员构成

软件外包开发团队的人员构成可以因项目的规模、类型和要求而有所不同。通常&#xff0c;一个典型的软件外包开发团队可能包括以下关键角色&#xff0c;每个角色都有要完成的工作。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 项目经…
阅读更多...
playwright: local variable ‘page‘ referenced before assignment

playwright: local variable ‘page‘ referenced before assignment

安装好playwright后&#xff0c;运行相关程序出现此错误&#xff0c;按照下述链接中的方法安装相关组件和浏览器驱动后&#xff0c;问题得以解决。 https://www.cnblogs.com/fengyangsheng/p/17531254.html安装playwright pip install -i https://mirrors.aliyun.com/pypi/si…
阅读更多...
区块链运行原理

区块链运行原理

文章目录 前言区块链的结构区块链的交易过程区块链的共识机制区块链交易存在的问题特性总结 前言 上文《认识区块链》中可以知道区块链是一个通过各种加密算法、共识机制以及其他技术可以实现一个点对点的电子现金系统&#xff0c;从而达到去第三方的效果&#xff08;通常称之…
阅读更多...
【Wifi】Wifi架构介绍

【Wifi】Wifi架构介绍

Wifi架构介绍 本文基于Android介绍其Wifi架构。Wifi是许多操作系统提供的重要功能之一&#xff0c;特别是越来越多的车载系统wifi是其必备功能。为啥wifi是必备功能&#xff1f; 一方面是传统的上网&#xff08;现在有些车载使用DCM模块管理网络&#xff09;&#xff0c;另一方…
阅读更多...
没有前端如何测试后端跨域问题

没有前端如何测试后端跨域问题

一、问题 前段时间对项目中的跨域做了相关的处理&#xff0c;网上有很多跨域的解决方案。前端解决&#xff0c;后端解决&#xff0c;nginx代理解决。我采用的是在后端中使用Cors来解决跨域的问题。但是前端项目还没有搭建起来&#xff0c;并不知道Cors的解决方案是否会生效&am…
阅读更多...
Apollo(阿波罗)分布式配置中心

Apollo(阿波罗)分布式配置中心

&#x1f353; 简介&#xff1a;java系列技术分享(&#x1f449;持续更新中…&#x1f525;) &#x1f353; 初衷:一起学习、一起进步、坚持不懈 &#x1f353; 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正&#x1f64f; &#x1f353; 希望这篇文章对你有所帮助,欢…
阅读更多...
CSS Vue/RN 背景使用opacity，文字在背景上显示

CSS Vue/RN 背景使用opacity，文字在背景上显示

Vue <div class"training_project_tip"> <div class"tip">展示的文字</div> </div> .training_project_tip { font-size: 12px; font-weight: 400; text-align: left; color: #ffffff; margin-top: 8px; position: relative; dis…
阅读更多...
如何将前后端分离项目部署到本地的Docker Desktop容器运行并且访问

如何将前后端分离项目部署到本地的Docker Desktop容器运行并且访问

文章目录 前言 完成了客户的一个前后端分离项目&#xff0c;要求部署到客户电脑上去展示&#xff0c;那肯定不能直接把代码弄上去跑呀~~~&#xff0c;于是我就想把他们都打包部署到本地的docker容器里面&#xff0c;方便运行和访问&#xff0c;so&#xff0c;以下内容就详细介…
阅读更多...
LeetCode09——回文数

LeetCode09——回文数

LeetCode09 自己写的解,转化为字符串再反转&#xff0c;比较笨。 import java.util.Scanner; public class Result01 {public static void main(String[] args) {System.out.println("请输入整数&#xff0c;我来帮您判断是否是回文数。");Scanner scanner new Sc…
阅读更多...
Linux之解除ssh远程登录限制

Linux之解除ssh远程登录限制

背景&#xff1a;复制了一个虚拟机&#xff0c;将root密码重置为123456后&#xff0c;使用xshell通过ssh登录竟然失败&#xff0c;检查了很多次&#xff0c;确定root账号密码正确&#xff0c;以下是记录的排查过程。 1、查看ssh登录日志 Ubuntu&#xff1a;/var/log/auth.log…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发