PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q1

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Queues

Question

What is circular queue? Write an algorithm to implement circular queue with the condition for the queue full and empty.

Solution

Definition of Circular Queue: A circular queue is a linear FIFO queue implemented in a fixed-size array Q[0..MAX-1] treated logically as a ring: when rear or front reaches MAX - 1, advancing it wraps around to index 0 via (index + 1) % MAX, eliminating false overflow.

Full/Empty Conditions and Enqueue/Dequeue Algorithms: With front = -1, rear = -1 initially:

Algorithm CQ_ENQUEUE(Q, val):
1. If (rear + 1) % MAX == front:
       Print "Circular Queue Overflow"
       Return
2. If front == -1:
       front = 0; rear = 0
   Else:
       rear = (rear + 1) % MAX
3. Q[rear] = val

Algorithm CQ_DEQUEUE(Q):
1. If front == -1:
       Print "Circular Queue Underflow"
       Return -1
2. val = Q[front]
3. If front == rear:
       front = -1; rear = -1
   Else:
       front = (front + 1) % MAX
4. Return val
Answer:

A circular queue wraps array indices modulo MAX to reuse freed front slots, using front == -1 for empty and (rear + 1) % MAX == front for full.

All past exam questions for Data Structure and Algorithms