Java栈与队列深度解析:结构、实现与应用指南
一、栈与队列核心概念对比
特性 | 栈 (Stack) | 队列 (Queue) |
---|---|---|
数据原则 | LIFO(后进先出) | FIFO(先进先出) |
核心操作 | push(入栈)、pop(出栈)、peek(查看栈顶) | offer(入队)、poll(出队)、peek(查看队首) |
典型应用 | 函数调用栈、括号匹配、撤销操作 | 任务调度、BFS算法、消息缓冲队列 |
Java实现类 | Stack (遗留类) / Deque | LinkedList / ArrayDeque / PriorityQueue |
二、栈的Java实现方案
1. 标准库实现
// 推荐使用Deque作为栈(Java官方建议)
Deque<Integer> stack = new ArrayDeque<>();// 基本操作
stack.push(10); // 入栈
int top = stack.peek(); // 查看栈顶(不删除)
int val = stack.pop(); // 出栈// 不推荐使用遗留Stack类(同步开销大)
Stack<String> legacyStack = new Stack<>();
2. 自定义数组栈实现
public class ArrayStack<E> {private static final int DEFAULT_CAPACITY = 10;private Object[] elements;private int top = -1;public ArrayStack() {this(DEFAULT_CAPACITY);}public ArrayStack(int capacity) {elements = new Object[capacity];}public void push(E item) {if (top == elements.length - 1) {resize();}elements[++top] = item;}public E pop() {if (isEmpty()) {throw new EmptyStackException();}E item = (E) elements[top];elements[top--] = null; // 帮助GCreturn item;}private void resize() {int newSize = elements.length * 2;elements = Arrays.copyOf(elements, newSize);}
}
三、队列的Java实现体系
1. 队列类型与实现类
队列类型 | 特点 | 实现类 |
---|---|---|
普通队列 | 先进先出,无优先级 | LinkedList / ArrayDeque |
优先队列 | 按优先级出队 | PriorityQueue |
阻塞队列 | 支持等待式操作 | ArrayBlockingQueue / LinkedBlockingQueue |
双端队列 | 两端都可操作 | ArrayDeque / LinkedList |
并发队列 | 线程安全 | ConcurrentLinkedQueue |
2. 队列操作对比
Queue<String> queue = new LinkedList<>();// 添加元素
queue.offer("A"); // 推荐(返回boolean)
queue.add("B"); // 可能抛异常// 移除元素
String head = queue.poll(); // 返回null为空
String elem = queue.remove(); // 空队列抛异常// 查看队首
String peek = queue.peek(); // 不删除元素
四、核心数据结构实现原理
1. 栈的链表实现
public class LinkedStack<E> {private static class Node<E> {E item;Node<E> next;Node(E item, Node<E> next) {this.item = item;this.next = next;}}private Node<E> top;private int size;public void push(E item) {top = new Node<>(item, top);size++;}public E pop() {if (top == null) throw new EmptyStackException();E item = top.item;top = top.next;size--;return item;}
}
2. 循环队列实现(解决假溢出)
public class CircularQueue<E> {private final Object[] elements;private int front; // 队首指针private int rear; // 队尾指针private int count; // 元素计数public CircularQueue(int capacity) {elements = new Object[capacity];}public boolean offer(E e) {if (count == elements.length) return false;elements[rear] = e;rear = (rear + 1) % elements.length;count++;return true;}public E poll() {if (count == 0) return null;E e = (E) elements[front];elements[front] = null;front = (front + 1) % elements.length;count--;return e;}
}
五、高级应用场景
1. 栈的应用:括号匹配检查
public static boolean isBalanced(String expression) {Deque<Character> stack = new ArrayDeque<>();for (char c : expression.toCharArray()) {if (c == '(' || c == '[' || c == '{') {stack.push(c);} else {if (stack.isEmpty()) return false;char top = stack.pop();if ((c == ')' && top != '(') ||(c == ']' && top != '[') ||(c == '}' && top != '{')) {return false;}}}return stack.isEmpty();
}
2. 队列的应用:生产者-消费者模型
BlockingQueue<Task> queue = new LinkedBlockingQueue<>(10);// 生产者线程
new Thread(() -> {while (true) {Task task = generateTask();try {queue.put(task); // 阻塞直到有空间} catch (InterruptedException e) {Thread.currentThread().interrupt();}}
}).start();// 消费者线程
new Thread(() -> {while (true) {try {Task task = queue.take(); // 阻塞直到有元素processTask(task);} catch (InterruptedException e) {Thread.currentThread().interrupt();}}
}).start();
六、性能对比与选型建议
1. 不同实现的性能对比
操作 | ArrayDeque | LinkedList | PriorityQueue |
---|---|---|---|
插入/删除 | O(1) | O(1) | O(log n) |
随机访问 | O(1) | O(n) | O(n) |
内存占用 | 连续空间更优 | 节点额外开销 | 数组堆结构 |
2. 选型决策树
是否需要优先级处理? ├── 是 → 使用PriorityQueue └── 否 → 需要线程安全?├── 是 → 使用ConcurrentLinkedQueue或BlockingQueue└── 否 → 预估数据量?├── 小 → LinkedList└── 大 → ArrayDeque
七、常见问题解决方案
1. 实现最小栈(O(1)获取最小值)
class MinStack {private Deque<Integer> stack = new ArrayDeque<>();private Deque<Integer> minStack = new ArrayDeque<>();public void push(int x) {stack.push(x);if (minStack.isEmpty() || x <= minStack.peek()) {minStack.push(x);}}public void pop() {if (stack.pop().equals(minStack.peek())) {minStack.pop();}}public int getMin() {return minStack.peek();}
}
2. 用队列实现栈
class MyStack {Queue<Integer> queue = new LinkedList<>();public void push(int x) {queue.offer(x);// 将前n-1个元素重新入队for (int i = 1; i < queue.size(); i++) {queue.offer(queue.poll());}}public int pop() {return queue.poll();}
}
八、Java 8+新特性应用
1. Stream操作队列
Queue<Integer> queue = new LinkedList<>(Arrays.asList(3,1,4,1,5));// 过滤并收集
List<Integer> filtered = queue.stream().filter(n -> n > 2).collect(Collectors.toList());// 并行处理(注意线程安全)
ConcurrentLinkedQueue<Integer> safeQueue = new ConcurrentLinkedQueue<>(queue);
safeQueue.parallelStream().map(n -> n * 2).forEach(System.out::println);
2. Lambda表达式简化操作
PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> b.length() - a.length() // 自定义比较器
);pq.offer("Java");
pq.offer("Python");
pq.offer("C++");while (!pq.isEmpty()) {System.out.println(pq.poll()); // 输出:Python, Java, C++
}
九、最佳实践总结
-
栈的选择原则:
-
单线程环境优先使用
ArrayDeque
-
需要同步时使用
Collections.synchronizedDeque()
-
避免使用遗留的
Stack
类
-
-
队列的选择原则:
-
高并发场景使用
ConcurrentLinkedQueue
-
需要阻塞功能选择
BlockingQueue
实现 -
优先级处理使用
PriorityQueue
-
-
通用建议:
-
预估数据规模选择底层存储结构
-
注意边界条件(空栈/空队列操作)
-
合理使用容量限制防止内存溢出
-
性能口诀:
-
数组实现随机访问快
-
链表实现增删效率高
-
优先队列按需排序
-
并发场景选择线程安全实现
通过深入理解栈和队列的特性,开发者可以更高效地解决算法问题和系统设计挑战。
相关文章:
Java栈与队列深度解析:结构、实现与应用指南
一、栈与队列核心概念对比 特性栈 (Stack)队列 (Queue)数据原则LIFO(后进先出)FIFO(先进先出)核心操作push(入栈)、pop(出栈)、peek(查看栈顶)offer(入队)、poll(出队)、peek(查看队首)典型应用函数调用栈、括号匹配、撤销操作任…...
CentOS DVD完整版与Minimal版的区别
文章目录 一、体积与内置软件:从“大而全”到“小而精”二、安装体验:开箱即用 vs 高度定制三、适用场景:桌面与服务器的分水岭四、后续配置:时间成本的权衡五、性能与资源占用六、推荐新手下载完整版建议: 在 CentOS…...
AI日报 - 2025年4月13日
🌟 今日概览(60秒速览) ▎🤖 AGI突破 | OpenAI CFO称AGI可能已到来 Sarah Friar透露Sam Altman认为AGI潜力尚未完全发挥,引发行业热议 ▎💼 商业动向 | OpenAI开发新型AI工程师A-SWE 超越Copilot,能独立完成应用构建、…...
有哪些基于solidity的应用
🔥 Solidity 常见应用分类(附例子) 🏦 1. DeFi(去中心化金融) Solidity 的最大应用场景之一。 项目功能示例合约逻辑Uniswap去中心化交易所(AMM)流动性池、定价算法、swap函数Aave /…...
mybatis--多对一处理/一对多处理
多对一处理(association) 多个学生对一个老师 对于学生这边,关联:多个学生,关联一个老师[多对一] 对于老师而言,集合,一个老师有多个学生【一对多】 SQL: 测试环境搭建 1.导入依…...
中兴B860AV3.2-U-晶晨S905L3B芯片-安卓9.0-2+8G-线刷固件包
中兴B860AV3.1-U/B860AV3.2-U--晶晨S905L3B芯片-安卓9.0-28G-线刷固件包 线刷方法:(新手参考借鉴一下) 1、准备好一根双公头USB线刷刷机线,长度30-50CM长度最佳,同时准备一台电脑; 2、电脑上安…...
资源分配不均,如何优化
优化资源分配需要关注资源需求评估精准性、资源调度合理性、实时监控与反馈机制、沟通协调的高效性以及持续改进的管理理念。其中,资源需求评估精准性最为关键。精准的资源需求评估意味着对项目各阶段所需资源的准确把控,这能有效防止资源过剩或短缺现象…...
Kimi-VL 解读:高效 MoE 视觉语言模型VLM,兼顾长上下文与高分辨率
写在前面:一起读多模态大模型Kimi-VL Moonshot AI 推出了 Kimi-VL,一个高效的、开源的、基于混合专家(MoE)架构的视觉语言模型。Kimi-VL 旨在解决上述痛点,它具备以下几个核心特点: 高效 MoE 架构:语言解码器采用 MoE 架构,在保持强大能力的同时,显著降低了推理时的激…...
2024团体程序设计天梯赛L3-1 夺宝大赛
L3-037 夺宝大赛 分数 30 作者 陈越 单位 浙江大学 夺宝大赛的地图是一个由 nm 个方格子组成的长方形,主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里,同时开始向大本营进发。所有参赛队从一个方格…...
SpringBoot DevTools:开发工具与热部署机制
文章目录 引言一、Spring Boot DevTools概述二、自动重启机制2.1 工作原理2.2 自定义重启触发器 三、LiveReload支持3.1 浏览器自动刷新3.2 与前端框架集成 四、属性默认值调整4.1 缓存配置4.2 日志配置 五、远程开发支持5.1 配置远程应用5.2 使用远程客户端 总结 引言 在Java…...
PyCharm 开发工具 修改字体大小及使用滚轮没有反应
PyCharm 开发工具 修改字体大小及使用滚轮没有反应 提示:帮帮志会陆续更新非常多的IT技术知识,希望分享的内容对您有用。本章分享的是Python基础语法。前后每一小节的内容是有学习/理解关联性,希望对您有用~ PyCharm 开发工具 修改字体大小及…...
小刚说C语言刷题——每日一题东方博宜1000熟悉OJ环境
1.题目描述 2.参考代码(C语言版) #include <stdio.h> int main(void) { //定义两个整型变量num1和num2 int num1,num2; int sum;//定义两个数的和sum //下面语句表示输入两个数字 scanf("%d%d",&num1,&num2); sumnum1num…...
Ubuntu安装Docker容器,通过Tomcat部署项目
温馨提示:本教程不是最完美的,只能说是填鸭式教育,仅仅让你快速部署Docker的tomcat项目。 *******命令行需要一行一行操作哟!!!******* 一、检查Ubuntu本地的Tomcat能发正常打开项目 1.1 检查本地tomcat是…...
ubuntu22.04安装zabbix7.0
一、安装repository wget https://repo.zabbix.com/zabbix/7.0/ubuntu/pool/main/z/zabbix-release/zabbix-release_latest_7.0ubuntu24.04_all.deb dpkg -i zabbix-release_latest_7.0ubuntu24.04_all.deb apt update二、安装Zabbix server,Web前端,ag…...
AIGC工具平台-建筑平面图3D渲染
本模块是一款智能化的建筑设计辅助工具,可将任意房屋平面设计图快速转换为高品质3D渲染效果图,让建筑设计更加直观、高效。用户无需复杂的3D建模操作,仅需上传房屋平面图,系统即可一键生成符合实际尺度的3D渲染效果,精…...
OpenGL学习笔记(立方体贴图、高级数据、高级GLSL)
目录 立方体贴图天空盒环境映射斯涅尔定律(Snells Law)菲涅尔效应(Fresnel Effect)动态环境贴图 高级数据分批顶点属性复制缓冲 高级GLSL顶点着色器变量片段着色器变量接口块Uniform缓冲对象Uniform块布局使用Uniform缓冲测试 Git…...
嵌入式进阶:如何选择合适的开发平台?
随着现代工业、物联网以及人工智能技术的迅速发展,嵌入式系统已经由简单的控制器向复杂的高性能系统迈进。从传统家电到智能机器人、从自动驾驶汽车到工业自动化,每一项应用都对嵌入式系统的响应速度、运行稳定性和能耗管理提出了更高要求。在这种背景下…...
CVPR‘25 SOTA——GoalFlow论文精读
1)第一遍___粗读 Q: 这篇论文试图解决什么问题? A: 这篇论文提出了一个名为 GoalFlow 的端到端自动驾驶方法,旨在解决自动驾驶场景中高质量多模态轨迹生成的问题。具体而言,它试图解决以下问题: 轨迹选择的复杂性&am…...
vue3 onMounted 使用方法和注意事项
基础用法 / 语法糖写法 <script> import { onMounted } from vue;// 选项式 API 写法 export default {setup() {onMounted(() > {console.log(组件已挂载);});} } </script><script setup> onMounted(() > {console.log(组件已挂载); }); </scrip…...
【ubuntu】linux开机自启动
目录 开机自启动: /etc/rc.loacl system V 使用/etc/rc*.d/系统运行优先级 遇到的问题: 1. Linux 系统启动阶段概述 方法1:/etc/rc5.d/ 脚本延时日志 方法二:使用 udev 规则来触发脚本执行 开机自启动: /etc/…...
OpenCV day2
Matplotlib相关知识 Matplotlib相关操作: import numpy as np from matplotlib import pyplot as pltx np.linspace(0, 2 * np.pi, 100) y1 np.sin(x) y2 np.cos(x)# 使用红色虚线,圆点标记,线宽1.5,标记大小为6绘制sin plt.p…...
OpenCV 图形API(31)图像滤波-----3x3 腐蚀操作函数erode3x3()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 使用3x3矩形结构元素腐蚀图像。 该函数通过使用中心作为锚点的3x3矩形结构元素来腐蚀源图像。腐蚀操作可以应用多次(迭代࿰…...
机器学习概述自用笔记(李宏毅)
机器学习概述 机器学习即找一个复杂的人类写不出来的函数,把输入(向量,矩阵,序列)转换为输出。 regression:输出是一个数值(预测PM2.5的数值) classification:选择设置…...
大数据面试问答-Spark
1. Spark 1.1 Spark定位 "Apache Spark是一个基于内存的分布式计算框架,旨在解决Hadoop MapReduce在迭代计算和实时处理上的性能瓶颈。 1.2 核心架构 Spark架构中有三个关键角色: Driver:解析代码生成DAG,协调任务调度&a…...
UE5 设置父物体和解除父子关系(移除子物体)
文章目录 设置父物体解除父子关系 Acotor类似于untiy的objecttransfrom,可以用来进行父子操作 设置父物体 Actor attach to Actor节点 解除父子关系 Detach From Actor...
Git - 怎么把当前修改追加到前面某个commit中
怎么把当前修改追加到前面某个commit中 git log commit b7cb11b53388d410d07e3b3084c67274cee4cdad (HEAD -> hotfix/task-108344, origin_dbackup/hotfix/task-108344) Author: aaa <aaammm.com> Date: Thu Mar 27 15:08:32 2025 0800Fix #108344: add bbbcommit …...
【HFP】蓝牙 HFP 协议状态通知机制研究
目录 一、状态通知体系架构 1.1 核心功能矩阵 1.2 三层控制体系 1.3 角色分工 1.4 协议栈层级 二、核心AT命令解析 2.1 ATCMER:指示器状态报告控制 2.2 ATBIA:指示器激活控制 2.3 CIEV:未请求结果码 三、关键功能实现机制 3.1 注册…...
unity100天学习计划
以下是一个为期100天的Unity学习大纲,涵盖从零基础到独立开发完整游戏的全流程,结合理论、实践和项目实战,每天学习2-3小时: 第一阶段:基础奠基(Day 1-20) 目标:掌握Unity引擎基础与C#编程 Day 1-5:引擎入门 安装Unity Hub和Unity Editor(LTS版本)熟悉Unity界面:S…...
STM32电机库 电机控制特性
ST MC FW库提供FOC和六步法两种电机控制方式。这使得它能够驱动永磁同步电机 (PMSM) 和无刷直流电机 (BLDC)。FOC 更适合 PMSM,而六步法更适合 BLDC 电机。该固件可以驱动内嵌式PMSM 和标贴式PMSM。 ST Motor Control 固件库提供以下功能: FOC SVPWM 生成: 可配置的 PW…...
MySQL数据库 - 事务
事务 此笔记参考黑马教程,仅学习使用,如有侵权,联系必删 文章目录 事务1. 事务简介2. 事务操作2.1 事务操作 - 方式一2.2 方式二代码实现 3. 事务四大特性(ACID)4. 并发事务问题5. 事务隔离级别代码实现 总结 1. 事务…...
火山引擎旗下的产品
用户问的是火山引擎旗下的产品,我需要详细列出各个类别下的产品。首先,我得确认火山引擎有哪些主要业务领域,比如云计算、大数据、人工智能这些。然后,每个领域下具体有哪些产品呢?比如云计算方面可能有云服务器、容器…...
用 Python 从零构建异步回显服务器
简介 让我们从 0 开始,搭建一个异步服务输出服务器。 套接字 套接字(socket),是不同计算机中实现通信的一种方式,你可以理解成一个接口,它会在客户端和服务端建立连接,一台发送数据ÿ…...
【3D文件】可爱小鹿3D建模,3D打印文件
【3D文件】可爱小鹿3D建模,3D打印文件 免费下载,下载链接: 3D文件可爱小鹿3D建模,可爱小鹿建模仿真,小鹿仿真设计,3D打印文件,免费下载资源-CSDN文库 资源下载: 3D文件可爱小鹿3D…...
RabbitMQ 优先级队列详解
本文是博主在记录使用 RabbitMQ 在执行业务时遇到的问题和解决办法,因此查阅了相关资料并做了以下记载,记录了优先级队列的机制和使用要点。 本文为长文,详细介绍了相关的知识,可作为学习资料看。 文章目录 一、优先级队列介绍1、…...
串口通信简述
一.串口的特点 1.全双工异步通信 全双工指通信双方可以同时进行数据的发送和接收操作。 异步通信是指通信双方不使用共同的时钟信号来同步数据传输,而是通过特殊的信号或约定来标识数据的开始和结束 2.数据字长度可编程(8 位或 9 位) 不…...
【2025年五一数学建模竞赛A题】完整思路和代码
1.问题背景与重述 2.解题思路分析 2.1 问题一的分析 问题一假设无人机以平行于水平面的方式飞行并投放物资,可以将物资的运动 类比成平抛运动,由于物资的重量较大,因此不能简单的看成质点,还要考虑物资 的重量。 2.1.1本题要求给…...
为了四季度的盈利,李斌的换人还在继续
李斌对蔚来和乐道人事调整还在继续。 4月10日,蔚来发布内部邮件宣布大量人事变动。 蔚来方面: 原用户关系(UR)负责人沈泓因个人原因将离开公司。 任命孙明担任用户关系(UR)负责人,向高级副总…...
Pytest 自动化测试框架详解
Pytest和Unittest测试框架的区别? 如何区分这两者,很简单unittest作为官方的测试框架,在测试方面更加基础,并且可以再次基础上进行二次开发,同时在用法上格式会更加复杂;而pytest框架作为第三方框架&#x…...
sqli-labs靶场 less 9
文章目录 sqli-labs靶场less 9 时间盲注 sqli-labs靶场 每道题都从以下模板讲解,并且每个步骤都有图片,清晰明了,便于复盘。 sql注入的基本步骤 注入点注入类型 字符型:判断闭合方式 (‘、"、’、“”…...
奇趣点播系统测试报告
1.项目简介 本项目旨在搭建一个视频共享点播系统,服务器支持用户通过前端浏览器访问服务器,获取展示与观看和操作的界面,最终实现视频的上传以及观看和删改查等基础管理功能。让用户拥有良好的观看体验和分享视频的快捷方式,此外…...
空地机器人在复杂动态环境下,如何高效自主导航?
随着空陆两栖机器人(AGR)在应急救援和城市巡检等领域的应用范围不断扩大,其在复杂动态环境中实现自主导航的挑战也日益凸显。对此香港大学王俊铭基于阿木实验室P600无人机平台自主搭建了一整套空地两栖机器人,使用Prometheus开源框架完成算法的仿真验证与…...
01 - QEMU 初始化概览 - Init()
目录 1.初始化 - qemu_init() 1.1.基本设备 1.2.日志 1.3.模块信息 1.4.子系统 1.5.选项解析 - 阶段一 1.6.选项解析 - 阶段二 1.7.选项配置 1.8.Trace 1.9.主线程 1.10.CPU 时钟 1.11.其他设置 1.12.创建虚拟机 1.13.启动虚拟机 2.主线程 - qemu_main() 2.1.处…...
Vue3 使用ref
<button click"changeMsg">change</button> <div>{{ message }}</div>//接受一个内部值并返回一个响应式且可变的 ref 对象。ref 对象仅有一个 .value property,指向该内部值。 const message ref(hello world) const mum 1 co…...
React中 点击事件写法 的注意(this、箭头函数)
目录 1、错误写法:onClick{this.acceptAlls()} 2、正确写法:onClick{this.acceptAlls}(不带括号) 总结 方案1:构造函数绑定 方案2:箭头函数包装方法(更简洁) 方案3&am…...
DeepSeek AI大模型:中国智能时代的“争气机“-AI生成
DeepSeek AI大模型:中国智能时代的"争气机" 当全球科技巨头在万亿参数竞赛中你追我赶时,一家中国公司悄然改写了游戏规则。DeepSeek AI最新发布的"探月"大模型不仅以中英双语能力打破技术壁垒,更用"动态脑区"设…...
Java老鼠迷宫(递归)---案例来自韩顺平老师讲Java
题目: 粉色圈圈是启动,红色方框是阻挡,蓝色五角星是出口,走到出口,老鼠winner 代码: public class test6 {public static void main(String[] args){//创建二维数组int[][] map new int[8][7];// 最外围都…...
Python大数据视频教程
概述 最新整理的Python大数据视频教程已出,需要学习的小伙伴抓紧了。 课程亮点: ❶ 编程基石:从Python基础到高阶函数式编程,用代码驯服数据 ❷ 数据魔法:SQL进阶ETL实战,Pandas玩转百万级数据分析 ❸ 分…...
Java工厂模式解析:灵活对象创建的实践指南
精心整理了最新的面试资料和简历模板,有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 一、模式定义与分类 工厂模式(Factory Pattern)是创建型设计模式的核心成员之一,主要解决对象创建过程中的灵活性问题。根…...
PDF转换格式失败?原因及解决方法全解析
在日常工作中,我们经常会遇到将PDF转换为Word、Excel、PPT等格式的需求。有时候以为一键转换就能搞掂,没想到却转换失败。到底问题出在哪?别急,我们可以看看是否以下几个问题引起的,找到解决问题的关键! 原…...
《轨道力学讲义》——第五讲:摄动理论基础
第五讲:摄动理论基础 引言 在实际的航天任务中,我们很少能够使用理想的二体问题来精确描述航天器的运动。地球的非球形性、大气阻力、太阳辐射压以及第三天体引力等各种因素都会对航天器轨道产生偏离理想轨道的影响。这些额外的力被称为"摄动力&q…...