实现Queue，使FindMin和FindMax为0（1）-ImplementQueuesuchthatFindMinandFindMaxis0(1)

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 个解决方案