Suppose a stack implementation supports an instruction REVERSE, which reverses…
2014
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?
- A.
A queue cannot be implemented using this stack.
- B.
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
- C.
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
- D.
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.
Attempted by 300 students.
Show answer & explanation
Correct answer: C
Key idea: keep the front of the queue at the top of the stack so removing from the queue is a single POP.
ENQUEUE(x): REVERSE; PUSH x; REVERSE.
DEQUEUE(): POP.
Why this works: REVERSE makes the bottom item become the top, so after reversing and pushing the new element the new element sits at the top of the reversed stack. Reversing again restores the original order but with the new element placed at the bottom (the rear of the queue). Keeping the front at the top means DEQUEUE is just POP.
Example (stack shown top-to-bottom; top is queue front):
Start: 1, 2, 3 (1 is front, 3 is rear).
REVERSE -> 3, 2, 1.
PUSH 4 -> 4, 3, 2, 1.
REVERSE -> 1, 2, 3, 4 (now 1 is front, 4 is rear).
DEQUEUE (POP) would remove 1, the front element.
Therefore, ENQUEUE requires three instructions (REVERSE, PUSH, REVERSE) and DEQUEUE requires one instruction (POP).
A video solution is available for this question — log in and enroll to watch it.