How to Implement a Queue Using Linked List in C++
Queues are fundamental data structures that follow the First In First Out (FIFO) principle. They are widely used in various applications, from managing tasks in operating systems to handling requests on web servers. In this article, we will explore how to implement a queue using a linked list in C++. This approach not only provides a dynamic way to manage your data but also enhances your understanding of data structures in C++.
What is a Queue?
A queue is a linear data structure that allows elements to be added at one end (the rear) and removed from the other end (the front). This makes queues ideal for scenarios where the order of processing matters. Some common use cases include:
- Task scheduling: Managing processes in operating systems.
- Print spooling: Ordering print jobs in a printer.
- Breadth-first search: Utilizing queues to explore nodes in graphs.
Why Use a Linked List for a Queue?
Using a linked list to implement a queue has several advantages over using an array:
- Dynamic Size: Unlike arrays, linked lists can grow and shrink as needed, making them more memory efficient.
- No Wasted Space: Queues implemented with arrays can lead to wasted space if the maximum size is not fully utilized.
- Ease of Insertion/Deletion: Inserting or removing elements from a linked list is generally more efficient than in an array, especially when dealing with large datasets.
Key Components of a Linked List Queue
To implement a queue using a linked list, we need two main components:
- Node Structure: This will hold the data and a pointer to the next node.
- Queue Class: This will manage the front and rear pointers and provide methods for enqueueing and dequeueing elements.
Step-by-Step Implementation
Let's dive into the code implementation.
Step 1: Define the Node Structure
First, we need to create a node structure that will represent each element in the queue.
struct Node {
int data; // Data part
Node* next; // Pointer to the next node
Node(int val) : data(val), next(nullptr) {} // Constructor
};
Step 2: Create the Queue Class
Next, we will create the Queue class that will encapsulate the functionality of our queue.
class Queue {
private:
Node* front; // Pointer to the front of the queue
Node* rear; // Pointer to the rear of the queue
public:
Queue() : front(nullptr), rear(nullptr) {} // Constructor
// Function to add an element to the queue
void enqueue(int value);
// Function to remove an element from the queue
int dequeue();
// Function to check if the queue is empty
bool isEmpty();
// Function to get the front element
int peek();
};
Step 3: Implement Enqueue Operation
The enqueue operation adds an element to the rear of the queue.
void Queue::enqueue(int value) {
Node* newNode = new Node(value); // Create a new node
// If the queue is empty, both front and rear will point to the new node
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode; // Link the new node at the end
rear = newNode; // Update rear to new node
}
}
Step 4: Implement Dequeue Operation
The dequeue operation removes an element from the front of the queue.
int Queue::dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty"); // Error handling
}
Node* temp = front; // Store the front node
int value = front->data; // Get the data from the front node
front = front->next; // Update front to the next node
// If the queue becomes empty, update rear as well
if (front == nullptr) {
rear = nullptr;
}
delete temp; // Free the memory of the old front node
return value; // Return the dequeued value
}
Step 5: Implement Additional Methods
To enhance our queue, we can implement methods to check if the queue is empty and to peek at the front element.
bool Queue::isEmpty() {
return front == nullptr; // Check if the front is null
}
int Queue::peek() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty"); // Error handling
}
return front->data; // Return the data at the front node
}
Complete Example
Here is the complete code for our Queue implementation using a linked list:
#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() : front(nullptr), rear(nullptr) {}
void enqueue(int value);
int dequeue();
bool isEmpty();
int peek();
};
void Queue::enqueue(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
}
int Queue::dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
}
Node* temp = front;
int value = front->data;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return value;
}
bool Queue::isEmpty() {
return front == nullptr;
}
int Queue::peek() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
}
return front->data;
}
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
std::cout << "Front element: " << queue.peek() << std::endl; // Output: Front element: 10
std::cout << "Dequeued: " << queue.dequeue() << std::endl; // Output: Dequeued: 10
std::cout << "Front element after dequeue: " << queue.peek() << std::endl; // Output: Front element after dequeue: 20
return 0;
}
Conclusion
Implementing a queue using a linked list in C++ provides an efficient and flexible way to manage data in a FIFO manner. This approach enhances your programming skills and deepens your understanding of data structures. With the clear examples and step-by-step instructions provided, you can easily integrate this queue implementation into your projects or use it as a foundation for more complex data structures.
Feel free to experiment with the code, optimize it further, and troubleshoot any issues you encounter. Happy coding!