Data Structures: Queue to Circular Queue
Complete Beginner's Guide
III. Queue
📦 Queue as Abstract Data Type (ADT)
Definition: A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
Real-life example: Think of people standing in line for movie tickets. The person who came first gets
served first.
Show Image
Basic Operations:
Operation Description
Enqueue Add an element to the rear/back
Dequeue Remove an element from the front
Front Get the front element without removing
IsEmpty Check if queue is empty
IsFull Check if queue is full
🔢 Array Implementation of Queue
In this implementation, we will use an array to store queue elements. We'll need to keep track of both the
front and rear indices.
c
#include <stdio.h>
#define MAX 5 // Maximum size of queue
// Global variables
int queue[MAX]; // Array to store queue elements
int front = -1; // Index of front element
int rear = -1; // Index of rear element
// Function to check if queue is full
int isFull() {
if (rear == MAX - 1) { // If rear is at the last index
return 1; // Return true (queue is full)
} else {
return 0; // Return false (queue is not full)
}
}
// Function to check if queue is empty
int isEmpty() {
if (front == -1 || front > rear) { // If front is -1 or has crossed rear
return 1; // Return true (queue is empty)
} else {
return 0; // Return false (queue is not empty)
}
}
// Function to add an element to the queue
void enqueue(int item) {
if (isFull()) { // Check if queue is full
printf("Queue Overflow\n"); // Print error message
} else {
if (front == -1) { // If queue was empty
front = 0; // Set front to the first position
}
rear++; // Increment rear
queue[rear] = item; // Place the item at rear position
printf("%d enqueued to queue\n", item);
}
}
// Function to remove an element from the queue
int dequeue() {
if (isEmpty()) { // Check if queue is empty
printf("Queue Underflow\n"); // Print error message
return -1; // Return error value
} else {
int item = queue[front]; // Get the front item
front++; // Increment front
if (front > rear) { // If the last item was dequeued
front = rear = -1; // Reset front and rear
}
return item; // Return the item
}
}
// Function to get the front element without removing it
int getFront() {
if (isEmpty()) { // Check if queue is empty
printf("Queue is empty\n"); // Print error message
return -1; // Return error value
} else {
return queue[front]; // Return the front item
}
}
// Sample usage
int main() {
enqueue(10); // Add 10 to queue
enqueue(20); // Add 20 to queue
enqueue(30); // Add 30 to queue
printf("Front element: %d\n", getFront()); // Should print 10
printf("Dequeued: %d\n", dequeue()); // Should print 10
printf("Dequeued: %d\n", dequeue()); // Should print 20
printf("Front element after dequeues: %d\n", getFront()); // Should print 30
return 0;
}
Step-by-Step Algorithm Explanation:
1. Initialize the queue:
Create an array of fixed size MAX
Set front and rear to -1 (indicating empty queue)
2. isEmpty() function:
Returns true if front is -1 (queue never started) or front > rear (all elements dequeued)
Otherwise returns false
3. isFull() function:
Returns true if rear == MAX-1 (last position filled)
Otherwise returns false
4. enqueue() function:
Check if queue is full
If full, display overflow message
If not full:
If queue was empty (front == -1), set front to 0
Increment rear
Place the item at rear position
5. dequeue() function:
Check if queue is empty
If empty, display underflow message and return error value
If not empty:
Get the item at front position
Increment front
If front crosses rear (last item dequeued), reset front and rear to -1
Return the item
6. getFront() function:
Check if queue is empty
If empty, display error message and return error value
If not empty, return the item at front position
Memory Visualization:
Let's visualize a queue with MAX = 5 after adding some elements:
After enqueue(10), enqueue(20), enqueue(30):
Array: [10, 20, 30, _, _]
Indices: 0 1 2 3 4
↑ ↑
front rear
After dequeue() (removes 10):
Array: [10, 20, 30, _, _]
Indices: 0 1 2 3 4
↑ ↑
front rear
❓ Q&A for Queue
Q1: What is a Queue?
A: A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the element
that is inserted first will be the first one to be removed.
Q2: What are the main operations of a Queue?
A: The main operations are:
Enqueue: Add an element to the rear of the queue
Dequeue: Remove an element from the front of the queue
Front/Peek: View the front element without removing it
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full (in case of array implementation)
Q3: What is the difference between Stack and Queue?
A: A Stack follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be
removed. A Queue follows the First-In-First-Out (FIFO) principle, where the first element added is the first
one to be removed.
Q4: What are the real-life applications of Queue?
A: Real-life applications include:
Waiting lines at ticket counters, grocery stores, etc.
Print job scheduling in printers
CPU task scheduling
Call center phone systems
Traffic management
Q5: What are the limitations of array implementation of Queue?
A: The main limitations are:
Fixed size (cannot grow dynamically)
Inefficient space utilization (after some dequeue operations, the front moves ahead leaving unused
space at the beginning)
Q6: How can we solve the space utilization problem in Queue?
A: We can solve it by using a Circular Queue implementation, which reuses the space at the beginning after
dequeue operations.
🔄 Problems with Simple Queue
The array implementation of a queue has a significant drawback: inefficient space utilization.
The Problem:
1. As we dequeue elements, the front index moves forward.
2. Even if we dequeue all elements, we cannot add more than MAX - front elements.
3. The space at the beginning of the array (from index 0 to front-1) remains unused.
Illustration:
Initial state:
Array: [10, 20, 30, 40, 50]
Indices: 0 1 2 3 4
↑ ↑
front rear
After dequeue() twice (removing 10 and 20):
Array: [10, 20, 30, 40, 50]
Indices: 0 1 2 3 4
↑ ↑
front rear
Now, if we try to enqueue a new element, we'll get "Queue Overflow" even though there are two unused
spaces at the beginning!
Solution:
1. Reset front and rear to -1 when the queue becomes empty.
2. Use a Circular Queue implementation to reuse the space.
🔄 Circular Queue Concept
A Circular Queue is an enhanced version of a regular queue that solves the problem of inefficient space
utilization.
Definition: A Circular Queue is a linear data structure in which operations are performed based on FIFO
principle and the last position is connected back to the first position to make a circle.
How it works:
1. When we reach the end of the array, we wrap around to the beginning.
2. We use modulo arithmetic ( % ) to implement this circular behavior.
Visualization:
front
↓
[10] [20] [30]
↑ ↑
rear → [50] [40] ← items
In this circular arrangement, after element 50, the next element would be at position 0 (making it circular).
🔢 Array Implementation of Circular Queue
Here's how to implement a Circular Queue using an array:
c
#include <stdio.h>
#define MAX 5 // Maximum size of circular queue
// Global variables
int cqueue[MAX]; // Array to store circular queue elements
int front = -1; // Index of front element
int rear = -1; // Index of rear element
// Function to check if circular queue is full
int isFull() {
if ((front == 0 && rear == MAX - 1) || (front == rear + 1)) {
return 1; // Return true (queue is full)
} else {
return 0; // Return false (queue is not full)
}
}
// Function to check if circular queue is empty
int isEmpty() {
if (front == -1) { // If front is -1
return 1; // Return true (queue is empty)
} else {
return 0; // Return false (queue is not empty)
}
}
// Function to add an element to the circular queue
void enqueue(int item) {
if (isFull()) { // Check if queue is full
printf("Circular Queue Overflow\n"); // Print error message
} else {
if (front == -1) { // If queue was empty
front = 0; // Set front to the first position
}
rear = (rear + 1) % MAX; // Increment rear in circular manner
cqueue[rear] = item; // Place the item at rear position
printf("%d enqueued to circular queue\n", item);
}
}
// Function to remove an element from the circular queue
int dequeue() {
if (isEmpty()) { // Check if queue is empty
printf("Circular Queue Underflow\n"); // Print error message
return -1; // Return error value
} else {
int item = cqueue[front]; // Get the front item
if (front == rear) { // If the last item was dequeued
front = rear = -1; // Reset front and rear
} else {
front = (front + 1) % MAX; // Increment front in circular manner
}
return item; // Return the item
}
}
// Function to get the front element without removing it
int getFront() {
if (isEmpty()) { // Check if queue is empty
printf("Circular Queue is empty\n"); // Print error message
return -1; // Return error value
} else {
return cqueue[front]; // Return the front item
}
}
// Sample usage
int main() {
enqueue(10); // Add 10 to queue
enqueue(20); // Add 20 to queue
enqueue(30); // Add 30 to queue
enqueue(40); // Add 40 to queue
printf("Front element: %d\n", getFront()); // Should print 10
printf("Dequeued: %d\n", dequeue()); // Should print 10
printf("Dequeued: %d\n", dequeue()); // Should print 20
// Now we can add more elements even though the array is "full"
enqueue(50); // Add 50 to queue
enqueue(60); // Add 60 to queue
printf("Front element after changes: %d\n", getFront()); // Should print 30
return 0;
}
Key Differences from Regular Queue:
1. The isFull() condition is different:
A circular queue is full when front == 0 && rear == MAX-1 (regular wraparound hasn't
occurred)
OR when front == rear + 1 (wraparound has occurred)
2. Circular increment using modulo:
rear = (rear + 1) % MAX
front = (front + 1) % MAX
Step-by-Step Algorithm Explanation:
1. Initialize the circular queue:
Create an array of fixed size MAX
Set front and rear to -1 (indicating empty queue)
2. isEmpty() function:
Returns true if front is -1 (queue never started)
Otherwise returns false
3. isFull() function:
Returns true if front is at position 0 AND rear is at last position (MAX-1)
OR if front is exactly one position ahead of rear (wrapped around)
Otherwise returns false
4. enqueue() function:
Check if queue is full
If full, display overflow message
If not full:
If queue was empty (front == -1), set front to 0
Update rear = (rear + 1) % MAX (circular increment)
Place the item at rear position
5. dequeue() function:
Check if queue is empty
If empty, display underflow message and return error value
If not empty:
Get the item at front position
If front equals rear (last item), reset front and rear to -1
Otherwise, update front = (front + 1) % MAX (circular increment)
Return the item
6. getFront() function:
Check if queue is empty
If empty, display error message and return error value
If not empty, return the item at front position
Memory Visualization:
Let's visualize a circular queue with MAX = 5:
Initial state (empty):
Array: [_, _, _, _, _]
Indices: 0 1 2 3 4
front = -1, rear = -1
After enqueue(10), enqueue(20), enqueue(30):
Array: [10, 20, 30, _, _]
Indices: 0 1 2 3 4
↑ ↑
front rear
After dequeue() twice (removes 10, 20):
Array: [10, 20, 30, _, _]
Indices: 0 1 2 3 4
↑
front
↑
rear
After enqueue(40), enqueue(50):
Array: [10, 20, 30, 40, 50]
Indices: 0 1 2 3 4
↑ ↑
front rear
After dequeue() twice (removes 30, 40) and enqueue(60):
Array: [60, 20, 30, 40, 50]
Indices: 0 1 2 3 4
↑ ↑
rear front
Notice how we're reusing the space at index 0!
❓ Q&A for Circular Queue
Q1: What is a Circular Queue?
A: A Circular Queue is a linear data structure that follows the FIFO principle and connects the last position to
the first position to form a circle, allowing better memory utilization by reusing the empty spaces.
Q2: What problem does a Circular Queue solve?
A: Circular Queue solves the problem of inefficient space utilization in a regular queue implementation. In a
regular queue, after dequeuing elements, the space at the beginning cannot be reused without resetting the
entire queue, while a Circular Queue allows reusing those spaces.
Q3: How does a Circular Queue detect if it's full?
A: A Circular Queue is full when:
Front is at position 0 and rear is at the last position (MAX-1), OR
Front is exactly one position ahead of rear (front == rear + 1)
Q4: How does a Circular Queue implement "wrapping around"?
A: Circular Queue implements wrapping around using the modulo operator (%). When incrementing front
or rear, it uses (index + 1) % MAX which makes the index go back to 0 after reaching MAX-1.
Q5: What are the real-life applications of Circular Queue?
A: Real-life applications include:
CPU scheduling
Memory management
Traffic system management
Data streaming (like buffering in media players)
Round-robin scheduling algorithm
Q6: What is the difference between enqueue operation in regular Queue and Circular Queue?
A: In a regular Queue, the enqueue operation simply increments the rear index (rear++), while in a Circular
Queue, it uses modulo arithmetic to wrap around: rear = (rear + 1) % MAX .
Q7: What are the advantages of Circular Queue over regular Queue?
A: Advantages include:
Better memory utilization (reuses empty spaces)
No need to shift elements
Can operate indefinitely within its fixed size
More efficient for applications that require continuous queue operations
Q8: Can a Circular Queue become full even if there are empty spaces?
A: No, that's the main advantage of a Circular Queue. It can detect and utilize any empty spaces, becoming
full only when all spaces are actually occupied.
