GATE CS 2014 Set 2 Q.51 (CS Q.41): Stacks and Queues

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 queue cannot be implemented using this stack.

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

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

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

Official answer and solution

Official answer: C
From: Official GATE 2014 answer key

Solution

Orient the stack so that either the front or the rear of the queue is always at the top of the stack, and evaluate instruction counts.

Queue Requirements:
- A queue operates on a FIFO basis: elements enter at the rear (ENQUEUE) and leave at the front (DEQUEUE).
- A stack operates on a LIFO basis: both insertions and deletions occur at the top.
Using the REVERSE Instruction:
- Suppose we maintain the invariant that the front of the queue is at the top of the stack.
  - DEQUEUE: To remove the front element, execute a single POP instruction (1 instruction).
  - ENQUEUE( $x$ ): New elements must be appended to the bottom of the stack (rear of the queue):
    1. Execute REVERSE (now the bottom becomes the top).
    2. Execute PUSH(x) (pushes $x$ on top).
    3. Execute REVERSE (reverses back, restoring original elements with the front at the top).
      This takes a sequence of 3 instructions.
Alternative Invariant:
- If the rear is at the top of the stack, ENQUEUE takes 1 instruction (PUSH(x)), but DEQUEUE requires REVERSE, POP, REVERSE (3 instructions).
Conclusion:
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction, which corresponds to option (C).

Final answer

Common trap

Thinking that a single stack can never implement a queue without a second data structure, overlooking the power of the REVERSE instruction.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 51 of 65, printed as CS Q.41
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source