A priority queue Q is used to implement a stack S that stores characters.…
1997
A priority queue Q is used to implement a stack S that stores characters. PUSH(C) is implemented as INSERT(Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in
- A.
Non-increasing order
- B.
Non-decreasing order
- C.
Strictly increasing order
- D.
Strictly decreasing order
Attempted by 109 students.
Show answer & explanation
Correct answer: D
A stack follows Last-In-First-Out (LIFO) semantics, meaning the most recently added element must be removed first.
Since DELETEMIN removes the element with the smallest key, the last inserted character must have the smallest key value.
Consequently, every subsequent push operation must assign a strictly smaller integer key than all previous keys to maintain correct stack behavior.
A video solution is available for this question — log in and enroll to watch it.