Insertion in Circular Queue
Data Structures
Name: [Your Name]
USN: [Your USN]
Subject: Data Structures
What is a Circular Queue?
"Circular" Nature
It's called circular because elements are added and removed in a
circular fashion, reusing space at the front once elements are
Definition dequeued.
A linear data structure that operates on a FIFO (First-In, First-
Out) principle, but with the last position connected back to the
first. Front & Rear
The Front pointer indicates the position of the first element,
while Rear points to the last element inserted.
Why Circular Queue over Linear Queue?
Limitations of Linear Queue Circular Queue Solution
Linear queues suffer from inefficient memory utilization. Even after dequeuing By connecting the rear to the front, the circular queue reuses the vacated spaces.
elements, the space at the front cannot be reused until the queue is completely This optimizes memory usage and prevents false "queue full" conditions, making it
empty and reset, leading to "queue full" situations when physical memory is still more efficient for continuous operations.
available.
Basic Concepts & Terminology
Front Pointer Rear Pointer
Points to the index of the first element in the queue. Increments on dequeue operation. Points to the index of the last element inserted into the queue. Increments on
enqueue operation.
Empty Condition Full Condition
The queue is empty when front == -1 (or front == rear in some The queue is full when the next position after Rear is Front, i.e., (rear + 1) % size == fron
implementations, along with other checks).
Conditions for Insertion
Before inserting a new element, we must always check the state of the queue.
Queue Full Check
The most critical condition: if (rear + 1) % size == front, the queue is full, and insertion is not poss
Initially Empty
If the queue is initially empty (front == -1), both front and rear are set to 0 for the first insertion.
General Insertion
If not full and not empty, the rear pointer is advanced using modulo arithmetic: rear =
(rear + 1) % size.
Algorithm for Insertion
Adding an element to a circular queue follows a precise sequence of steps.
01
Check for Overflow
First, verify if the queue is full. If (rear + 1) % size == front, output an "Overflow" message and exit.
02
Initialize Pointers (if empty)
If the queue was initially empty (front == -1), set both front and rear to 0.
03
Advance Rear Pointer
Update the rear pointer: rear = (rear + 1) % size. This handles wrapping around to the beginning of the array.
04
Insert Element
Place the new element at the position indicated by the updated rear pointer: queue[rear] = element.
Step-by-Step Insertion Example
Let's visualize inserting an element into a circular queue of size 5.
Before Insertion After Insertion
Queue state: [_, 'A', 'B', 'C', _]Front: 1, Rear: 3Element to insert: 'D' Check (rear+1)%size != front. Rear becomes (3+1)%5 = 4. Element 'D' is placed at index 4.
New queue state: [_, 'A', 'B', 'C', 'D']Front: 1, Rear: 4
Now, let's insert 'E' when the array is almost full and 'F' which would cause an overflow.
Inserting 'E' (Wrap-around) Queue Full Condition
Queue state: ['X', 'A', 'B', 'C', 'D']Front: 1, Rear: 0 (after some dequeues) If the queue was ['E', 'A', 'B', 'C', 'D'], with front = 1 and rear = 0, then (rear + 1) % size = (0 + 1) % 5 = 1. Since 1 == front, the queue is indeed full.
Element to insert: 'E'
Pseudocode / Code Logic
A language-independent representation of the insertion process.
Function Enqueue(queue, size, element):
If (rear + 1) % size == front:
Print "Queue Overflow: Cannot insert element"
Return
End If
If front == -1: // Queue is initially empty
front = 0
rear = 0
Else:
rear = (rear + 1) % size
End If
queue[rear] = element
Print "Element", element, "inserted successfully."
End Function
The modulo operator (%) is crucial for wrapping the rear pointer around to the beginning of the array.
Advantages of Circular Queue
Circular queues offer several benefits over their linear counterparts.
Efficient Memory Utilization
Eliminates the problem of unutilized space, ensuring that memory is fully leveraged for storage.
No Shifting Required
Unlike some data structures (e.g., arrays requiring element shifting on deletion), circular
queues only involve pointer movements, making operations faster.
Useful in Real-time Systems
Its continuous, efficient nature makes it ideal for applications where data streams need
constant processing without interruptions from memory management.
Applications & Conclusion
Circular queues are fundamental in various computing scenarios.
CPU Scheduling Buffer Management Traffic Systems
Manages processes in operating systems, ensuring Used in data buffering, where data is temporarily Models traffic flow and signal sequencing, managing
fair execution in a round-robin fashion. stored before being processed, such as in streaming vehicles efficiently in a continuous cycle.
or network protocols.
The insertion operation in a circular queue is a cornerstone of efficient data management, enabling continuous processing and optimal resource utilization in diverse computing applicati