GATE CS 2014 Set 2 Q41 — Arrays, Stacks and Queues

To implement a queue (FIFO: First-In-First-Out) using a stack (LIFO: Last-In-First-Out) that supports PUSH, POP, and REVERSE, we need to map the queue operations to stack instructions.

Analyzing Option C:

Suppose we want the DEQUEUE operation to take a single instruction. For this to work, the oldest element in the queue must always reside at the top of the stack so that a simple POP removes it.

Let the current stack state be $[c, b, a]$ (where $a$ is at the top and is the oldest element, and $c$ is at the bottom and is the newest).

• DEQUEUE (1 instruction):
  Simply perform POP.
  Resulting stack: $[c, b]$ (with $b$ now at the top).
• ENQUEUE(x) (3 instructions):
  To insert a new element $x$ such that it becomes the newest element (at the bottom of the stack), we perform the following sequence:
  1. REVERSE: The stack becomes $[b, c]$ (with $c$ at the top).
  2. PUSH(x): The stack becomes $[b, c, x]$ (with $x$ at the top).
  3. REVERSE: The stack becomes $[x, c, b]$ (with $b$ at the top).
  Resulting stack: $[x, c, b]$ (where $b$ is at the top and ready to be dequeued next, and $x$ is at the bottom).

This implementation requires exactly 3 instructions for ENQUEUE and 1 instruction for DEQUEUE, which perfectly matches statement C.