当前位置: 首页 > news >正文

双栈实现一个队列

两个栈可实现将列表倒序:设有含三个元素的栈 A = [1,2,3] 和空栈 B = [] 。若循环执行 A 元素出栈并添加入栈 B ,直到栈 A 为空,则 A = [] , B = [3,2,1] ,即栈 B 元素为栈 A 元素倒序。

利用栈 B 删除队首元素:倒序后,B 执行出栈则相当于删除了 A 的栈底元素,即对应队首元素。

因此,可以设计栈 A 用于加入队尾操作,栈 B 用于将元素倒序,从而实现删除队首元素。

函数设计:

  1. 加入队尾 push() : 将数字 val 加入栈 A 即可。
  2. 获取队首元素 peek() :
    1. 当栈 B 不为空: B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。
    2. 否则,当 A 为空: 即两个栈都为空,无元素,因此返回 -1 。
    3. 否则: 将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。
  3. 弹出队首元素 pop() :
    1. 执行 peek() ,获取队首元素。
    2. 弹出 B 的栈顶元素。
  4. 队列判空 empty() : 当栈 A 和 B 都为空时,队列为空。

代码:

class MyQueue {private Stack<Integer> A;private Stack<Integer> B;public MyQueue() {A = new Stack<>();B = new Stack<>();}public void push(int x) {A.push(x);}public int pop() {int peek = peek();B.pop();return peek;}public int peek() {if (!B.isEmpty()) return B.peek();if (A.isEmpty()) return -1;while (!A.isEmpty()){B.push(A.pop());}return B.peek();}public boolean empty() {return A.isEmpty() && B.isEmpty();}
}

相关文章:

  • 新手小白的pytorch学习第一弹-------张量
  • 生成日志系统和监控
  • 算法·高精度
  • C++的介绍与认识
  • 用JavaScript将 NCR(Numeric Character Reference)标记转换为对应字符的方法
  • 对称加密和非对称加密解析
  • 关于力扣150题目——逆波兰表达式求值Java实现的三种解法
  • 如何写好品牌宣传稿提升品牌曝光?看这篇文章就够了
  • Java虚拟机(JVM):深入理解与性能调优
  • 如何在应用运行时定期监控内存使用情况
  • “LNMP环境搭建实战指南:从零开始配置CentOS 7下的Nginx、MySQL与PHP“
  • C# —— Directory类
  • Java 中的异常处理机制是如何工作的?请解释 try-catch-finally 的基本用法?
  • 如何远程访问运行电脑上运行的程序?
  • 【知网CNKI-注册安全分析报告】
  • IE9 : DOM Exception: INVALID_CHARACTER_ERR (5)
  • 【Redis学习笔记】2018-06-28 redis命令源码学习1
  • 【翻译】Mashape是如何管理15000个API和微服务的(三)
  • 07.Android之多媒体问题
  • 30秒的PHP代码片段(1)数组 - Array
  • Angular 响应式表单之下拉框
  • Angular数据绑定机制
  • HomeBrew常规使用教程
  • Java 多线程编程之:notify 和 wait 用法
  • JavaScript设计模式系列一:工厂模式
  • jQuery(一)
  • laravel 用artisan创建自己的模板
  • Linux编程学习笔记 | Linux IO学习[1] - 文件IO
  • Linux编程学习笔记 | Linux多线程学习[2] - 线程的同步
  • magento2项目上线注意事项
  • MySQL-事务管理(基础)
  • tensorflow学习笔记3——MNIST应用篇
  • ⭐ Unity 开发bug —— 打包后shader失效或者bug (我这里用Shader做两张图片的合并发现了问题)
  • Vue2.x学习三:事件处理生命周期钩子
  • 阿里中间件开源组件:Sentinel 0.2.0正式发布
  • 翻译:Hystrix - How To Use
  • 复习Javascript专题(四):js中的深浅拷贝
  • 前嗅ForeSpider中数据浏览界面介绍
  • 如何学习JavaEE,项目又该如何做?
  • 一个JAVA程序员成长之路分享
  • 浅谈sql中的in与not in,exists与not exists的区别
  • ​flutter 代码混淆
  • # centos7下FFmpeg环境部署记录
  • $ git push -u origin master 推送到远程库出错
  • $.type 怎么精确判断对象类型的 --(源码学习2)
  • %3cli%3e连接html页面,html+canvas实现屏幕截取
  • (CPU/GPU)粒子继承贴图颜色发射
  • (Python第六天)文件处理
  • (webRTC、RecordRTC):navigator.mediaDevices undefined
  • (八)c52学习之旅-中断实验
  • (笔试题)分解质因式
  • (论文阅读23/100)Hierarchical Convolutional Features for Visual Tracking
  • (求助)用傲游上csdn博客时标签栏和网址栏一直显示袁萌 的头像
  • (转载)Linux网络编程入门
  • .bat批处理(一):@echo off