The GATE Grind

GATE 2014 CS (CS2) – Question 51

Programming and Data Structures · Stacks and Queues · 2 marks · Multiple choice

A stack supports REVERSE (reverses all elements) in addition to PUSH and POP. Which is TRUE?

  1. A queue cannot be implemented.
  2. A queue can have one-instruction ENQUEUE and two-instruction DEQUEUE.
  3. A queue can have three-instruction ENQUEUE and one-instruction DEQUEUE.
  4. Both ENQUEUE and DEQUEUE can take one instruction each.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) A queue can have three-instruction ENQUEUE and one-instruction DEQUEUE.

Explanation

Keep the oldest queued item at the stack top. To enqueue, reverse the stack, push the new item, then reverse again, restoring older items ahead of it. Dequeue is a single pop. Thus **C**, three instructions for enqueue and one for dequeue, preserves FIFO order after every operation.