You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack
See here for the full implementation.
Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.
To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values. (Of course, there's some extra logic here is case one of the stacks is empty, but that's not too hard to work around).
It will have O(1)
[4,2,5,1]
(1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]
.See here for the full implementation.
Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.
To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values. (Of course, there's some extra logic here is case one of the stacks is empty, but that's not too hard to work around).
It will have O(1)
get_min()
and push()
and amortized O(1) pop()
.
0 comments:
Post a Comment