C++ Program to Implement Queue using Linked List
Queue is the fundamental data structure that follows the First In, First Out (FIFO) principle where the elements are added at the one end, called the rear and removed from other end called the front. In this article, we will learn how to implement queue in C++ using a linked list.
Queue Using Linked List in C++
The queue can implemented using the linked list which consists of the nodes where the each node contains the two parts:
- Data: The value or the data can be stored in the node.
- Next: The pointer to the next node in queue.
The queue itself maintains the two pointers:
- Front: It can be used the points to the first node of the linked list.
- Rear: It can be used the points to the last node of the linked list.
When the queues is empty, both the front and rear pointers are the nullptr. When the new element is enqueued, it is added at the rear and when the element is dequeued, it is removed from the front.
Basic Operations on Queue in C++
The following are the basic operation on the queue in C++ that is implemented using linked list:
Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
Enqueue | It adds the new element to the end of the queue. | O(1) | O(1) |
Dequeue | It removes the element from the front of the queue. | O(1) | O(1) |
Peek | It retrieves but does not remove then the front element of the queue. | O(1) | O(1) |
IsEmpty | Returns true is the queue is empty otherwise returns false. | O(1) | O(1) |
Implementation of Basic Operations
The above basic operations are implemented using the following algorithms:
Algorithm of Enqueue
- Create the new node with the given data.
- Check if the queue is empty.
- If it is empty then set the front and rear pointers to this new node.
- If it is not empty then link the current rear nodes next pointer to this new node.
- Update the rear pointer to the point to the new node.
Algorithm of Dequeue
- Check if the queue is empty.
- If queue is empty then return from the function or throw an error.
- Save the current front node in the temporary variable.
- Move the front pointer to next node in the queue.
- Delete the old front node.
- If the queue becomes the empty then update the rear pointer to nullptr as well.
Algorithm of Peek
- Check if queue is empty.
- If queue is empty then throw the error or return the sentinel value indicating the queue is empty.
- Return the data from the front node.
Algorithm of isEmpty
- Return the true if the front pointer is nullptr otherwise return false.
C++ Program to Implement Queue using Linked List
#include <iostream>
using namespace std;
// Define Node structure
struct Node {
// The data held by the node
int data;
// Pointer to the next node in the list
Node* next;
};
// Define Queue class
class Queue {
// Pointer to the front node of the queue
Node* front;
// Pointer to the rear node of the queue
Node* rear;
public:
// Constructor initializes an empty queue
Queue()
: front(nullptr)
, rear(nullptr)
{
}
// Enqueue adds an element at the end of the queue
void enqueue(int x)
{
// Create a new node with given data
Node* newNode = new Node{ x, nullptr };
// If the queue is empty
if (rear == nullptr) {
// Both front and rear point to the new node
front = rear = newNode;
}
else {
// Link the new node at the end of the queue
rear->next = newNode;
// Update rear to the new node
rear = newNode;
}
}
// Dequeue removes the element at the front of the queue
void dequeue()
{
// If the queue is empty, do nothing
if (front == nullptr)
return;
// Temporary pointer to the front node
Node* temp = front;
// Move front to the next node
front = front->next;
// If the queue is now empty
if (front == nullptr)
// Set rear to nullptr
rear = nullptr;
// Delete the old front node
delete temp;
}
// Peek returns the front element of the queue
int peek()
{
if (!isEmpty())
return front->data;
else
throw runtime_error("Queue is empty");
}
// isEmpty checks if the queue is empty
bool isEmpty()
{
// Return true if front is nullptr
return front == nullptr;
}
};
// Main function
int main()
{
// Create a queue
Queue q;
// Enqueue elements into the queue
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
// Output the front element
cout << "Front element is: " << q.peek() << endl;
// Dequeue the front element
q.dequeue();
// Output the new front element
cout << "Front element is: " << q.peek() << endl;
// Dequeue the remaining elements
q.dequeue();
q.dequeue();
// Check if the queue is empty and output the result
cout << "Queue is empty: " << q.isEmpty() << endl;
return 0;
}
Output
Front element is: 10 Front element is: 20 Queue is empty: 1
Time and Space Complexity
- The time complexity of the implementation of queue using linked list is O(1).
- The space complexity of the implementation of queue using linked list is O(n), where n is number of the nodes in the linked list.
Application of the Linked List Queue
- It can applies in operating system uses the queues for job scheduling.
- It can be used in web servers for the handling incoming requests in the order.
- It can be used for the buffering data streams into the media players.
- It can applies on the inter-process communication for the facilitate asynchronous data exchange between the processes.
Conclusion
Implementing the queue using Linked list in the C++ offers the advantages of the dynamic memory usage. It can allowing the queue to the expand based on the needs of the application. This approach can particularly useful in the scenarios where the maximum size of the queue is not known in advance.