Queues in Data Structures
A complete student guide covering concepts, types, implementations, and real-world applications of queue data structures — from simple FIFO to advanced deques and BFS algorithms.
📖Introduction to Queue Data Structure
In computer science, a queue is one of the most basic and useful data structures. It is used to store and manage data in a specific order so that tasks are processed systematically. If you imagine standing in a line at a movie ticket counter, you are already experiencing the concept of a queue. The person who arrives first gets served first, and new people join the line from the back. This exact idea is used when managing data in computer programs.
A queue is formally defined as a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element inserted into the queue is the first element removed. This simple rule makes queues extremely useful when tasks must be handled in the same order they arrive.
Queues are widely used in operating systems, network systems, scheduling algorithms, and even everyday applications like printing documents. Whenever a system needs to manage multiple tasks fairly and efficiently, queues become the ideal solution. Think about your smartphone downloading multiple files or your computer printing documents — these operations rely heavily on queue structures.
Another reason queues are important is that they provide organized and predictable data processing. Instead of randomly processing tasks, the system handles them one by one in the correct order. This ensures fairness and efficiency, especially when many users or processes are involved.
Understanding queues is essential for students studying Data Structures and Algorithms (DSA) because many advanced algorithms, operating system mechanisms, and network systems depend on this concept. Once you understand queues, you can easily learn related structures and algorithms such as BFS traversal, CPU scheduling, and task management systems.
Real-Life Example of a Queue
Queues are everywhere in real life, and recognizing them makes the concept easier to understand. Consider these everyday examples:
- Waiting line at a bank
- Queue at a movie ticket counter
- Vehicles waiting at a traffic signal
- Customers standing at a supermarket checkout
In each case, the rule is simple: first come, first served. No one jumps ahead unless there is a special priority. Computers apply the same logic — when multiple tasks need processing, the system places them in a queue and processes them one by one.
Why Queues Are Important in Computer Science
Queues help computers manage tasks effectively. Imagine if a computer tried to process all tasks randomly — it would create confusion and inefficiency. Queues solve this problem by organizing tasks in order. They help manage:
- Processes in operating systems
- Network packet handling
- Task scheduling
- Data buffering
Because of this, queues are considered one of the fundamental data structures in computer science.
🔄Queue Concept (FIFO Principle)
What is FIFO (First In First Out)?
The main principle behind queues is FIFO, which stands for First In, First Out. This means the first element added to the queue is the first element removed from it.
Think about a queue like a line of students waiting for lunch in the school cafeteria. The first student who enters the line gets food first. Students who arrive later must wait their turn. In programming, the same rule applies.
If we remove an element:
Removed → A
Remaining queue: [B, C]
This behavior ensures fairness and predictable execution order. Queues have two main ends:
Basic Operations in Queue
Queues support several important operations that allow programmers to manage data effectively.
Queue: [10, 20] → Enqueue(30) → [10, 20, 30]
Queue: [10, 20, 30] → Dequeue() → [20, 30]
Queue: [20, 30] → Peek → 20
These operations form the foundation of queue functionality and are widely used in real-world programming.
🗂️Types of Queues
Queues are not limited to just one structure. Over time, several variations have been developed to solve different problems. The four most common types are:
➡️Simple Queue (Linear Queue)
A Simple Queue, also called a Linear Queue, is the most basic form of a queue. In this structure, elements are inserted from the rear and removed from the front. It strictly follows the FIFO rule.
When an element is removed, the next element moves forward logically.
Example of Simple Queue
Imagine students submitting assignments to a teacher. Student order: Rahul → Priya → Aman → Sara. If the teacher checks assignments using a queue:
- Rahul checked first
- Priya second
- Aman third
- Sara last
The order remains exactly the same as the arrival order.
⚠️ Limitation: One limitation of a simple queue occurs when implemented using arrays. After several deletions, empty spaces may appear at the front but cannot be reused easily, leading to inefficient memory usage. This problem led to the creation of the Circular Queue.
C++ Program: Simple Queue using Array
#include <iostream>
using namespace std;
#define SIZE 5
class Queue {
int arr[SIZE];
int front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
void enqueue(int value) {
if (rear == SIZE - 1) {
cout << "Queue Overflow\n";
return;
}
if (front == -1)
front = 0;
arr[++rear] = value;
cout << value << " inserted into queue\n";
}
void dequeue() {
if (front == -1 || front > rear) {
cout << "Queue Underflow\n";
return;
}
cout << arr[front] << " removed from queue\n";
front++;
}
void display() {
if (front == -1 || front > rear) {
cout << "Queue is empty\n";
return;
}
cout << "Queue elements: ";
for (int i = front; i <= rear; i++)
cout << arr[i] << " ";
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
q.dequeue();
q.display();
return 0;
}
10 inserted into queue 20 inserted into queue 30 inserted into queue Queue elements: 10 20 30 10 removed from queue Queue elements: 20 30
Explanation
- Queue starts empty.
- Elements 10, 20, 30 are inserted.
- When we remove an element, 10 (first inserted) is removed first.
🔁Circular Queue
A Circular Queue solves the memory problem of the simple queue. In a circular queue, the last position connects back to the first position, forming a circular structure. Instead of wasting space, the queue reuses empty slots.
Positions: [0][1][2][3][4]
When the rear reaches position 4 and there is space at position 0,
the next element goes back to position 0.
Advantages of Circular Queue
- Efficient memory usage
- Faster operations
- No wasted space after deletion
- Ideal for fixed-size buffers
Because of these advantages, circular queues are commonly used in CPU scheduling, streaming data buffers, and multimedia applications.
C++ Program: Circular Queue
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
int arr[SIZE];
int front, rear;
public:
CircularQueue() {
front = -1;
rear = -1;
}
void enqueue(int value) {
if ((rear + 1) % SIZE == front) {
cout << "Queue is Full\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 is Empty\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 is empty\n";
return;
}
cout << "Queue elements: ";
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.display();
q.dequeue();
q.display();
return 0;
}
10 inserted 20 inserted 30 inserted Queue elements: 10 20 30 10 removed Queue elements: 20 30
Explanation
- Elements move in a circle.
- When the queue reaches the end, it wraps around to the beginning.
⚡Priority Queue
A Priority Queue works differently from a normal queue. Instead of processing elements based on arrival time, elements are processed based on priority level. Each element has an associated priority value.
| Task | Priority |
|---|---|
| Task A | 1 (Lowest) |
| Task B | 3 (Highest) |
| Task C | 2 (Medium) |
(Higher priority tasks are executed first)
Real-Life Example of Priority Queue
Hospitals use priority queues. Patients are treated based on urgency rather than arrival time.
- Accident patient → High priority
- Fever patient → Medium priority
- Regular checkup → Low priority
Even if a regular patient arrives first, a critical patient is treated earlier. In computing, priority queues are used in algorithms like Dijkstra's shortest path algorithm and operating system schedulers.
C++ Program: Priority Queue
#include <iostream>
using namespace std;
#define SIZE 5
class PriorityQueue {
int arr[SIZE];
int size;
public:
PriorityQueue() {
size = 0;
}
void insert(int value) {
if (size == SIZE) {
cout << "Queue Full\n";
return;
}
arr[size++] = value;
cout << value << " inserted\n";
}
void deleteHighest() {
if (size == 0) {
cout << "Queue Empty\n";
return;
}
int maxIndex = 0;
for (int i = 1; i < size; i++) {
if (arr[i] > arr[maxIndex])
maxIndex = i;
}
cout << arr[maxIndex] << " removed (highest priority)\n";
for (int i = maxIndex; i < size - 1; i++)
arr[i] = arr[i + 1];
size--;
}
void display() {
cout << "Queue elements: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
};
int main() {
PriorityQueue pq;
pq.insert(10);
pq.insert(50);
pq.insert(30);
pq.display();
pq.deleteHighest();
pq.display();
return 0;
}
10 inserted 50 inserted 30 inserted Queue elements: 10 50 30 50 removed (highest priority) Queue elements: 10 30
Explanation
- The program searches for the largest value.
- That element is removed first because it has the highest priority.
↔️Double Ended Queue (Deque)
A Deque (Double Ended Queue) allows insertion and deletion from both ends. This makes it more flexible than a regular queue.
Operations Allowed
Types of Deque
Deque is widely used in sliding window algorithms, task scheduling, and memory management systems.
C++ Program: Deque
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_front(5);
cout << "Deque elements: ";
for(int x : dq)
cout << x << " ";
cout << endl;
dq.pop_front();
dq.pop_back();
cout << "After deletion: ";
for(int x : dq)
cout << x << " ";
}
Deque elements: 5 10 20 After deletion: 10
Explanation
push_front()→ insert at frontpush_back()→ insert at rearpop_front()→ delete front elementpop_back()→ delete rear element
⚙️Implementation Methods of Queue
Queues can be implemented using different data structures. The two most common methods are Array implementation and Linked list implementation.
Array Implementation
In this method, a queue is stored inside an array. Two variables are used: Front and Rear.
Queue: [10, 20, 30, _, _]
Front = 0, Rear = 2
- Simple implementation
- Fast access
- Fixed size
- Possible memory wastage
Because of these problems, circular queues are often used instead.
Linked List Implementation
In this approach, a queue is implemented using a linked list. Each element contains data and a pointer to the next element.
- Dynamic size
- Efficient memory usage
- No overflow until memory is full
- Slightly complex implementation
- Requires pointer handling
Despite this complexity, linked lists are widely used for queues in modern systems.
C++ Program: Queue using Linked List
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
Node *front, *rear;
public:
Queue() {
front = rear = NULL;
}
void enqueue(int value) {
Node* temp = new Node();
temp->data = value;
temp->next = NULL;
if (rear == NULL) {
front = rear = temp;
}
else {
rear->next = temp;
rear = temp;
}
cout << value << " inserted\n";
}
void dequeue() {
if (front == NULL) {
cout << "Queue Empty\n";
return;
}
Node* temp = front;
cout << front->data << " removed\n";
front = front->next;
delete temp;
}
void display() {
Node* temp = front;
cout << "Queue elements: ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.display();
q.dequeue();
q.display();
}
10 inserted 20 inserted 30 inserted Queue elements: 10 20 30 10 removed Queue elements: 20 30
Explanation
- Each element is stored in a node.
- Nodes are connected using pointers.
🌐Applications of Queue
Queues are extremely useful in many real-world computing systems. They help manage tasks that need to be processed sequentially. Some important applications include:
CPU Scheduling — Example
When multiple programs are running, they cannot all use the CPU simultaneously. So the system places processes in a CPU queue.
Execution order: P1 → P2 → P3
(This ensures fairness — every process gets CPU time in order)
Printer Queue — Example
1. Report.pdf
2. Resume.docx
3. Assignment.doc
Printing order: Report → Resume → Assignment
Breadth First Search (BFS)
BFS explores nodes level by level. Steps:
- Start with the first node.
- Add it to the queue.
- Visit neighbors and add them to the queue.
- Continue until all nodes are visited.
Queue: [A]
Visit neighbors → Queue: [B, C]
Then process B, then C.
BFS is useful in: Shortest path algorithms, Network routing, Social network analysis
Queues make BFS efficient because they maintain the correct processing order.
C++ Program: BFS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> adj[5];
bool visited[5];
void bfs(int start) {
queue<int> q;
visited[start] = true;
q.push(start);
while(!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for(int neighbor : adj[node]) {
if(!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
cout << "BFS Traversal: ";
bfs(0);
}
BFS Traversal: 0 1 2 3 4
Explanation
- Start from node 0.
- Visit its neighbors 1 and 2.
- Then visit 3 and 4.
- Queue ensures nodes are processed level by level.
📊Summary Table
| Queue Type | Key Idea | Example |
|---|---|---|
| Simple Queue | FIFO order | Ticket line |
| Circular Queue | Reuses empty spaces | Circular buffer |
| Priority Queue | Highest priority first | Hospital emergency |
| Deque | Insert/Delete from both ends | Task scheduling |
Conclusion
Queues are one of the most fundamental data structures in computer science. Their simple rule — First In, First Out (FIFO) — makes them extremely useful for managing tasks in an organized and fair way. From real-world lines at supermarkets to complex operating system scheduling, the queue concept appears everywhere.
Students learning data structures should understand queues deeply because they form the foundation for many advanced algorithms and system designs. Variations like circular queues, priority queues, and deques solve different types of problems and improve performance in specialized scenarios.
Queues are used in many important applications such as CPU scheduling, printer management, and graph algorithms like BFS. Once you understand how queues work and how they are implemented, you can easily apply them to solve real programming challenges.
❓Frequently Asked Questions
- Enqueue (insert)
- Dequeue (remove)
- Peek
- IsEmpty
- IsFull
- Simple Queue
- Circular Queue
- Priority Queue
- Double Ended Queue (Deque)
- CPU scheduling
- Printer management
- Network buffering
- Graph algorithms like BFS
0 Comments
If you have any doubts, Please let me know