PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q2(a)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Queues

Question

For 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:

  1. Empty Queue Condition: front == -1 (both pointers initialized to -1).
  2. Full Queue Condition: (rear + 1) % N == front (the position immediately following rear is front).
  3. Single Element Condition: front == rear (reset both to -1 upon 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. Return

Algorithm 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.

Answer:

For a circular queue of capacity with pointers front and rear:

All past exam questions for Data Structure and Algorithms