Published: December 13, 2024
Reading Time: 6 minutes
Queue is a data structure that follows the First In, First Out (FIFO) principle. It is commonly used in various applications like task scheduling, resource management, and buffering. While there are multiple ways to implement a queue, one of the most efficient methods is by using a linked list.
A queue using a linked list is a dynamic implementation of a queue where elements are linked using pointers rather than relying on a fixed-size array. This approach offers numerous advantages, such as flexibility and ease of memory management, especially when the size of the queue is not known in advance.
A linked list is ideal for implementing the queue due to its dynamic size and efficient operations. The time complexity is O(1) for both enqueue (insertion of an element from the back) and dequeue (removal of an element from the front).
The representation of queue using a linked list consists of nodes that contain:
For the queue, there are two pointers:
The main operations for a queue using a linked list are:
Here is the implementation of the queue using a linked list with all the operations:
#include<iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = rear = nullptr;
}
// Enqueue operation
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
// Dequeue operation
int dequeue() {
if (front == nullptr) {
cout << "Queue is empty!" << endl;
return -1;
}
Node* temp = front;
int value = front->data;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return value;
}
// Peek operation
int peek() {
if (front == nullptr) {
cout << "Queue is empty!" << endl;
return -1;
}
return front->data;
}
// Check if queue is empty
bool isEmpty() {
return front == nullptr;
}
};
int main() {
Queue q;
q.enqueue(2);
q.enqueue(5);
q.enqueue(10);
cout << "Front element: " << q.peek() << endl;
cout << "Dequeued element: " << q.dequeue() << endl;
cout << "Front element: " << q.peek() << endl;
return 0;
}
Front element: 2
Dequeued element: 2
Front element: 5
Here are some of the applications of queue using a linked list:
Operating Systems use queues for job scheduling where processes are executed in the order they arrive. In this case, the queue helps maintain the order of tasks that need to be executed.
Example: Jobs in a printer queue or tasks in a process scheduler in an OS are managed using a queue.
BFS is a graph traversal algorithm used in many applications like social networks, solving mazes, and routing in networks. A queue is essential in BFS for managing the nodes to be explored next. Using a linked list-based queue ensures that memory is used dynamically as the graph or maze grows.
In web servers, incoming requests are handled in the order they are received. A linked list-based queue can manage the requests, ensuring each one is processed in the order it was received.
Example: A web server processes requests to serve files or respond to API calls.
In a traffic control system, queues can be used to manage cars waiting at traffic lights or intersections. A linked list-based queue can dynamically manage the flow of cars based on real-time traffic data.
In conclusion, a queue implemented using a linked list is a versatile and efficient data structure for a wide range of applications, particularly in systems requiring dynamic memory allocation or real-time task handling. It provides efficient O(1) operations for both enqueue and dequeue, making it an essential tool in many real-world scenarios.
When you try to dequeue from an empty queue, typically, an error or exception is thrown (e.g., "Queue Underflow"). It's important to handle this condition in your implementation by checking if the queue is empty before performing the dequeue operation.
Yes, a queue implemented with a linked list can be used in multi-threaded environments, but you would need to implement synchronization mechanisms (like mutexes or locks) to prevent race conditions and ensure thread safety while performing enqueue and dequeue operations.
The major difference between a queue and a stack is the order in which elements are removed:
Source: NxtWave CCBP
Original URL: https://www.ccbp.in/blog/articles/queue-using-linked-list