PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q3

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Queues

Question

What are the problems with linear queue? Explain different queue operations in circular queue.

Solution

Problems with Linear Queue (Array Implementation):

  1. False Overflow / Wasted Memory: Once rear reaches MAX - 1, no more insertions are allowed (rear == MAX - 1) even if earlier dequeue() calls have freed slots at 0..front-1.
  2. Costly Shifting Workaround: Shifting all elements toward index 0 on every dequeue turns operations into .

Circular Queue Operations (Ring Buffer of Size MAX): Initially front = -1, rear = -1.

  1. isEmpty(): Returns true when front == -1.
  2. isFull(): Returns true when (rear + 1) % MAX == front.
  3. enqueue(x):
    • Check isFull(). If full, report overflow.
    • If empty (front == -1), set front = 0, rear = 0; else set rear = (rear + 1) % MAX.
    • Store Q[rear] = x.
  4. dequeue():
    • Check isEmpty(). If empty, report underflow.
    • Save val = Q[front].
    • If front == rear (last item removed), reset front = rear = -1; else set front = (front + 1) % MAX.
    • Return val.
  5. display(): Start at i = front and advance i = (i + 1) % MAX until i == rear.
Answer:

A linear queue suffers from false overflow (unusable freed slots before front) or shifting overhead. A circular queue wraps front and rear with (index + 1) % MAX, supporting isEmpty, isFull, enqueue, dequeue, and display in per operation with full slot reuse.

All past exam questions for Data Structure and Algorithms