2

Implementing a queue with a max() API so that push(), pop(), and max() all work in (amortized) O(1) is a known solved problem. Is there a known solution for implementing a double ended queue with the same max() API which is faster than O(n)? Can it be proven that it's impossible?

Valentin
  • 1,108
  • 8
  • 18

1 Answers1

3

It's 100% possible to have a deque with an O(1) max api.

A deque can be implemented from two stacks. While there's some additional business logic in keeping the deque balanced, the idea is fairly simple. Imagine two stacks facing opposite directions joined together. From this structure you can pop and append to both sides.

It's possible to create a stack that has a constant time get_max() or get_min(). Each time you push onto the stack push onto it two things - (value, current_max). You can calculate the current_max in constant time by comparing the current_max in previous element to the current value. The result of get_max() will always be the current_max of the top of the stack.

If you implement a deque from two stacks that have the get_max() api, to get max of the deque, you only have to call get_max() for both stacks and return the bigger value.

Primusa
  • 13,136
  • 3
  • 33
  • 53
  • 1
    Great idea! I guess in this case although `get_max()` is O(1), maintaining a deque with two stacks requires O(1) amortized cost since when the either one is empty you will have to do O(n) work. – Kevin He Feb 10 '19 at 18:09