A Circular Queue is often used instead of a Simple Queue because it efficiently utilizes memory by reusing empty spaces that would otherwise remain unused in a simple queue. Here I am providing images: one for simple queue and the other for circular queue, which will explain all the differences between these terms.
Simple Queue (Enque and Dequeue)
A simple queue (also known as a linear queue) is a data structure that follows the First In, First Out (FIFO) principle.
1. Enqueue (Rear): Front Rear Movement
An element is always added to the queue at the rear (end) of the queue. Therear
pointer moves forward after each enqueue.
SimpleQueue[++rear] = value; // Add value to the queue and increment rear
Note: Ensure rear < SIZE - 1
before incrementing.
2. Dequeue (Front) : Front Pointer Movement
Removing an element from the queue is always removed from the front (start) of the queue. Thefront
pointer moves forward after each dequeue.
value = SimpleQueue[front++]; // Retrieve value from the front and increment front
Note: Ensure front <= rear
before incrementing.
Circular Queue (Enqueue and Dequeue)
A circular queue is a data structure that overcomes the limitations of a simple queue by reusing the empty spaces created by dequeuing elements. It also follows the First In, First Out (FIFO) principle. The main operations from enqueue and dequeue are given below
1. Enqueue (Rear) – Rear Pointer Movement
An element is added to the circular queue at the rear (end). The rear
pointer is updated in a circular manner by using following code
rear=(rear+1)%SIZE
If the queue is full ((rear + 1) % SIZE == front
), enqueue is not possible. Space is reused by wrapping around to the start of the queue when the end is reached.
2. Dequeue (Front) – Front Pointer Movement
An element is removed from the circular queue at the front (start). The front
pointer is updated in a circular manner:
front=(front+1)%SIZE
If the queue becomes empty (front == rear
after a dequeue), both pointers (front
and rear
) are reset to -1
. Dequeued spaces can be reused for new elements.
The key difference between a simple queue and a circular queue
A simple queue is straightforward but wastes memory after dequeues, while a circular queue is more space-efficient and reuses previously dequeued spaces by wrapping around. Let’s explain major terms one by one
1. Memory Utilization
Simple Queue:
- When elements are dequeued, the
front
pointer moves forward, but the memory occupied by dequeued elements is not reused. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After 3 dequeues:front
is at index 3. The queue looks like this:
[_, _, _, 30, 23, 56]
(where_
represents empty space).
Even though there are 3 spaces available at the beginning, new elements cannot be enqueued unless the queue is reset or resized.
Circular Queue:
- In a circular queue, when the
rear
pointer reaches the end of the array, it wraps around to the beginning if space is available. This ensures efficient memory utilization. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After 1 dequeue:front
moves forward to index 1, leaving one space at the start. When a new element is enqueued, the queue looks like this:
[0, 80, 11, 30, 23, 56]
(where70
is added at the beginning).
2. Queue Full Condition
Simple Queue:
- The queue is considered full when the
rear
pointer reaches the last position (SIZE - 1
), even if there is space at the beginning due to dequeues. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After dequeuing8
and80
:
[_, _, 11, 30, 23, 56]
Even though there are two empty spaces, the queue is full whenrear == SIZE - 1
.
Circular Queue:
- The queue is full when
(rear + 1) % SIZE == front
, ensuring that all available space is used. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After dequeuing8
, and enqueueing 228:
[228, 80, 11, 30, 23, 56]
The queue is now full, utilizing all positions.
3. Queue Empty Condition
Simple Queue:
- The queue is empty when
front > rear
. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After dequeuing all elements:
[_, _, _, _, _, _]
(front > rear), the queue is empty.
Circular Queue:
- The queue is empty when
front == -1
(initial state) orfront == rear
after dequeues. - For example:
Initial Queue:[8, 80, 11, 30, 23, 56]
After dequeuing all elements:
[_, _, _, _, _, _]
(front == rear), the queue is empty.
4. Front and Rear Movement
Simple Queue:
- The
front
andrear
pointers move forward only. - When the
rear
reaches the last position, no new elements can be added without resetting or resizing the queue.
Circular Queue:
- The
front
andrear
pointers move in a circular manner using modulo-arithmetic- front=(front+1)%SIZE
- rear=(rear+1)%SIZE
- This allows the queue to wrap around and efficiently reuse spaces.
5. Applications
Simple queues fit scenarios where tasks or processes are handled sequentially in a first-come, first-served manner. Applications of Simple Queue are
- Task scheduling in operating systems (e.g., process scheduling).
- Managing print jobs in printer queues.
- Customer service systems like ticket or call queues.
- Breadth-First Search (BFS) for graph traversal.
- Simulating resource allocation in systems.
Circular queues are ideal for scenarios requiring efficient memory utilization and cyclic or repeated processing of tasks. Applications of circular Queue are
- Efficient data buffering for audio or video streams.
- Round-robin scheduling in operating systems.
- Managing cyclic operations in traffic light control systems.
- Networking for buffering packets in routers or switches.
- Thread-safe circular buffers for multithreading.
6. Performance (Time Complexity)
- Simple Queue:
- To reuse space, elements may need to be shifted after dequeuing, which adds time complexity (
O(n)
for shifting).
- To reuse space, elements may need to be shifted after dequeuing, which adds time complexity (
- Circular Queue:
- Both enqueue and dequeue operations have constant time complexity (
O(1)
) because no shifting is required.
- Both enqueue and dequeue operations have constant time complexity (
Comparison Table: Simple Queue vs Circular Queue
This table summarizes the major differences between Simple Queue vs Circular Queue and highlights where each type of queue is suitable.
Aspect | Simple Queue | Circular Queue |
---|---|---|
Memory Utilization | Dequeued spaces are not reused; memory is wasted. | Efficiently reuses memory by wrapping around using modulo arithmetic. |
Queue Full Condition | Full when rear == SIZE - 1 , even if space exists at the start. |
Full when (rear + 1) % SIZE == front , ensuring all spaces are utilized. |
Queue Empty Condition | Empty when front > rear . |
Empty when front == -1 (initial state) or front == rear . |
Front and Rear Movement | Front and rear move forward only. Resizing or resetting needed to add new elements when the rear reaches the end. | Front and rear move circularly using (index + 1) % SIZE , allowing continuous use of all available spaces. |
Applications | Sequential task handling (e.g., scheduling, BFS, print queues). | Efficient cyclic task handling (e.g., buffering, round-robin scheduling, networking). |
Performance | May require shifting elements to reuse space, leading to O(n) time complexity in some cases. | Enqueue and dequeue operations are always O(1) as no shifting is required. |
Conclusion:
A Circular Queue is preferred over a Simple Queue because it:
- Prevents memory wastage.
- Provides better performance for fixed-size arrays.
- Is ideal for real-time and cyclic processes.
A Simple Queue is only sufficient for small-scale or non-continuous applications where memory efficiency is not a priority.