不良人系列-复兴数据结构(栈和队列)

 个人主页:爱编程的小新☆ 

不良人经典语录:“相呴相济 玉汝于成 勿念 心安”

目录

一. 栈(stack)

1. 栈的概念

2. 栈的常见方法

3.栈的模拟实现

 ​编辑

二. 队列

1. 队列的概念

2. 队列的使用

 2.1 队列的常见方法

2.2 队列的模拟实现

 2.3 队列的分类

(1) 普通队列

(2) 循环队列 

 (3) 双端队列

 三. 栈和队列的优缺点

1. 栈的优缺点

 2. 队列的优缺点


一. 栈(stack)

栈是一种重要的数据结构,接下来我们来看看什么是栈

1. 栈的概念

栈是一种只能在一端进行插入和删除操作的特殊线性表,进行数据操作的一端称作栈顶,那么在另一端则称为栈底,它采用后进先出的原则存储数据,即最后插入的数据最先被取出。

栈的基本操作:

  • 入栈/压栈/进栈(push):将新的元素插入到栈顶
  • 出栈(pop):删除栈顶元素并返回其的值
  • 查看栈顶元素(peek):返回栈顶元素但是不删除它
  • 判断栈是否为空:(isEmpty):若栈为空返回true,否则返回false
  • 获取栈的大小(size):返回栈中元素的个数

 栈在生活中的例子:

比如我们的羽毛球桶,后放进的球会先被取出(统一往球头的方向出); 

2. 栈的常见方法

方法功能
Stack()

构造一个空的栈

E push(E  e)将e放入栈,并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空
public static void main(String[] args) {Stack<Integer> stack=new Stack<>();//将元素放入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);System.out.println(stack);//1,2,3,4,5System.out.println(stack.size());//栈中有效元素个数:5System.out.println(stack.peek());//栈顶元素:5stack.pop();//5出栈System.out.println(stack.isEmpty());//判断栈是否为空:false}

3.栈的模拟实现

从下图可以看见,Stack其实是继承了Vector,Vector和ArrayList类似都是基于数组实现的容器并且是动态的顺序表,但是不同的是:Vector是线程安全的数据结构

 

 线程安全和不安全的概念:

在多线程编程中,线程安全和线程不安全是两个重要的概念(这里了解一下即可)

  • 线程安全:指的是一段代码或者一个数据结构在多线程环境中被多个线程同时访问或者操作时,还是能够正确的运行,不会出现数据不一致、错误结果、程序崩溃等问题
  • 线程不安全:指的是一段代码或者一个数据结构在多线程环境中被多个线程同时访问或者操作时,可能出现数据竞争、数据不一致、错误结果、程序崩溃等问题,导致程序的行为不可预测。

 Stack的模拟实现:

public class Mystacks {public int []elem;//使用数组模拟实现栈public int usedsize;//有效元素的个数public Mystacks() {this.elem=new int[10];//默认栈的初始空间为10}public int size(){//获取栈中有效元素的个数return usedsize;}public void push(int value){//入栈//在入栈前我们需要判断一下栈是否满了,如果满了则需要进行扩容if(isFull()){//扩容this.elem= Arrays.copyOf(elem,elem.length*2);}elem[usedsize++]=value;}//该方法不对用户开放,设置为private权限即可private boolean isFull(){return usedsize==elem.length;}public int pop(){//删除栈顶元素,并返回//判断栈是否为空,为空则返回-1if(isEmpty()){return -1;}int val=elem[usedsize];usedsize--;return val;}public boolean isEmpty(){return usedsize==0;}public int peek(){//获取栈顶元素if(isEmpty()){throw new RuntimeException("栈为空,无法获取栈顶元素");}return elem[usedsize-1];}
}

 那么其实不止可以使用数组来实现栈,也可以使用链表来实现栈:

链式栈:使用链表来存储数据栈数据元素,每个节点包含数据域和指向下一个节点的指针域。其优点是可灵活扩展不存在栈溢出的问题,缺点是需要而外的指针空间,实现相对复杂

二. 队列

1. 队列的概念

队列也是一种特殊的线性表,它允许在表的一端进行插入操作,而在另一端进行删除操作,允许插入的一端称为队尾,允许删除的一端称为队头,元素按照先进先出的原则存储数据

 队列的基本操作:

  • 入队(offer):将元素添加到队尾
  • 出队(poll):从队头删除元素并返回值
  • 查看队头元素(peek):返回队头元素的值,但不改变队列的状态
  • 判断队列是否为空(isEmpty):若队列为空返回true,否则返回false
  • 获取队列大小(size):返回队列中元素的个数

 队列在生活中的例子:

就像一群小朋友在排队玩滑滑梯,先排队的人先玩滑滑梯,后排队的人后玩,遵循了我们队列的原则:先进先出,后进后出

2. 队列的使用

在Java中,Queue是一个接口,底层是通过链表来实现的,所以在实例化的时候必须实例化LinkedList的对象,因为LinkedList实现了Queue接口

 2.1 队列的常见方法

方法功能
boolean offer(E e)入队列
E poll ()出队列
peek()获取队头元素
int size()获取队列中有效元素的个数
boolean isEmpty()检测队列是否为空
 public static void main(String[] args) {Queue<Integer> queue=new LinkedList<>();//入队列queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);System.out.println(queue);//1,2,3,4,5System.out.println(queue.size());//5System.out.println(queue.peek());//5queue.poll();//出队列System.out.println(queue);//2,3,4,5System.out.println("判断队列是否为空:"+queue.isEmpty());}

2.2 队列的模拟实现

在模拟实现队列之前我们来思考一下,是采用单向链表来实现队列好还是双向链表来实现队列好?

实际上双向链表才是最优的选择:

使用单向链表:在插入新元素的时间复杂度为O(n),因为我们需要遍历链表来找到最后一个元素的位置,此时的效率是没有双向链表好的

使用双向链表:在插入新元素和删除元素的时间复杂度都为O(1),可以直接通过对头指针和队尾指针进行入队和出队的操作,效率较高

public class Myqueue {static class ListNode{//定义一个内部类来充当我们的节点public int value;public ListNode next;//存放下一个节点的地址public ListNode prev;//存放前一个节点的地址public ListNode(int value) {this.value = value;}}public ListNode head=null;public ListNode last=null;public int usedsize=0;public void offer(int val){//创建新的节点ListNode node=new ListNode(val);//判断队列是否为空,如果为空将新节点的地址赋值给头节点的地址//如果不为空,将新节点添加到队尾if(isEmpty()){head=node;//头节点是该节点last=node;//尾节点也是该节点}else{last.next=node;//将node的地址赋值给当前尾节点的下一个节点地址node.prev=last;//将当前尾节点的地址赋值给node节点的前一个节点地址last=node;//将尾节点指向新节点}usedsize++;//有效元素个数++}public boolean isEmpty(){//判断队列为不为空return usedsize==0;}public int poll(){//出队// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int val = 0;if(head == null){return -1;}else if(head == last){last = null;head = null;}else{val = head.value;head = head.next;head.prev = null;}--usedsize;//将有效元素--return val;//返回删除的值}public int peek(){//获取队尾元素if(head==null){return -1;}return head.value;}public int size(){//获取队列中有效元素的个数return usedsize;}}

 2.3 队列的分类

(1) 普通队列

普通队列就是队列最基本的形式,我们模拟实现的就是普通队列,普通队列遵行先进先出的原则

(2) 循环队列 

循环队列是将队列存储空间的最后一个位置绕到第一个位置,从而形成一个环,依然遵循先进先出的原则进行操作:

循环队列的好处 :

  • 相较于普通队列,解决了顺序队列(底层用数组实现的队列)中可能出现的假溢出问题,提高了存储空间的利用率
  • 入队和出队的时间复杂度均为O(1),操作效率高
 (3) 双端队列
双端队列( deque)是指允许两端都可以进行入队和出队操作的队列,它综合了栈和队列的特点,元素可以从队头和队尾进行插入或删除,那么在集合框架中有一个Deque, deque “double ended queue” 的简称。 那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。 Deque 是一个接口,使用时必须创建 LinkedList 的对象。

 三. 栈和队列的优缺点

1. 栈的优缺点

栈的优点:

  • 操作简单高效:入栈和出栈操作的时间复杂度均为O(1),能快速实现数据的插入和删除,在对时间要求严格的场景中表现出色。
  • 空间利用率高:只需动态分配内存来存储栈中的元素,无需预留大量额外空间,内存管理高效。

栈的缺点:

  • 数据访问受限:只能访问栈顶元素,若要访问其他元素,需先将栈顶元素依次出栈,操作不便且效率低。
  • 功能相对单一:主要用于数据的暂存和特定顺序的处理,在复杂数据结构和算法中,单独使用栈可能无法满足需求,需与其他数据结构配合。

 2. 队列的优缺点

队列的优点:

  • 先进先出顺序保证:严格按照先进先出原则处理数据,在模拟现实世界中的排队现象、任务调度等场景中,能确保数据处理的公平性和顺序性。
  • 多端操作灵活:双端队列等特殊队列结构支持在两端进行插入和删除操作,为数据处理提供了更多灵活性,可适应不同应用场景需求。

队列的缺点:

  • 出队操作效率问题:在某些实现方式中,出队操作可能涉及到元素的移动或指针的调整,时间复杂度可能较高,影响整体性能。
  • 空间管理复杂:在动态分配内存的队列中,频繁的入队和出队操作可能导致内存碎片产生,影响内存空间的有效利用和管理。

 以上就是本期栈和队列的全部内容啦,在此感谢大家的观看!!!

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

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

相关文章

在clion中使用MySQL的教程

首先就是配置好东西&#xff0c;也是非常简单的&#xff1a; 1.把mysql安装目录&#xff08;其中的lib好像&#xff09;中的2个文件复制到下面就行 2.然后配置&#xff0c;这个文件 cmake_minimum_required(VERSION 3.24) project(2024_12project)include_directories(D:\\mys…

某名校考研自命题C++程序设计——近10年真题汇总(下)

第二期&#xff0c;相比上一贴本帖的题目难度更高一些&#xff0c;我当然不会告诉你我先挑简单的写~ 某名校考研自命题C程序设计——近10年真题汇总&#xff08;上&#xff09;-CSDN博客文章浏览阅读651次&#xff0c;点赞9次&#xff0c;收藏13次。本帖更新一些某校的编程真题…

探讨不同类型的自动化测试框架

以下为作者观点&#xff1a; 在自动化测试中&#xff0c;框架提供了一种组织和执行测试案例的结构化方式。它们提供了一套准则和最佳实践&#xff0c;使测试人员能够编写可重复使用、可维护和可扩展的测试脚本。在这篇文章中&#xff0c;我们将讨论自动化测试中不同类型的框架…

C# 网络编程--关于Socket编程TCP协议中封包、拆包问题

在使用 Socket 编程&#xff0c;进行TCP协议网络通信时&#xff0c;经常会遇到“粘包”&#xff08;也称为“封包、拆包”&#xff09;的问题。粘包是指发送方发送的多个数据包被接收方合并成一个数据包&#xff0c;或者一个数据包被拆分成多个数据包接收。这通常是由于 TCP协议…

HarmonyOS:@Observed装饰器和@ObjectLink装饰器:嵌套类对象属性变化

装饰器仅能观察到第一层的变化&#xff0c;但是在实际应用开发中&#xff0c;应用会根据开发需要&#xff0c;封装自己的数据模型。对于多层嵌套的情况&#xff0c;比如二维数组&#xff0c;或者数组项class&#xff0c;或者class的属性是class&#xff0c;他们的第二层的属性变…

Excel拆分脚本

Excel拆分 工作表按行拆分为工作薄 工作表按行拆分为工作薄 打开要拆分的Excel文件&#xff0c;使用快捷键&#xff08;AltF11&#xff09;打开脚本界面&#xff0c;选择要拆分的sheet&#xff0c;打开Module&#xff0c;在Module中输入脚本代码&#xff0c;然后运行脚本 Su…

【机器人】Graspness 端到端 抓取点估计 | 论文解读

在复杂场景中实现抓取检测&#xff0c;Graspness是一种端到端的方法&#xff1b; 输入点云数据&#xff0c;输出抓取角度、抓取深度、夹具宽度等信息。 开源地址&#xff1a;GitHub - rhett-chen/graspness_implementation: My implementation of Graspnet Graspness. 论文地…

盛元广通畜牧与水产品检验技术研究所LIMS系统

一、系统概述 盛元广通畜牧与水产品检验技术研究所LIMS系统集成了检测流程管理、样品管理、仪器设备管理、质量控制、数据记录与分析、合规性管理等功能于一体&#xff0c;能够帮助实验室实现全流程的数字化管理。在水产、畜牧产品的质检实验室中&#xff0c;LIMS系统通过引入…

kubeadm安装K8s高可用集群之集群初始化及master/node节点加入calico网络插件安装

系列文章目录 1.kubeadm安装K8s高可用集群之基础环境配置 2.kubeadm安装K8s集群之高可用组件keepalivednginx及kubeadm部署 3.kubeadm安装K8s高可用集群之集群初始化及master/node节点加入集群calico网络插件安装 kubeadm安装K8s高可用集群之集群初始化及master/node节点加入ca…

【机器学习】以机器学习为翼,翱翔网络安全创新苍穹

我的个人主页 我的领域&#xff1a;人工智能篇&#xff0c;希望能帮助到大家&#xff01;&#xff01;&#xff01;&#x1f44d;点赞 收藏❤ 在数字化浪潮汹涌澎湃的当下&#xff0c;网络安全如同守护数字世界的坚固堡垒&#xff0c;其重要性不言而喻。而机器学习技术的蓬勃…

go引用包生成不了vendor的问题

比如我要引入github.com/jinzhu/gorm这个包. 1. 首先获取包 go get github.com/jinzhu/gorm 这时go.mod文件中也有这个包依赖信息了. 2. 然后构建vendor go mod vendor 结果发现vendor目录下没有生成对应的包, 而且modules.txt也注释掉这个包了. 原因是没有其进行引用, go…

多模块的spring boot项目发布指定模块的脚本

我有一个多模块的Spring Boot项目&#xff0c;里面有基础模块&#xff0c;有业务模块&#xff0c;业务模块依赖一些基础模块。发布的时候&#xff0c;如果单独将某个模块发布&#xff0c;一般会报错。所以我都是整个项目&#xff0c;无论多少个模块&#xff0c;不管3721&#x…

fabric.js

目录 一、在canvas上画简单的图形 二、在canvas上用路径(Path)画不规则图形 三、在canvas上插入图片并设置旋转属性(angle) 四、让元素动起来(animate) 五、图像过滤器(filters)让图片多姿多彩 六、颜色模式(Color)和相互转换(toRgb、toHex) 七、对图形的渐变填充(Gradi…

23. 合并 K 个升序链表(java)

题目描述&#xff1a; 给你一个链表数组&#xff0c;每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中&#xff0c;返回合并后的链表。 示例 1&#xff1a; 输入&#xff1a;lists [[1,4,5],[1,3,4],[2,6]] 输出&#xff1a;[1,1,2,3,4,4,5,6] 解释&#xff…

爬取Q房二手房房源信息

文章目录 1. 实战概述2. 网站页面分析3. 编写代码爬取Q房二手房房源信息3.1 创建项目与程序3.2 运行程序&#xff0c;查看结果 4. 实战小结 1. 实战概述 本次实战项目旨在通过编写Python爬虫程序&#xff0c;抓取深圳Q房网上的二手房房源信息。我们将分析网页结构&#xff0c;…

【蓝桥杯】43699-四平方和

四平方和 题目描述 四平方和定理&#xff0c;又称为拉格朗日定理&#xff1a; 每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去&#xff0c;就正好可以表示为 4 个数的平方和。 比如&#xff1a; 502021222 712121222; 对于一个给定的正整数&#xff0c;可…

Kerberos身份验证

Kerberos是更现代化的身份验证协议&#xff0c;它比 NTLM 认证更安全&#xff0c;但域内某些服务仍支持 NTLM 认证。Kerberos 和 NTLM 认证一样&#xff0c;都是通过在 SSPI 接口实现的功能&#xff0c;这使得使用第三方协议&#xff08;如&#xff1a;HTTP、SMB、LDAP&#xf…

达梦8-达梦数据的示例用户和表

1、示例库说明&#xff1a; 创建达梦数据的示例用户和表&#xff0c;导入测试数据。 在完成达梦数据库的安装之后&#xff0c;在/opt/dmdbms/samples/instance_script目录下有用于创建示例用户的SQL文件。samples目录前的路径根据实际安装情况进行修改&#xff0c;本文将达梦…

认识javascript中的模块化

什么是模块化&#xff1f; 将程序⽂件依据⼀定规则拆分成多个文件&#xff0c;拆分出来每个⽂件就是⼀个模块&#xff0c;模块中的数据都是私有的&#xff0c;模块之间互相隔离。如果不进行隔离&#xff0c;可能会造成模块间的变量定义有冲突&#xff0c;导致程序崩溃 为啥要使…

EasyExcel 动态设置表格的背景颜色和排列

项目中使用EasyExcel把数据以excel格式导出&#xff0c;其中设置某一行、某一列单元格的背景颜色、排列方式十分常用&#xff0c;记录下来方便以后查阅。 1. 导入maven依赖&#xff1a; <dependency><groupId>com.alibaba</groupId><artifactId>easy…