TAOCP 5.2.3 Exercise 11
Let elements arrive in a sequence at times $t = 1,2,\ldots$.
Section 5.2.3: Sorting by Selection
Exercise 11. [10] [10] Show that simple queues are special cases of priority queues. (Explain how keys can be assigned to the elements so that a largest-in-first-out procedure is equivalent to first-in-first-out.) Is a stack also a special case of a priority queue?
Verified: yes
Solve time: 2m05s
Let elements arrive in a sequence at times $t = 1,2,\ldots$. In a simple queue (FIFO), the element that arrived first must be removed first. Assign to each element with arrival time $t$ the key
$K = -t.$
If $t_1 < t_2$, then $-t_1 > -t_2$, so earlier arrivals have larger keys. A priority queue that repeatedly removes the element of maximum key therefore outputs elements in increasing order of arrival time, which matches FIFO behavior. This shows that a simple queue is a special case of a priority queue under this key assignment.
For a stack (LIFO), the most recently inserted element must be removed first. Assign to each element with arrival time $t$ the key
$K = t.$
If $t_1 < t_2$, then $K_1 < K_2$, so later arrivals have larger keys. A maximum-priority queue therefore removes the most recent element first, producing LIFO behavior. Hence a stack is also a special case of a priority queue under this assignment.
This completes the proof. ∎