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 $\text{with respect to this modified stack}$?

A queue follows First-In, First-Out (FIFO) order, whereas a stack follows Last-In, First-Out (LIFO) order.

We can implement a queue using the modified stack such that the front of the queue is always at the top of the stack:

• DEQUEUE operation: Since the oldest element (front of the queue) is maintained at the top of the stack, DEQUEUE simply performs a single POP instruction (1 instruction).

• ENQUEUE(x) operation: To insert a new element at the bottom of the stack (rear of the queue) while keeping the oldest at the top:

  1. REVERSE (the newest elements move to the top)

  2. PUSH(x) (push the new element)

  3. REVERSE (restore order so that the oldest element is back at the top)

  This takes a sequence of 3 instructions.

Thus, a queue can be implemented where ENQUEUE takes a sequence of 3 instructions and DEQUEUE takes a single instruction, making (C) the correct statement.