Suppose implementation supports an instruction REVERSE, which reverses the…

2023

Suppose 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?

  1. A.

    A queue cannot be implemented using this stack.

  2. B.

    A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.

  3. C.

    A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

  4. D.

    A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Attempted by 2 students.

Show answer & explanation

Correct answer: C

Concept

A queue must remove elements in First-In-First-Out (FIFO) order -- whichever element arrived earliest must come out first. A plain stack only ever exposes its top for PUSH and POP, giving Last-In-First-Out (LIFO) access; adding a REVERSE instruction that flips the order of every element lets the same top position be made to hold either end of the arrival order, at the cost of extra instructions.

Applying it to this stack

Maintain the invariant that the current front of the queue (the earliest arrival still present) always sits at the top of the stack.

  1. DEQUEUE: simply POP. Because the front already sits at the top by the invariant, one POP removes exactly the earliest remaining arrival -- a single instruction.

  2. ENQUEUE, step 1: REVERSE the stack. This flips the order of every element, moving the current front from the top to the bottom and bringing the back position to the top.

  3. ENQUEUE, step 2: PUSH the new element. It lands on top, i.e. logically behind every earlier arrival.

  4. ENQUEUE, step 3: REVERSE again. This restores the invariant -- the front (the earliest arrival) is back on top, ready for the next DEQUEUE.

So ENQUEUE costs exactly three instructions (REVERSE, PUSH, REVERSE) and DEQUEUE costs exactly one (POP).

Cross-check

Trace two enqueues then a dequeue on an empty stack. Enqueue the first arrival: REVERSE on an empty stack changes nothing, PUSH places it, REVERSE again leaves it alone -- the stack holds only the first arrival. Enqueue the second arrival: REVERSE leaves the stack unchanged, PUSH puts the second arrival on top, REVERSE flips the order so the first arrival is back on top. DEQUEUE now POPs the first arrival, exactly the earliest of the two, confirming the invariant and the three-and-one instruction split.

Why the other splits fail

  • A queue is not impossible to build here: REVERSE gives access to the far end of the stack, defeating a plain top-only LIFO limitation.

  • A single PUSH for ENQUEUE combined with a REVERSE-then-POP for DEQUEUE can retrieve the oldest element correctly just once, but it leaves the remaining elements in flipped order; the next ENQUEUE (another plain PUSH) then inserts relative to that flipped order, so this pairing does not stay consistent across repeated ENQUEUE and DEQUEUE calls.

  • Skipping REVERSE entirely keeps only the most recent arrival reachable at the top for both operations, which never enforces FIFO order, so neither operation can be reduced to a single instruction on both sides simultaneously.

Explore the full course: Coding For Placement