The GATE Grind

GATE 2012 CS (CS1) – Question 45

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

A circular queue stores at most n−1 items in an n-element array. REAR and FRONT index insertion/deletion positions and both start zero. Identify full and empty tests.

  1. Full: (REAR+1) mod n == FRONT; empty: REAR == FRONT
  2. Full: (REAR+1) mod n == FRONT; empty: (FRONT+1) mod n == REAR
  3. Full: REAR == FRONT; empty: (REAR+1) mod n == FRONT
  4. Full: (FRONT+1) mod n == REAR; empty: REAR == FRONT

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Full: (REAR+1) mod n == FRONT; empty: REAR == FRONT

Explanation

One slot is deliberately unused to distinguish full from empty. Empty has matching indices. Full occurs when advancing REAR one position would reach FRONT and consume that reserved slot. Therefore full is (REAR+1) mod n==FRONT and empty is REAR==FRONT, A.

More Stacks and Queues questions

All Stacks and Queues questions →