【数据结构】栈与队列的“双向奔赴”

目录
前言
1.使用“栈”检查符号是否成对出现
2.使用“栈”实现字符串反转
3.使用“队列”实现“栈”
4.使用“栈”实现“队列”
前言
什么是栈?
- 栈(stack)是一种特殊的线性数据集合,只允许在栈顶按照后进先出LIFO(Last In First Out)进行数据操作;
为什么使用栈?
- 常见应用场景:浏览器的前进与回退操作、虚拟机栈等;
如何使用栈?
- 栈的实现结构可以是一维数组或链表实现
- 用数组实现的栈叫做顺序栈。在Java中,顺序栈使用java.util.Stack类实现
- 用链表实现的栈叫做链式栈。在Java中,链式栈使用java.util.LinkedList类实现;
- 入栈(push):将新元素放入栈顶,只允许从栈顶一侧放入元素,类似于弹匣装弹,只能从弹匣口依次压入弹匣内;
- 出栈(pop):只有栈顶元素才允许出栈,类似于枪射出子弹时,子弹从弹匣口依次进入枪体射出;
- 时间复杂度:
- 访问指定位置的元素:O(n) ——>需要依次遍历所有元素,所需元素可能在栈底
- 入栈和出栈:O(1) ——>只涉及栈顶
什么是队列?
- 队列(queue)是一种线性数据结构,队列中的元素按照先入先出的规则从队尾进入,队头出队;按照实现机制分为:单队列、循环队列;
为什么使用队列?
- 常见应用场景:KTV点歌列表、阻塞队列、线程池的任务队列等;
如何使用队列?
- 队列的实现结构可以是数组或链表实现
- 用数组实现的队列叫做顺序队列。在Java中,顺序队列使用java.util.ArrayDeque类实现;
- 用链表实现的队列叫做链式队列。在Java中,链式队列使用java.util.LinkedList类实现;
- 入队(enqueue):只允许从队尾的位置放入元素,类似于银行取号等待叫号办理业务;
- 出队(dequeue):只允许从队头的位置移出元素;
- 假溢出:使用数组实现队列,执行出队操作时,指向队头和队尾的指针会向后移,队尾指针移动到最后的时候,无法添加数据,即使数组中之前出队的位置还要空闲空间,这种现象就是“假溢出”。
1. 使用“栈”检查符号是否成对出现
public static boolean isValid(String s ){HashMap<Character, Character> mappings = new HashMap<>();mappings.put('}','{');mappings.put(')','(');mappings.put(']','[');Stack<Character> stack = new Stack<>();for(int i=0;i<s.length();i++){char c =s.charAt(i);if(mappings.containsKey(c)){//当前字符是“右括号”char topElement = stack.isEmpty() ? '#' :stack.pop();char left = mappings.get(c);if(left != topElement){return false;}}else {//当前字符是"左括号"stack.push(c);}}return stack.isEmpty();}
解读:
- 创建一个HashMap
mappings,用于存储右括号和对应的左括号的映射关系;- 创建一个Stack
stack,用于存储遍历过程中遇到的左括号,以便后续进行匹配检查;- 进入for循环,遍历输入的字符串s。在循环中,取出字符串中的每个字符c;
- 如果当前字符c存在于
mappings中,即为右括号,那么就从栈中弹出栈顶元素,然后检查该右括号对应的左括号是否与弹出的左括号匹配,如果不匹配则返回false;- 如果当前字符c不存在于
mappings中,即为左括号,将其压入栈中;- 循环结束后,检查栈是否为空,如果栈为空则说明所有的括号都匹配,返回true,否则返回false;
- 测试用例
public static void main(String[] args) {String str ="{[(!)]}";System.out.println(isValid(str));}
- 测试结果

2. 使用“栈”实现字符串反转
public static void main(String[] args) {String str ="just do it";StringBuilder stringBuilder = new StringBuilder(str);//使用栈实现字符串反转Stack<Character> stringStack = new Stack<>();//入栈for(int i=0;i<str.length();i++){stringStack.push(str.charAt(i));}//出栈while (!stringStack.empty()){str +=stringStack.pop();}System.out.println(stringBuilder);}
解读:
- 创建一个Stack
stringStack,用于存储字符串中的字符;- 进入for循环,遍历输入的字符串
str,将字符串中的每个字符依次压入栈中;- 使用while循环,当栈不为空时,依次从栈中弹出字符,并将其拼接到原字符串
str的末尾;- 循环结束后,
str中存储的就是原字符串str的反转结果;
- 测试结果

3. 使用“队列”实现“栈”
public class MyStack{private Queue<Integer> queue1; //出栈队列private Queue<Integer> queue2; //入栈队列public MyStack(){queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x){queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop(){return queue1.poll();}public int top(){return queue1.peek();}public boolean empty(){return queue1.isEmpty();}@Overridepublic String toString() {return queue1.toString();}
}
解读:
- 定义了一个名为
MyStack的类,其中包含两个私有属性queue1和queue2,分别表示出栈队列和入栈队列,并在构造函数中对它们进行了初始化;push方法用于入栈操作,将元素加入queue2中,然后通过循环将queue1中的元素逐个转移到queue2中,以确保新入栈的元素位于队列的头部(因为队列的特性是先进先出)。最后交换queue1和queue2的引用,使得queue1始终指向当前栈中的元素所在的队列;pop方法用于出栈操作,直接从queue1中弹出元素即可;top方法用于获取栈顶元素,直接返回queue1的头部元素;empty方法用于判断栈是否为空,直接返回queue1是否为空的结果;用两个队列模拟栈的基本操作,通过不断在两个队列之间转移元素,使得栈的操作可以在队列上进行;
- 测试用例
public static void main(String[] args) {MyStack myStack = new MyStack();//入栈myStack.push(1);myStack.push(2);myStack.push(3);myStack.push(4);myStack.push(5);System.out.println("入栈后"+myStack);System.out.println("入栈后栈顶元素:"+myStack.top());//出栈myStack.pop();myStack.pop();myStack.pop();myStack.pop();myStack.pop();System.out.println("出栈后"+myStack);System.out.println("出栈后栈是否为空:"+myStack.empty());}
- 测试结果

4. 使用“栈”实现“队列”
public class Queue{//入队栈private Stack<Integer> inStack = new Stack<>();//出队栈private Stack<Integer> outStack = new Stack<>();//入队public void offer(int item){while(!outStack.empty()){inStack.push(outStack.pop());}//新元素入队inStack.push(item);}//出队public int poll(){while(!inStack.empty()){outStack.push(inStack.pop());}return outStack.pop();}//判断是否为空public boolean empty(){return outStack.size() == 0 && inStack.size() == 0;}@Overridepublic String toString() {return inStack.toString();}
}
解读:
offer方法用于向队列中添加元素。首先,它会将 outStack 中的元素逐个弹出并压入 inStack 中,这样可以确保之前入队的元素在 inStack 的底部,新的元素可以被放在队列的末尾,接着,将新元素直接入栈到 inStack 中,表示将新元素放入队列中。poll方法用于从队列中取出元素。首先,它会将 inStack 中的元素逐个弹出并压入 outStack 中,这样可以确保队列的头部元素位于 outStack 的栈顶,然后,从 outStack 中弹出栈顶元素,并作为出队操作的结果返回。empty方法用于检查队列是否为空。只有当 inStack 和 outStack 都为空时,才表示整个队列为空;基于两个栈实现队列的方法称为双栈法,通过巧妙地利用栈的特性,可以实现队列的先进先出(FIFO)功能。在实际应用中,双栈法可以用于需要频繁进行队列操作的场景,同时也可以作为栈和队列之间的一个有趣的数据结构转换方式。
- 测试用例
public static void main(String[] args) {Queue myQueue = new Queue();//入队myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);myQueue.offer(4);myQueue.offer(5);System.out.println("入队后:"+myQueue);//出队myQueue.poll();myQueue.poll();myQueue.poll();myQueue.poll();myQueue.poll();System.out.println("出队后是否为空:"+myQueue.empty());}
- 测试结果

相关文章:
【数据结构】栈与队列的“双向奔赴”
目录 前言 1.使用“栈”检查符号是否成对出现 2.使用“栈”实现字符串反转 3.使用“队列”实现“栈” 4.使用“栈”实现“队列” 前言 什么是栈? 栈(stack)是一种特殊的线性数据集合,只允许在栈顶按照后进先出LIFOÿ…...
sqllab第二十七关通关笔记
知识点: union select 关键字过滤 通过<> /**/进行截断处理 un<>ion sel<>ect 没效果uni/**/on sel/**/ect 被过滤了双写绕过 这关对select进行了多重过滤,无法进行双写绕过 大小写绕过 UNion SElect (这关可以用&am…...
助推直播产业升级与经济转型 天府锋巢直播产业基地成都开园
2023年年末,位于成都天府新区兴隆湖板块的天府锋巢直播产业基地正式开园,为成都直播产业注入了新的活力,助推成都经济转型和产业升级。天府锋巢直播产业基地的成立,不仅是成都直播产业的一大盛事,更是对成都经济发展的…...
VSCode+python单步调试库代码
VSCodepython单步调试库代码 随着VSCode版本迭代更新,在最新的1.87.x中,使用Python Debugger扩展进行调试时,扩展的justMyCode默认属性为true,不会进入库中的代码。这对debug而言不太方便,因此需要手动设置一下&#…...
如何使用EMC测试软件执行辐射抗扰度测试?(三)软件检查及手动模式
一、前言 之前的文章为大家介绍了使用EMC测试软件执行辐射抗扰度测试的测试方法、频率变化模式测试方法、校准方法及调制。本期文章继续为大家介绍软件检查和手动模式两部分内容。 前文回顾: 如何使用EMC测试软件执行辐射抗扰度测试?(一&am…...
云手机为电商提供五大出海优势
出海电商行业中,各大电商平台的账号安全是每一个电商运营者的重中之重,账号安全是第一生产力,也是店铺运营的基础。因此多平台多账号的防关联管理工具成了所有电商大卖家的必备工具。云手机最核心的优势就是账户安全体系,本文将对…...
chatgpt大模型基础学习
chatgpt大模型基础学习 1. 吴恩达提示工程2. 大模型说的token是什么 1. 吴恩达提示工程 知乎 https://zhuanlan.zhihu.com/p/626290417?utm_id0 中文版 https://mp.weixin.qq.com/s?__bizMzkwMjQ5MzExMg&mid2247483714&idx1&sn5e905f5ec6196f6dc2187db2a8618f02&…...
代码随想录算法训练营第14天 part01 | 二叉树理论基础篇
代码随想录 二叉树理论基础篇 二叉树的种类 二叉树有两种主要的形式:满二叉树和完全二叉树 满二叉树:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 这棵二叉树为满二叉树…...
async与defer的区别
原文解释 async vs defer attributes - Growing with the Web...
奇数乘积(C语言)
一、运行结果; 二、源代码; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值;int i 1;int j 3;//循环运算;while (j < 12){//运算;i i * j;//改变数值;j 2…...
中文分词库:jieba的词性对照表
jieba词性对照表 字母词性a形容词ad副形词ag形容词性语素an名形词b区别词c连词d副词dg副词素e叹词f方位词g语素h前接成分i成语j简称略称k后接成分l习用语m数词mq数量词n名词ng名词性语素nr人名ns地名nt机构团体名nz其他专名o拟声词p介词q量词r代词rg代词性语素rr人称代词rz指示…...
Linux:git的基础操作
git的下载 版本控制系统一般分为两种,集中式版本控制系统,分布式版本控制系统 什么是集中式版本控制系统:版本库集中存放在中央服务器,工作时候使用自己的电脑,当工作时候在中央服务器上拉取最新版本的代码,…...
【华为OD机试】CPU 算力分配【C卷|100分】
【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述 现有两组服务器A和B,每组有多个算力不同的CPU,其中 A[i] 是 A 组第 i 个CPU的运算能力, B[i] 是 B组 第 i 个CPU的运算能力。 一组服务器的总算力是各CPU的算力之和。 为了让两组服务器…...
挑战杯 机器视觉目标检测 - opencv 深度学习
文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 ǵ…...
基于Spring Boot的社区便民服务管理系统的设计与实现
摘 要 二十一世纪我们的社会进入了信息时代,信息管理系统的建立,大大提高了人们信息化水平。传统的管理方式对时间、地点的限制太多,而在线管理系统刚好能满足这些需求,在线管理系统突破了传统管理方式的局限性。于是本文针对这一…...
亚信安慧AntDB:数字化创新背后的数据力量
亚信安慧AntDB的“融合实时”的特性,不仅使得数据库具备了更强大的适应性,更让企业在不同业务场景下能够更好地实现业务目标,释放出更大的商业价值。融合实时的特性让AntDB具有了高度灵活性和实时性,使其能够满足企业在不同业务需…...
Matplotlib数据可视化实战-1数据可视化Matplotlib基础
1.1绘图的一般过程: 1.导入相关库 2.生成、读入或计算得到数据; 3.根据需要绘制折线图、散点图、柱状图、饼状图、雷达图、箱线图、三维曲线/曲面以及极坐标系图形; 4.根据需要设置图形属性; 5.显示或保存绘图结果。 例如&…...
信也科技发布消费者权益保护2023年度报告: 科技驱动、服务为先、合作共建社会化消保体系
3月15日消费者权益日当天,信也科技发布《消费者权益保护2023年度报告》(下称《报告》,消费者权益保护简称“消保”)。该报告为信也科技消保委员会成立后首份公开披露的消保工作年度总结。《报告》显示,信也科技通过智能…...
REDHAWK——连接(续)
文章目录 前言一、突发 IO1、数据传输①、输入②、输出 2、突发信号相关信息 (SRI)3、多输出端口4、使用复数数据①、在 C 中转换复数数据 5、时间戳6、端口统计①、C 二、消息传递1、消息生产者①、创建一个消息生产者②、发送消息 2、消息消费者①、创建消息消费者②、注册接…...
9.Python从入门到精通—Python 字符串格式化,三引号,Unicode 字符串
9.Python从入门到精通—Python 字符串格式化,三引号,Unicode 字符串 Python 字符串格式化Python 三引号Unicode 字符串创建 Unicode 字符串Python 的字符串内建函数 Python 字符串格式化 Python中的字符串格式化是指将一个字符串中的占位符替换为指定的值。Python中有多种字符串…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
