Multiple choice

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

  1. non-increasing order

  2. non-decreasing order

  3. strictly increasing order

  4. strictly decreasing order
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

To simulate a stack (LIFO) using a priority queue (which returns the smallest key), we need to assign keys such that the most recently added item has the smallest key. Therefore, keys must be strictly decreasing.

Keep practicing — related questions