- 2070 Magh · 5 marks
Circular queue algorithm with conditions
Short answer
A circular queue uses an array, empty when front==-1, full when (rear+1)%N==front. Insertion: if not full increment rear modulo N and store. Deletion: if not empty retrieve front, increment front modulo N, reset both to -1 if last element removed.
Write an algorithm to implement circular queue with the condition for insertion, deletion, queue full and queue empty.
A circular queue stores items in an array CQ[0..N-1] and uses (index + 1) % N so that the position after N − 1 is 0.
Conditions
| Condition | Test |
|---|---|
| Initially empty | front = rear = -1 |
| Queue empty | front == -1 |
| Queue full | (rear + 1) % N == front |
| Insertion allowed | queue not full |
| Deletion allowed | queue not empty |
| Exactly one element | front == rear (after deleting it, reset both to −1) |
Algorithm for insertion
ENQUEUE(CQ, x)
1. if (rear + 1) % N == front: print "Queue full"; return
2. if front == -1: front = 0; rear = 0
else rear = (rear + 1) % N
3. CQ[rear] = x
Algorithm for deletion
DEQUEUE(CQ)
1. if front == -1: print "Queue empty"; return
2. x = CQ[front]
3. if front == rear: front = -1; rear = -1
else front = (front + 1) % N
4. return x
Example (N = 4)
| Operation | Array contents (index 0 → N-1) | front | rear |
|---|---|---|---|
| enqueue(1) | 1 _ _ _ | 0 | 0 |
| enqueue(2) | 1 2 _ _ | 0 | 1 |
| enqueue(3) | 1 2 3 _ | 0 | 2 |
| enqueue(4) | 1 2 3 4 | 0 | 3 |
| enqueue(5): (rear+1)%4 = 0 = front → Queue overflow | 1 2 3 4 | 0 | 3 |
| dequeue() returns 1 | _ 2 3 4 | 1 | 3 |
| enqueue(5) | 5 2 3 4 | 1 | 0 |
| dequeue() returns 2 | 5 _ 3 4 | 2 | 0 |
| dequeue() returns 3 | 5 _ _ 4 | 3 | 0 |
| dequeue() returns 4 | 5 _ _ _ | 0 | 0 |
| dequeue() returns 5 | _ _ _ _ | -1 | -1 |
| dequeue(): Queue underflow | _ _ _ _ | -1 | -1 |
All N cells can be used, and the wrap-around of rear shows the circular behaviour.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Insertion and deletion in array list · Data Structure and Algorithm, chapter 3
- Enqueue and dequeue in circular queue · Data Structure and Algorithm, chapter 2 · asked 2×
- Circular queue using linked list · Data Structure and Algorithm, chapter 4
- Circular queue vs linear queue · Data Structure and Algorithm, chapter 2
- Circular queue with display operation · Data Structure and Algorithm, chapter 2
- Linear and circular queue operations · Data Structure and Algorithm, chapter 2
- Circular sewer just full, 1.6 m³/s · Sanitary Engineering, chapter 3
- Race condition example; Peterson's algorithm · Operating System, chapter 3
- Insertion loss design of given LC ladder filter · RF and Microwave Engineering, chapter 6