0

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.

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.

Example :10 7 8 9 2

Node - [data,max,min]

[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]

And the min and max values are wrong (10,7) , where it should have been (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?

h4ck3d
  • 6,134
  • 15
  • 51
  • 74
  • If this is a priority queue -- and you want to track the maximum elements -- then you're not going to get anywhere using stacks. A priority queue has an entirely different implementation from a queue. – Louis Wasserman Aug 21 '12 at 19:43
  • 2
    "Its a very common question .... I am doing is implementing Queue using 2 stacks" You have asked it many times, but I have never heard anyone ask this question, mostly because it doesn't make any sense, except perhaps as an interview question. Can you say why you want to do this. What problem are you trying to solve. – Peter Lawrey Aug 21 '12 at 19:44
  • @LouisWasserman Technically a Priority queue gives you the lowest element next. e.g. if sorted by time, you want the next node to occur. – Peter Lawrey Aug 21 '12 at 19:45
  • Why would use two stacks to implement a queue when you can use a Queue as a queue? – Peter Lawrey Aug 21 '12 at 19:46
  • 1
    Can you say what it is used for? what real world problem are you trying to solve? Can you give a reference where someone else has discussed this problem? – Peter Lawrey Aug 21 '12 at 19:49
  • While none of these explain why you would do this (other than for an interview question), they all suggest you want the min OR the max but not both. Can you clarify that you want "FindMin and FindMax is 0(1)"? I don't believe its a common problem. Common problems tend to have millions of hits on google. – Peter Lawrey Aug 21 '12 at 19:59
  • I just need to know the algo for EITHER of them , FindMin or FindMax , however , in my code I will implement for both of them. – h4ck3d Aug 21 '12 at 20:03
  • @PeterLawrey: is is an interview question, or at least a variation upon those. E.g. from "Cracking the Coding Interview", 5th ed., by G.L. McDowell, problem 3.2: "How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time." – fdierre Aug 21 '12 at 22:29

2 Answers2

0

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

foxx1337
  • 1,859
  • 3
  • 19
  • 23
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

Emily
  • 2,577
  • 18
  • 38