Scribd
Upload
5 views3 pages

Queue, Circular Queue

A Queue is a linear data structure that operates on the FIFO principle, allowing elements to be added at the rear and removed from the front. Simple queues can waste memory due to fixed array sizes, leading to the development of Circular Queues that efficiently utilize memory by wrapping around. Circular Queues are particularly useful in real-time systems and fixed-size buffer management, preventing overflow and underflow issues.

Uploaded by

The Legendary
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views3 pages

Queue, Circular Queue

A Queue is a linear data structure that operates on the FIFO principle, allowing elements to be added at the rear and removed from the front. Simple queues can waste memory due to fixed array sizes, leading to the development of Circular Queues that efficiently utilize memory by wrapping around. Circular Queues are particularly useful in real-time systems and fixed-size buffer management, preventing overflow and underflow issues.

Uploaded by

The Legendary
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First-In First-Out) principle.

●​ Enqueue → Insert element at the rear


●​ Dequeue → Remove element from the front

Queue Illustration
Front → [10, 20, 30, 40] → Rear

Simple (Linear) Queue


A simple queue is implemented using a linear array with two pointers:

●​ front
●​ rear

Problems with Linear Queue


A simple array-based queue may cause wasted memory:
Example workflow in an array of size 5:
Initial: [_, _, _, _, _] front=0, rear=-1
Enqueue 5 elements → full
Dequeue 3 elements
Array: [_, _, _, A4, A5]
front=3, rear=4

Even though the first two indices are empty, enqueue is not possible because rear = n−1.
This leads to the need for a Circular Queue.

Pseudocode for Simple Queue (Linear Array)

Enqueue
if rear == size-1:
print "Queue Overflow"
else:
if front == -1:
front = 0
rear = rear + 1
Q[rear] = value
Dequeue
if front == -1 or front > rear:
print "Queue Underflow"
else:
value = Q[front]
front = front + 1

Circular Queue
A Circular Queue solves the memory-waste problem by connecting the last position
back to the first.
Illustration:
Index: 0 1 2 3 4
Queue: A B C _ _
front=0, rear=2

After 2 dequeues:
Queue: _ _ C _ _
front=2, rear=2

Now enqueue:
Place at index 0 (wrap around!)

Why Are Circular Queues Needed?

1.​ Efficient Memory Utilization​


​ ​ No wasted spaces due to dequeue operations.
2.​ Useful in Real-Time Systems
○​ CPU scheduling
○​ Network buffers
○​ Hardware interrupts
3.​ Fixed-size buffer management​
​ ​ Perfect for embedded or hardware-based systems.
Circular Queue Pseudocode

Enqueue
if (front == 0 and rear == size-1) OR (rear + 1 == front):
print "Queue Overflow"
else:
if front == -1:
front = rear = 0
else:
rear = (rear + 1) % size
Q[rear] = value

Dequeue
if front == -1:
print "Queue Underflow"
else:
value = Q[front]
if front == rear:
front = rear = -1
else:
front = (front + 1) % size

Time & Space Complexity Analysis

You might also like