A Queue that Supports Enqueue, Dequeue, and GetMin in Constant Time | Algorithms Notes

A Queue that Supports Enqueue, Dequeue, and GetMin in Constant Time | Algorithms Notes

Design a queue that supports enqueue, dequeue, and retrieving the minimum element in constant time.

Solution:

Suppose that there are two elements x and y, such that x < y. If y is enqueued before x is enqueued, then y cannot be the output of operation getMin, since a queue is first-in-first-out. Based on this idea, we can use another queue that stores only the elements that can be outputted by getMin. For any elements y in this queue and x, the element before y, y is no smaller than x and y is enqueued before x is enqueued.

The algorithm is as follows. Use two queues A and B, where A stores all elements and B is a queue of minima. For enqueueing an element x, first enqueue x into A. Then, starting from the tail of B, remove all elements smaller x in B and enqueue x into B. For the dequeue operation, first dequeue A's head element and call it y. If y is the same as B's head element, then dequeue B's head element as well. Finally, return y. For the getMin operation, return B's head element. In this way, all three operations can be done in O(1) time.

Read full article from A Queue that Supports Enqueue, Dequeue, and GetMin in Constant Time | Algorithms Notes