201. How can a priority queue implement a stack or a queue?
MediumPriority queues & heaps
Technical
Show model answer
Attach a monotonically increasing counter (timestamp) to each pushed item and use it as the priority. For a queue (FIFO), use a min-heap on the timestamp: the oldest item comes out first. For a stack (LIFO), use a max-heap on the timestamp (or a min-heap on its negation): the newest item comes out first.
Each operation costs O(log n) instead of the O(1) of a dedicated stack or queue, so this is a conceptual reduction rather than a practical design. It is also how priority queues make equal-priority items behave FIFO: break ties with an insertion counter.