数据结构 - 栈 与 队列 - (java)
前言
本篇介绍栈和队列,了解栈有顺序栈和链式栈,队列底层是双链表实现的,单链表也可以实现队列,栈和队列的相互实现和循环队列;如有错误,请在评论区指正,让我们一起交流,共同进步!
文章目录
- 前言
- 1. 栈的认识
- 1.1 栈的使用:栈实现队列
- 2. 队列的认识
- 2.1 双队列实现栈
- 2.2 循环队列 - 数组实现的队列
- 3. 双端队列
- 总结
本文开始
1. 栈的认识
栈:一种特殊的线性表,只能从一头进入,一头出;
进出栈规则:先进后出
栈的模拟实现:顺序栈和链式栈实现栈时间复杂度都是O(1)
顺序栈:栈可以使用顺序表实现
链式栈:可以用单链表实现:头插和头删(入栈) 或 尾插和尾删(出栈);
可以使用双链表实现;既可以头进头出,也可以尾进尾出;(双链表知道前后节点位置)
链式栈代码实现:
public static void main(String[] args) {//链表实现栈:LinkedList底层是双链表LinkedList<Integer> stack = new LinkedList<>();stack.push(1);stack.push(2);stack.push(3);System.out.println(stack.pop());}
代码实现栈的基本操作:
public static void main(String[] args) {Stack<Integer> stack = new Stack<>();//压栈:栈中添加元素stack.push(2);stack.push(3);//看栈顶元素System.out.println(stack.peek());//栈的大小System.out.println(stack.size());//出栈System.out.println(stack.pop());//栈是否为空System.out.println(stack.isEmpty());}
1.1 栈的使用:栈实现队列
双栈实现队列代码:
思路:
一个栈1表示入队,一个栈2表示出队;
队列出队需要判断栈2是否为空,栈2空将栈1中元素全部放到栈2中,此时再出栈2栈顶元素即可;
入队:看栈2是否有元素,栈2有元素直接返回栈顶元素;栈2为空,再将栈1中元素放到栈2中,才能看到出队的值;
public class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;//创建两个栈public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}//在栈1中放元素public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}//判断栈2中是否有元素if(stack2.isEmpty()) {//栈1元素全部放到栈2中while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}//不空,栈2中有元素直接弹出return stack2.pop();}public int peek() {if(empty()) {return -1;}//看栈2是否有元素if(stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}//栈2有元素return stack2.peek();}//判断两个栈是否为空public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}
2. 队列的认识
1.队列:也是一种特殊的线性表,一头进,另一头出;
进出队列规则:先进先出;
2.链表实现队列:
单链表实现队列两种方式: - ==使用一种下标
头插法:进队-时间复杂的O(1) - 头插 ,出队-时间复杂的O(n) - 尾删
尾插法:进队-时间复杂的O(n) - 尾插,出队-时间复杂的O(1) - 头删
(两个下标控制头尾)单链表实现队列代码实现:
思想:使用头删尾插,进队出队时间复杂都是O(1);使用两个下标,记录头节点位置head,再记录尾节点位置last; 方便头插(入队),尾删(出队);
【注】单链表实现队列只能尾插头删,保证时间复杂度都为O(1)
不使用头插尾删原有?
使用头插尾删进行单链表,进队-头插时间复杂度O(1), 出队-尾删时间复杂度O(n);
尾删:每次删除都需要找尾节点前一个节点位置,需要遍历一般链表所以时间复杂度高;
代码:
public class MyQueue {static class Node {int val;Node next;public Node(int val) {this.val = val;}}//用双下标实现队列,需要定义两个public Node head;//头下标public Node last;//尾下标public int size;//入队操作: 插入public boolean offer(int val) {//插入需要新节点,创建新节点Node node = new Node(val);//没有节点的时候if(head == null) {//头尾下标指向同一位置head = node;last = node;}else {//head != null//链接新节点last.next = node;//尾节点向后移动一步last = node;}size++;//计数return true;}//出队:删除头删public int poll(int val) {//判断链表是否为空if(isEmpty()) {return -1;}//记录删除的值int v = head.val;head = head.next;//如果只有一个节点,lasta也需要置空if(head == null) {last = null;}size--;//-1return v;}private boolean isEmpty() {return size == 0;}public int peek() {//链表为空不用看队头元素if(isEmpty()) {return -1;}return head.val;//返回队头元素}public int getSize() {//队列大小return size;}
}
双链表实现队列代码实现:
特点:双链表实现队列可以自由头进尾删,头删尾进;
public class MyQueue2 {//双链表实现队列static class Node {int val;Node prev;Node next;public Node(int val) {this.val = val;}}//前后下标public Node front;public Node last;public int size;//入队public boolean offer(int val) {//插入的新节点Node newNode = new Node(val);//没有节点if(front == null) {front = newNode;last = newNode;}else {//不为空//链接前后节点newNode.prev = last;last.next = newNode;//后下标后移last = newNode;}size++;return true;}//出队:删除public int poll() {int v = -1;//队列为空if(isEmpty()) {return -1;}//只有一个节点if(front == last) {front = null;last = null;}else {//先记录值v = front.val;//前下标后移front = front.next;//找到前一个下标的next置为空front.prev.next = null;//当前prev置为空:防止空指针异常front.prev = null;}size--;return v;}private boolean isEmpty() {return size == 0;}public int peek() {if(isEmpty()) {return -1;}return front.val;}
}
队列基本操作代码实现:
public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();//入队:队列中添加元素queue.offer(1);queue.offer(2);queue.offer(3);//看队头元素System.out.println(queue.peek());//队列的大小System.out.println(queue.size());//出队System.out.println(queue.poll());//队列是否为空System.out.println(queue.isEmpty());}
2.1 双队列实现栈
双队列实现栈:
思路:
①先定义两个队列
②入栈:是判断那个队列不为空,队列1不为空,就往队列1中放,队列2不为空,就往队列2中放,都为空默认往队列1中放;
③出栈:假设不为空队列元素个数为size个,将不为空的队列出队size-1个到另一个为空的队列,出队列size-1个队列剩余一个就为出栈元素;
④栈顶元素:假设队列1不为空,队列2空;定义一个变量为tmp, 作为队列1元素到队列2元素的过度,将队列1中元素全部传到队列2中,此时队列1最后出队的元素就是栈顶元素,并存储在tmp中,返回tmp即可;
代码实现:
import java.util.LinkedList;
import java.util.Queue;public class MyStack {//双队列实现栈//构建双队列Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {//两个对谁不为空,就入那个队if(!queue1.isEmpty()) {queue1.offer(x);}else if(!queue2.isEmpty()) {queue2.offer(x);}else {//都为空,入第一个队queue1.offer(x);}}public int pop() {//判断队列是否为空//都为空if(empty()) {return -1;}if(!queue1.isEmpty()) {//获取队列1大小int size = queue1.size();//队1出size-1个元素,到队2中while (size - 1 != 0) {queue2.offer(queue1.poll());size--;}//队1只剩1个,就是要出栈的元素return queue1.poll();}else {//队1为空,队2不为空//获取队列2大小int size = queue2.size();//队2出size-1个元素,到队1中while (size - 1 != 0) {queue1.offer(queue2.poll());size--;}//队2只剩1个,就是要出栈的元素return queue2.poll();}}public int top() {//判断队列是否为空//都为空if(empty()) {return -1;}if(!queue1.isEmpty()) {//获取队列1大小int size = queue1.size();int tmp = -1;//存储每个出队元素while (size != 0) {tmp = queue1.poll();queue2.offer(tmp);size--;}//队1最后一个出队的,就是要栈顶的元素return tmp;}else {//获取队列2大小int size = queue2.size();int tmp = -1;//存储每个出队元素while (size != 0) {tmp = queue2.poll();queue1.offer(tmp);size--;}//队2最后一个出队的,就是要栈顶的元素return tmp;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}
2.2 循环队列 - 数组实现的队列
循环队列:可以看成一圈型的队列,但其实还是数组
为什么使用循环?
一个存满的数组,先出队一个,如果再进队尾rear下标就越界了,但数组中还有空间没有利用 =》 对于这种情况所以使用了循环;
怎么实现循环?
1.可以使用下标标记法,进队一个标记一个,从而实现循环;
2.牺牲一个空间,使用求余来实现循环 ( rear + 1) % length;(循环需要首尾相连,如图从7下标到0下标,求余就可以实现;)
实现循环队列:
思路分析:
判断循环队列是否为空还是满,就使用牺牲一个空间法,(rear + 1) == front 判断为满;
rear == front 判断为空;如下图
怎样实现循环:使用求余数的方法,可以让下标从尾下标到开始下标(如图0下标到7下标);
循环队列代码:
class MyCircularQueue {//循环链表:底层是数组,所以创建数组int[] elem;//循环的前后下标int front;//前int rear;//后public MyCircularQueue(int k) {//初始化k大小的数组elem = new int[k + 1];}//进队public boolean enQueue(int value) {//进队先判断队列是否满if(isFull()) {return false;}//不满进队elem[rear] = value;//rear++ =》不能使为下标到起始下标,进行循环,所以使用求余数;rear = (rear + 1) % elem.length;return true;}//出队public boolean deQueue() {//出队先判断队列是否有元素if(isEmpty()) {return false;}//前下标+1,与需要考虑构成循环,末尾到开始位置front = (front + 1) % elem.length;return true;}//获取队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];//不为空就返回}//获取队尾元素public int Rear() {if(isEmpty()) {return -1;}//牺牲一个空间法,尾下标超过尾元素1个数组空间 =》所以一般情况:尾下标需要-1才是尾元素//会遇到一种尾下标在(0位置)起始位置,而尾元素在最后位置,需要构成循环 =》 这里特殊情况,特殊出来0下标位置int index = (rear == 0) ? elem.length - 1 : rear - 1;return elem[index];}//判断是否为空public boolean isEmpty() {return rear == front;}//判断是否满public boolean isFull() {//循环队列使用牺牲1个空间方法,区分空和满//rear+1 再余 =>构成循环,尾下标就能够到起始下标;return (rear + 1) % elem.length == front;}
}
3. 双端队列
双端队列:是一种继承Queue的接口,可以用它实现栈与队列;
实现栈,队列:
Deque<Integer> stack1 = new ArrayDeque<>();Deque<Integer> stack2 = new LinkedList<>();Deque<Integer> queue1 = new LinkedList<>();
总结
✨✨✨各位读友,本篇分享到内容如果对你有帮助给个👍赞鼓励一下吧!!
感谢每一位一起走到这的伙伴,我们可以一起交流进步!!!一起加油吧!!!
相关文章:

数据结构 - 栈 与 队列 - (java)
前言 本篇介绍栈和队列,了解栈有顺序栈和链式栈,队列底层是双链表实现的,单链表也可以实现队列,栈和队列的相互实现和循环队列;如有错误,请在评论区指正,让我们一起交流,共同进步&a…...
CellularAutomata元胞向量机-8-渗流集群MATLAB代码分享
%% Percolation Clusterclf clc, clearthreshold .63; % ax axes(units,pixels,position,[1 1 650 700],color,k); text(units, pixels, position, [150,255,0],... string,美赛,color,w,fontname,helvetica,fontsize,100) text(units, pixels, position, [40,120,0],... str…...

iOS UI自动化测试详解
前言: 小目标 关于UI自动化的定义,我想要的是自动地按照流程去点击页面、输入数据,不需要人去参与,节省人工时间。比如登录,能够自己去填写用户名&密码,然后点击按钮跳转到下一个页面等。在能够保证业…...

Mybatis源码分析(九)Mybatis的PreparedStatement
文章目录一 JDBC的PreparedStatement二 prepareStatement的准备阶段2.1 获取Connection2.1.1 **UnpooledDataSource**2.1.2 PooledDataSource2.2 Sql的预编译PreparedStatementHandler2.3 为Statement设置参数2.4 执行具体的语句过程官网:mybatis – MyBatis 3 | 简…...
winfrom ui
http://www.iqidi.com/download/warehouse/Device_DotNetBar.rar http://qiosdevsuite.com/Download https://sourceforge.net/projects/qiosdevsuite/ https://www.cnblogs.com/hcyblogs/p/6758381.html https://www.cnblogs.com/jordonin/p/6484366.html MBTiles地图瓦片管…...

中国国家级地面气象站基本气象要素日值数据集(V3.0)
数据集摘要 数据集包含了中国基本气象站、基准气候站、一般气象站在内的主要2474个站点1951年1月以来本站气压、气温、降水量、蒸发量、相对湿度、风向风速、日照时数和0cm地温要素的日值数据。数据量为21.3GB。 (1)SURF_CLI_CHN_MUL_DAY-TEM-12001-201501.TXT 气温数据TEM, 包…...
【Python语言基础】——Python NumPy 数组副本 vs 视图
Python语言基础——Python NumPy 数组副本 vs 视图 文章目录 Python语言基础——Python NumPy 数组副本 vs 视图一、Python NumPy 数组副本 vs 视图一、Python NumPy 数组副本 vs 视图 副本和视图之间的区别 副本和数组视图之间的主要区别在于副本是一个新数组,而这个视图只是…...

Spring Cloud_OpenFeign服务接口调用
目录一、概述1.OpenFeign是什么2.能干嘛二、OpenFeign使用步骤1.接口注解2.新建Module3.POM4.YML5.主启动类6.业务类7.测试8.小总结三、OpenFeign超时控制1.超时设置,故意设置超时演示出错情况2.是什么3.YML中需要开启OpenFeign客户端超时控制四、OpenFeign日志打印…...
十三、GIO GTask
GTask表示管理一个可取消的“任务task” GCancellable GCancellable是一个线程安全的操作取消栈,用于整个GIO,以允许取消同步和异步操作。 它继承于GObject对象,不是一个单纯的结构体 相关函数 g_task_new GTask* g_task_new (GObject*…...

ch4_1存储器
1. 存储器的类型 1.1 按照存储介质来分类 半导体存储器: TTL, MOS 易失性 磁表面存储器: 磁头, 载磁体; 磁芯存储器: 硬磁材料, 环状元件 光盘存储器: 激光, 磁光材料; 1.2 按…...
Doris通过Flink CDC接入MySQL实战
1. 创建MySQL库表,写入demo数据 登录测试MySQL mysql -u root -pnew_password创建MySQL库表,写入demo数据 CREATE DATABASE emp_1;USE emp_1; CREATE TABLE employees_1 (emp_no INT NOT NULL,birth_date DATE NOT NULL,…...

搭建zookeeper高可用集群详细步骤
目录 一、虚拟机设置 1.新建一台虚拟机并克隆三台,配置自定义 2.修改四台虚拟机的主机名并立即生效 3.修改四台虚拟机的网络信息 4.重启四台虚拟机的网络服务并测试网络连接 5.重启四台虚拟机,启动后关闭四台虚拟机的防火墙 6.在第一台虚拟机的/e…...

Scala 变量和数据类型(第二章)
第二章、变量和数据类型2.1 注释2.2 变量和常量(重点)2.3 标识符的命名规范2.4 字符串输出2.5 键盘输入2.6 数据类型(重点)回顾:Java数据类型Scala数据类型2.7 整数类型(Byte、Short、Int、Long)…...

【JVM基础内容速查表】JVM基础知识 默认参数 GC命令 工具使用 JVM参数设置、说明、使用方法、注意事项等(持续更新)
目录一、JVM前置知识1. -X、-XX含义2. JVM参数值的类型和设置方式3. 查看GC时用到的命令和JVM参数4. 查看JVM默认参数二、垃圾收集器选择-XX:UseSerialGC-XX:UseParallelGC-XX:UseParallelOldGC-XX:UseParNewGC-XX:UseConcMarkSweepGC-XX:UseG1GC三、垃圾收集器特有参数1. ParN…...
C语言经典编程题100例(61~80)
目录61、练习7-7 矩阵运算62、练习7-8 方阵循环右移63、习题6-1 分类统计字符个数64、习题6-2 使用函数求特殊a串数列和65、习题6-4 使用函数输出指定范围内的Fibonacci数66、习题6-5 使用函数验证哥德巴赫猜想67、习题6-6 使用函数输出一个整数的逆序数68、练习8-2 计算两数的…...

toxssin:一款功能强大的XSS漏洞扫描利用和Payload生成工具
关于toxssin toxssin是一款功能强大的XSS漏洞扫描利用和Payload生成工具,这款渗透测试工具能够帮助广大研究人员自动扫描、检测和利用跨站脚本XSS漏洞。该工具由一台HTTPS服务器组成,这台服务器将充当一个解释器,用于处理恶意JavaScript Pay…...

Keepalived与HaProxy的协调合作原理分析
Keepalived与HaProxy的协调合作原理分析keepalived与haproxy合作场景更好的理解方式协调合作中考虑的问题一、Keepalived以TCP/IP模型角度来分析:二、HaProxy总结:协调合作中考虑的问题的答案虚拟ip:虚拟IP技术,就是一个未分配给客…...
抖音如何找到博主视频推广?筛选博主要看那些数据
近年来抖音视频推广越来越成为企业宣传的热门选择,今天就来和大家聊聊抖音如何找到博主视频推广,以及几种主流的对接方式。一、什么是抖音博主视频推广?抖音博主视频推广就是通过博主的影响力和粉丝量,吸引用户到短视频平台进行观看相关合作…...

Win11的两个实用技巧系列之如何关闭登录密码?
Win11如何关闭登录密码?Win11关闭登录密码的两种解决方法win11是电脑更新后的全新系统,每次开启需要输入密码。有的用户嫌麻烦想要关闭,下面小编就为大家带来了关闭的方法,一起来看看吧有不少用户在升级或者第一次使用Win11系统的时候&#…...
润普挂卷失败之老卷宗对接NP无法获取案件信息问题排查
润普挂卷失败之老卷宗对接NP无法获取案件信息问题排查 写在最前面 根因:NP的dzjzzzfw与老卷宗dzjz服务用的zookeeper不是同一个,且老卷宗指向的zookeeper没有任何一个匹配的dzjzzzfw。仅有消费者,没有任何生产者,导致老卷宗通过…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...

EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...