Deque in which all pushes/pops (front/back) and get_min() are O(1) operations

Question

I am just wondering, whether it's possible to implement a structure (list/deque) which would have O(1) complexity (const/amortized doesn't matter) for get_min(), push_back(), push_front(), pop_back(), pop_front() operations?

It's definitely possible to implement stack or even queue (for them push() and pop() are available only for one end) which will satisfy these conditions. But I wasn't able to reuse this logic to a dequeue case.

It's also possible to create structure which will have O(logn) complexity for pushes/pops and O(1) for get_min (just using simple list and min_heap in which deletion of arbitrary element for O(logn) is available).

But still amortized O(1) for all operations seems impossible for me. If that is the case, can the information about exact number of operations (or max possible number of elements in list) n helps (simpler case)? Can we somehow use O(n) (or even more) additional memory or smth like this?

Answer 1

It is indeed possible to build a min-deque where the push-front, push-back, and find-min operations work in worst-case time O(1) and the pop-front and pop-back operations take amortized time O(1). The easiest route that I know goes like this:

1. First, make a stack that supports push, pop, and find-min in time O(1). We’ll use this as a building block.
2. Use the construction that builds a deque out of three stacks, except using these min-stacks instead of regular stacks. You can then implement the find-min operation by querying each of the three stacks for its minimum element and returning the min of those values.

In case you haven’t seen how to do step (2), the idea is a generalization of how to make a queue from two stacks. You maintain two stacks representing the elements of the deque such that one stack represents the front of the deque in reverse order (stack top is the front of the deque, and deeper elements are the next elements of the deque) and the elements of the other stack represent the back of the deque (top element is the last element of the deque, deeper elements go backwards through the deque). For example, here’s one way to encode the deque 1, 2, 3, ..., 10:

front: | 7 6 5 4 3 2 1
back:  | 8 9 10

To push onto the front or back of the deque, just do a push onto the appropriate deque. To pop the front or back of the deque, if the appropriate stack is nonempty, just pop from it. Otherwise, if the stack is empty, you need to move some number of elements from the other stack over. Specifically, to keep things balanced between the two stacks, you do a series of pushes and pops to put half the elements into each of the two stacks. That looks like this:

1. Pop half the elements from the other stack and push them onto a temporary stack.
2. Pop the remaining elements from the other stack and push them onto the empty stack.
3. Pop the elements from the temporary stack and push them back onto the other stack.

You can show using a potential argument (see Φ to be the absolute value of the difference in heights of the two stacks) that each operation takes amortized time O(1).

It may be possible to somehow speed this up to worst-case O(1) time per operation using some sort of scheduling scheme, but I’m not sure how to do this. I know there’s a way to implement a queue with four stacks with worst-case O(1) for each operation, so perhaps this idea could be generalized to work here?