Queue Data Structures: Simple, Circular
Introduction
A Queue is a linear data structure that follows the First-In, First-Out (FIFO) principle similar
to a line of people waiting for service.
● Enqueue (Insertion): Always occurs at the rear end.
● Dequeue (Deletion): Always occurs at the front end.
1. Simple (Linear) Queue
Concept
A Simple Queue is the basic form, implemented using a fixed-size array.
Once elements are dequeued, their space cannot be reused, even if the array still has empty
spots.
Variables
● Front → Index of the first element.
● Rear → Index of the last element.
● Initially: Front = -1, Rear = -1.
Operation Condition/Logic Notes
Enqueue 1. Check if If full, insertion is
(Insert) Rear==MAX_SIZE−1 impossible.
(Overflow).
2. If Front==−1, set For the very first
Front=0. element.
3. Increment Rear. Rear=Rear+1
4. Add element at
Queue[Rear].
Dequeue 1. Check if Front==−1 or If empty, deletion is
(Delete) Front>Rear (Underflow). impossible.
2. Retrieve element at
Queue[Front].
3. Increment Front. Front=Front+1
4. If Front>Rear (queue Optional cleanup.
becomes empty), reset
Front=−1,Rear=−1.
Algorithm (Array Implementation)
Enqueue (Insert)
if Rear == MAX_SIZE - 1:
print("Overflow")
else:
if Front == -1:
Front = 0
Rear = Rear + 1
Queue[Rear] = item
Dequeue (Delete)
if Front == -1 or Front > Rear:
print("Underflow")
else:
item = Queue[Front]
Front = Front + 1
if Front > Rear:
Front = Rear = -1
Java Example
class SimpleQueue {
int front = -1, rear = -1;
int MAX = 5;
int[] queue = new int[MAX];
void enqueue(int x) {
if (rear == MAX - 1) [Link]("Overflow");
else {
if (front == -1) front = 0;
queue[++rear] = x;
}
}
void dequeue() {
if (front == -1 || front > rear)
[Link]("Underflow");
else {
[Link]("Removed: " + queue[front++]);
if (front > rear) front = rear = -1;
}
}
}
Example (MAX = 5)
Operation Queue State Fron Rear Note
t
Initial [,,,,] -1 -1 Empty
Enqueue(10) [10, , , , ] 0 0 First element
Dequeue() [,,,,] 1 0 Space wasted
Enqueue(20) [ , 20, , , ] 1 1 Still valid
Enqueue(50) [ , 20, 30, 40, 50 1 4 Queue full
]
Enqueue(60) Overflow! 1 4 Cannot reuse slot 0
Limitation: Space at index 0 remains unused after dequeue — causing inefficient memory
utilization.
2. Circular Queue
Concept
A Circular Queue connects the end of the array back to the start using the modulus (%)
operator, allowing space reuse.
Key Formula
● IsFull: (Rear + 1) % MAX_SIZE == Front
● Next Rear: (Rear + 1) % MAX_SIZE
● Next Front: (Front + 1) % MAX_SIZE
2. Step-by-Step Operations
Step Operation Queue State Front Rear Explanation
1 Initial [,,,,] -1 -1 Queue empty. Both pointers are
-1.
2 Enqueue(10) [10, , , , ] 0 0 First element inserted. Both
move from -1 → 0.
3 Enqueue(20) [10, 20, , , ] 0 1 Rear advances: (0 + 1)%5 = 1.
4 Enqueue(30) [10, 20, 30, , ] 0 2 Rear moves to 2.
5 Dequeue() [ , 20, 30, , ] 1 2 Element 10 removed. Front
moves forward (0 + 1)%5 = 1.
Space 0 is now free → reusable
later!
6 Enqueue(40) [ , 20, 30, 40, ] 1 3 Rear moves to 3.
7 Enqueue(50) [ , 20, 30, 40, 1 4 Rear moves to 4. Queue looks
50] full but index 0 is actually
empty.
8 Enqueue(60) [60, 20, 30, 40, 1 0 Here’s the magic: Rear wraps to
50] (4 + 1)%5 = 0 and reuses the
empty slot 0. No overflow!
9 Dequeue() [60, , 30, 40, 2 0 Front moves to (1 + 1)%5 = 2.
50] Still valid circularly.
10 Queue Full — — — If next Rear position equals
Condition Front, queue is full: (Rear +
1)%MAX == Front.
11 Queue Empty — — — When both are -1, or Front == -
Condition 1.
Enqueue (Insert)
if (Front == (Rear + 1) % MAX_SIZE):
print("Overflow")
else:
if (Front == -1):
Front = 0
Rear = (Rear + 1) % MAX_SIZE
Queue[Rear] = item
Dequeue (Delete)
if Front == -1:
print("Underflow")
else:
item = Queue[Front]
if Front == Rear:
Front = Rear = -1
else:
Front = (Front + 1) % MAX_SIZE
Java Example
class CircularQueue {
int front = -1, rear = -1;
int MAX = 5;
int[] queue = new int[MAX];
void enqueue(int x) {
if ((rear + 1) % MAX == front)
[Link]("Overflow");
else {
if (front == -1) front = 0;
rear = (rear + 1) % MAX;
queue[rear] = x;
}
}
void dequeue() {
if (front == -1)
[Link]("Underflow");
else {
[Link]("Removed: " + queue[front]);
if (front == rear) front = rear = -1;
else front = (front + 1) % MAX;
}
}
}
Example (MAX = 5) error solving
Operation Queue Front Rear Note
Enqueue(10) [10, , , , ] 0 0 Start
Dequeue() [,,,,] -1 -1 Empty again
Enqueue(20) [20, , , , ] 0 0 Reused
Enqueue(60) [ , , 40, 50, 60 ] 2 4 Wraps around
Enqueue(70) [70, , 40, 50, 60] 2 0 Space reused
Advantage: Efficient use of space; front and rear wrap around.
Summary Comparison
Feature Simple Queue Circular Queue
Insertion Rear only Rear (wraps)
Deletion Front only Front (wraps)
Memory Reuse No Yes
Example Use Printers CPU scheduling