Past exam question: 2079 Ashwin (Back), Q2(a)
Open in the Padhaiko appFor circular queue, write algorithms to implement enqueue () and dequeue () operations with all the required conditions and appropriate diagrams.
Solution
Need and Principle of Circular Queue: In a standard linear queue using an array of size , elements deleted from the front leave unused positions at the beginning. Once rear == N - 1, no new element can be inserted even if front > 0 (known as false overflow or memory wastage).
A circular queue overcomes this by logically joining the last position of the array back to the first position using modulo arithmetic:
Boundary Conditions:
- Empty Queue Condition:
front == -1(both pointers initialized to-1). - Full Queue Condition:
(rear + 1) % N == front(the position immediately followingrearisfront). - Single Element Condition:
front == rear(reset both to-1upon dequeue).
Diagrammatic Representation of Circular Queue: Consider an array of size :
Slot 0 [ 10 ] <-- front
/ \
Slot 4 [ ] Slot 1 [ 20 ]
\ /
Slot 3 [ 40 ] <-- rear Slot 2 [ 30 ]
State: front = 0, rear = 3. Elements: 10, 20, 30, 40.
Next insertion (enqueue 50) sets rear = (3 + 1) % 5 = 4.
Next insertion after that detects: (4 + 1) % 5 == 0 == front (Queue Full).Algorithm for Enqueue Operation (enqueue(element)):
Algorithm ENQUEUE(Q, N, front, rear, item):
1. [Check for Queue Overflow]
If (rear + 1) % N == front:
Print "Queue Overflow: Cannot insert"
Return
2. [Check for Empty Queue]
If front == -1:
Set front = 0
Set rear = 0
Else:
Set rear = (rear + 1) % N
3. [Insert element]
Set Q[rear] = item
Print "Item successfully enqueued"
4. ReturnAlgorithm for Dequeue Operation (dequeue()):
Algorithm DEQUEUE(Q, N, front, rear):
1. [Check for Queue Underflow]
If front == -1:
Print "Queue Underflow: Queue is empty"
Return NULL
2. [Retrieve element]
Set item = Q[front]
3. [Check if queue had only one element]
If front == rear:
Set front = -1
Set rear = -1
Else:
Set front = (front + 1) % N
4. [Return dequeued element]
Return item
Both operations execute in strictly constant time with auxiliary space.
For a circular queue of capacity with pointers front and rear:
- Full Condition:
(rear + 1) % N == front - Empty Condition:
front == -1 enqueue(x): If full, overflow; else if empty, setfront = rear = 0; elserear = (rear + 1) % N; setQ[rear] = x.dequeue(): If empty, underflow; retrieveitem = Q[front]; iffront == rear, resetfront = rear = -1; elsefront = (front + 1) % N; returnitem.