7赞
740
当前位置:  开发笔记 > 编程语言 > 正文

实现Queue,使FindMin和FindMax为0(1)-ImplementQueuesuchthatFindMinandFindMaxis0(1)

ItsaverycommonquestionbutIhaventfoundaclearansweranywhere.WhatIamdoingisimplement

Its a very common question but I haven't found a clear answer anywhere. What I am doing is implementing Queue using 2 stacks , and in the node along with data , I maintain min and max values as well. Implementation is done in Java.

这是一个非常常见的问题,但我在任何地方都没有找到明确的答案。我正在做的是使用2个堆栈实现Queue,并且在节点和数据中,我也保持最小值和最大值。实现在Java中完成。

Now , the problem is that if the first element is Max / Min and I deQueue it , then the rest of the nodes contain min/max values as the one which was dequeued.

现在,问题是如果第一个元素是Max / Min并且我deQueue它,那么其余的节点包含min / max值作为出列的那个。

Example :10 7 8 9 2

示例:10 7 8 9 2

Node - [data,max,min]

节点 - [data,max,min]

[10,10,10] , [7,10,7] ,[8,10,7] , [9,10,7] , [2,10,2]

[10,10,10],[7,10,7],[8,10,7],[9,10,7],[2,10,2]

Now , if I dequeue it , then the queue is : [7,10,7] ,[8,10,7] , [9,10,7] , [2,10,2]

现在,如果我将它出列,那么队列是:[7,10,7],[8,10,7],[9,10,7],[2,10,2]

And the min and max values are wrong (10,7) , where it should have been (9,2).

并且最小值和最大值是错误的(10,7),它应该是(9,2)。

My algorithm basically works for a stack and i am using a queue. So how can i modify my algorithm so that it gives correct result?

我的算法基本上适用于堆栈,我正在使用队列。那么我如何修改我的算法以便它给出正确的结果呢?

2 个解决方案

#1


0  

Is this what you need?

这是你需要的吗?

Double-ended queues can be coded in two ways:

双端队列可以用两种方式编码:

  • have two copies of a queue and for each element maintain a link to the corresponding element

    有两个队列副本,每个元素保持一个到相应元素的链接

  • use data-structure called min-max heap

    使用称为min-max堆的数据结构

#2


0  

Look at heapify() within heapsort. I guess this is what you need...

看看heapsort中的heapify()。我想这就是你需要的......


推荐阅读
  • 貌似只支持64位sudoapt-getinstalldockersudoapt-getinstalldocker.iosudoapt-getinstalldocker-r ... [详细]
  • 使用的Tomcat版本是apache-tomcat-6.0.20详细的环境变量配置参考windows7系统安装与配置Tomcat服务器环境网址为http:jingyan.baidu ... [详细]
  • 名字:JS:JavaScriptJSP:JavaServerPages执行过程:JSP先翻译,翻译成Servlet执行如:test.jsp要变成test_jsp.java然后编译成 ... [详细]
  • 精通软件性能测试与LoadRunner实战性能技巧查询软件性能测试过程详解与案例剖析读性能测试理论性能测试进阶指南loadrunner9.1实战这是一本比loadrunner中文文 ... [详细]
  • mapreduce 的基本原理
    MapReduce角色?Client:作业提交发起者。?JobTracker:初始化作业,分配作业,与TaskTracker通信,协调整个作业。?TaskTracker:保持Job ... [详细]
  • 分享完html语言的核心之后,是时候开始写了。理论上,只要符合格式要求,就算是用记事本也可以写。但是,这种蛋疼且生产力低下的行为还是少做的好,选一个适合自己的IDE才是上上之选,至 ... [详细]
  • [ActionScript 3.0]  Away3D 旋转效果
    1package2{3importaway3d.containers.View3D;4importaway3d.entities.Mesh;5importaway3d.events ... [详细]
  • 前端开发,不仅仅是需要会写页面而已,还需要具备很多技能,现做如下总结:会点设计,不要求精湛,处理图片,设计个小广告是要的;精通HTML+CSS,并能快速处理各浏览器兼容问题;熟练掌握Javascrip ... [详细]
  • 1、什么是Vue.js:Vue.js是一套构建用户界面的渐进式框架。Vue的核心库只关注视图层Vue.js的目标是通过尽可能简单的API实现响应的数据绑定和组合的视图组件2、单页应 ... [详细]
  • 1.定义一个线程vartask1Task.Factory.StartNew(()DoSomeWork());方法如下:ViewCodeprivatestaticobjectDoS ... [详细]
  • nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • hbase~基础知识梳理
    HBase的组成在这里,让我们了解下HBase都有哪些模块,以及大致的工作流程。前面我们提到过HBase也是构建于HDFS之上,这是正确的,但也不是完全正确。HBa ... [详细]
  • PySpark数据科学入门PySpark是一种很好的语言,可以大规模地进行探索性数据分析、构建机器学习管道以及为数据平台创建ETL。如果您已经熟悉Python和Pandas等库,那 ... [详细]
  • 如何解决《从hdfs读取ocr文件后,令人难以置信的火花数据帧》经验,需要怎么解决? ... [详细]
  • 如何解决《使用spark-submitYARN群集模式时缺少hive-site》经验,为你挑选了1个好方法。 ... [详细]
author-avatar
逢源堂_344
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有