Circular Queue and Priority Queue in Data Structures (C++ Implementation Guide)
Queues are one of the most fundamental linear data structures used in computer science and software engineering. From operating system process scheduling to network packet routing, queues play a critical role in managing data efficiently.
A traditional queue follows the FIFO (First In, First Out) principle, meaning the element inserted first will be removed first. However, basic queue implementations sometimes lead to inefficient memory usage and slow operations. To overcome these limitations, advanced queue types such as Circular Queue and Priority Queue were introduced.
In this comprehensive guide, you will learn:
-
What a Circular Queue is
-
How Priority Queues work
-
Static and Dynamic implementations of both queues
-
Insertion and deletion operations
-
C++ code examples for practical understanding
-
Real-world applications in computing systems
This article is particularly useful for computer science students, programmers, and software engineers preparing for technical interviews or studying data structures and algorithms.
Understanding Queue in Data Structures
Before diving into circular and priority queues, it is important to understand the concept of a queue.
A queue is a linear data structure that follows the FIFO rule. Elements are inserted from one end called the rear, and removed from the other end called the front.
Basic Queue Operations
The primary operations of a queue include:
Enqueue
Insertion of an element into the queue.
Dequeue
Removal of an element from the queue.
Peek / Front
Retrieves the first element without removing it.
IsEmpty
Checks whether the queue contains elements.
IsFull
Checks whether the queue is full (in array implementation).
Queues are widely used in task scheduling, buffering systems, printer spooling, and asynchronous data processing.
However, the traditional queue implemented using arrays can suffer from memory wastage, which leads to the concept of the Circular Queue.
Circular Queue in Data Structures
A Circular Queue is an advanced form of queue where the last position of the queue is connected back to the first position, forming a circular structure.
Instead of leaving unused memory spaces after deletions, a circular queue reuses freed positions, making it much more memory efficient.
Why Circular Queue is Needed
In a normal queue implemented with arrays:
-
Elements are inserted from the rear.
-
Elements are deleted from the front.
-
When elements are removed, empty spaces appear at the beginning of the array.
Even though there is free space, the queue may still report overflow because the rear has reached the last index.
Circular queue solves this problem by wrapping around the array.
Circular Queue Working Principle
The key idea behind circular queues is the modulo operator.
When the rear pointer reaches the end of the array, it moves back to the beginning.
Rear movement formula: Rear = (Rear + 1) % Size
Front movement formula: Front = (Front + 1) % Size
This circular movement allows the queue to reuse available memory efficiently.
Circular Queue Static Implementation in C++
Static implementation uses a fixed-size array.
Circular Queue C++ Code
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
private:
int arr[SIZE];
int front;
int rear;
public:
CircularQueue() {
front = -1;
rear = -1;
}
void enqueue(int value) {
if ((rear + 1) % SIZE == front) {
cout << "Queue Overflow\n";
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
arr[rear] = value;
cout << value << " inserted\n";
}
void dequeue() {
if (front == -1) {
cout << "Queue Underflow\n";
return;
}
cout << arr[front] << " removed\n";
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
}
void display() {
if (front == -1) {
cout << "Queue Empty\n";
return;
}
int i = front;
while (true) {
cout << arr[i] << " ";
if (i == rear)
break;
i = (i + 1) % SIZE;
}
cout << endl;
}
};
int main() {
CircularQueue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.enqueue(40);
q.display();
q.dequeue();
q.dequeue();
q.display();
return 0;
}
Circular Queue – Dynamic Implementation (Linked List)
Dynamic implementation uses linked lists, meaning the queue size can grow dynamically.
C++ Implementation
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class CircularQueue {
private:
Node *front, *rear;
public:
CircularQueue() {
front = rear = NULL;
}
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
if (front == NULL) {
front = rear = newNode;
rear->next = front;
} else {
rear->next = newNode;
rear = newNode;
rear->next = front;
}
cout << value << " inserted\n";
}
void dequeue() {
if (front == NULL) {
cout << "Queue Empty\n";
return;
}
int value = front->data;
if (front == rear) {
front = rear = NULL;
} else {
Node* temp = front;
front = front->next;
rear->next = front;
delete temp;
}
cout << value << " deleted\n";
}
void display() {
if (front == NULL) {
cout << "Queue Empty\n";
return;
}
Node* temp = front;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != front);
cout << endl;
}
};
int main() {
CircularQueue q;
q.enqueue(5);
q.enqueue(15);
q.enqueue(25);
q.display();
q.dequeue();
q.display();
}
Priority Queue
What is a Priority Queue?
A Priority Queue is a special type of queue where each element has a priority value.
Elements with higher priority are removed first, regardless of insertion order.
Key Principle
Higher Priority → Served First
Real-Life Examples of Priority Queue
1. Hospital Emergency Room
Patients with critical conditions are treated first.
2. Operating System Scheduling
High priority processes are executed before low priority tasks.
3. Network Packet Routing
Important data packets are transmitted first.
4. Airline Check-in Systems
Business class passengers are served before economy.
Priority Queue – Static Implementation (Array)
C++ Code
#include <iostream>
using namespace std;
#define SIZE 5
class PriorityQueue {
private:
int queue[SIZE];
int n;
public:
PriorityQueue() {
n = 0;
}
void insert(int value) {
if (n == SIZE) {
cout << "Queue Full\n";
return;
}
int i = n - 1;
while (i >= 0 && queue[i] > value) {
queue[i + 1] = queue[i];
i--;
}
queue[i + 1] = value;
n++;
cout << value << " inserted\n";
}
void deleteElement() {
if (n == 0) {
cout << "Queue Empty\n";
return;
}
cout << queue[0] << " deleted\n";
for (int i = 1; i < n; i++)
queue[i - 1] = queue[i];
n--;
}
void display() {
for (int i = 0; i < n; i++)
cout << queue[i] << " ";
cout << endl;
}
};
int main() {
PriorityQueue pq;
pq.insert(30);
pq.insert(10);
pq.insert(50);
pq.insert(20);
pq.display();
pq.deleteElement();
pq.display();
return 0;
}
Priority Queue – Dynamic Implementation (Linked List)
C++ Code
#include <iostream>
using namespace std;
struct Node {
int data;
int priority;
Node* next;
};
class PriorityQueue {
private:
Node* front;
public:
PriorityQueue() {
front = NULL;
}
void insert(int value, int priority) {
Node* newNode = new Node();
newNode->data = value;
newNode->priority = priority;
if (front == NULL || priority < front->priority) {
newNode->next = front;
front = newNode;
} else {
Node* temp = front;
while (temp->next != NULL && temp->next->priority <= priority)
temp = temp->next;
newNode->next = temp->next;
temp->next = newNode;
}
cout << "Inserted: " << value << endl;
}
void deleteElement() {
if (front == NULL) {
cout << "Queue Empty\n";
return;
}
Node* temp = front;
cout << "Deleted: " << front->data << endl;
front = front->next;
delete temp;
}
void display() {
Node* temp = front;
while (temp != NULL) {
cout << temp->data << "(P=" << temp->priority << ") ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
PriorityQueue pq;
pq.insert(100, 2);
pq.insert(200, 1);
pq.insert(300, 3);
pq.display();
pq.deleteElement();
pq.display();
}
Applications of Circular Queue and Priority Queue
Applications of Circular Queue
| Application | Description |
|---|---|
| CPU Scheduling | Used in Round Robin algorithm |
| Traffic Signal Systems | Timed circular scheduling |
| Multimedia Streaming | Continuous data buffering |
| Keyboard Buffers | Stores typed characters |
Applications of Priority Queue
| Application | Description |
|---|---|
| Operating Systems | Process scheduling |
| Artificial Intelligence | Pathfinding algorithms |
| Network Routing | Packet prioritization |
| Event Simulation | Event-driven systems |
| Dijkstra Algorithm | Shortest path calculation |
Circular Queue vs Priority Queue
| Feature | Circular Queue | Priority Queue |
|---|---|---|
| Principle | FIFO | Priority-based |
| Order | Insertion order | Priority order |
| Implementation | Array or Linked List | Array, Linked List, Heap |
| Memory Usage | Efficient (wrap-around) | Depends on structure |
| Example | CPU time-sharing | Emergency patient handling |
Advantages
Circular Queue
-
Efficient memory utilization
-
Avoids shifting operations
-
Faster insertion/deletion
Priority Queue
-
Processes important tasks first
-
Efficient task scheduling
-
Essential for algorithm design
Conclusion
Both Circular Queue and Priority Queue play a crucial role in modern computing systems. Circular queues optimize memory utilization by reusing empty spaces, while priority queues ensure that critical tasks are handled first.
From operating systems scheduling and networking to hospital management systems and artificial intelligence algorithms, these queue structures power many real-world applications.
Understanding their static and dynamic implementations in C++ enables developers and computer science students to design efficient, scalable, and optimized systems.
