Past exam question: 2063 Baishakh (Regular / Back), Q1
Open in the Padhaiko appQuestion
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:
- Queue Empty Condition:
front == -1 - Queue Full Condition:
(rear + 1) % MAX == front
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 valAnswer:
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.