Let’s implement the linear queue using Linked List. Firstly define a Node structure to represent the Queue items and initialize Front and Rear pointers to NULL. Then, implement the enqueue(), dequeue(), and peek() functions to insert, delete, and fetch the elements respectively.
Representation of Queue using Linked List
// Queue Node Representation
struct Node {
int element;
Node* next;
};
// Queue front and rear pointer
Node* front = NULL;
Node* rear = NULL;
Queue Implementation using Linked List
An example program to implement the Queue using a Linked List. This is an object-oriented implementation that encapsulates the Queue data structure using a c++ class.
/**
* C++ example to demonstrate Queue implementation using Linked List
*/
#include <iostream>
using namespace std;
/**
* Queue Node Representation
*/
struct Node {
int element;
Node* next;
};
/**
* Queue implementation using Linked List
*/
class Queue
{
private:
// Queue front pointer
Node* front;
// Queue rear pointer
Node* rear;
public:
// Constructor
Queue() : front(NULL), rear(NULL) {}
// Check if the Queue is empty
bool isEmpty();
// Returns the top element without deleting
int peek();
// Enqueue new element to Queue
void enqueue(int element);
// Dequeue an element from Queue
int dequeue();
// Traverse and display the Queue
void display(string msg);
};
// Check if the Queue is empty
bool Queue::isEmpty() {
if (front == NULL) {
cout << "Queue is Empty" << endl;
return true;
}
return false;
}
// Returns the top element without deleting
int Queue::peek() {
if (isEmpty()) {
return -1;
}
return front->element;
}
// Enqueue new element to Queue
void Queue::enqueue(int element) {
// Step 1: Create the new node
Node* node = new Node();
if (node == NULL) {
cout << "System out of memory" << endl;
return;
}
node->element = element;
node->next = NULL;
// Step 2: If the Queue is empty, set the Front to point the new node. Otherwise connect the new node at Rear.
if (rear == NULL) {
front = node;
} else {
rear->next = node;
}
// Step 3: Change the rear to point the new node
rear = node;
}
// Dequeue an element from Queue
int Queue::dequeue() {
// Check if the Queue is empty
if (front == NULL) {
return -1;
}
// Step 1: Retrieve the element at Front
int element = front->element;
// Step 2: Remember the front node in a temporary pointer
Node* tmp = front;
// Step 3: If the next node is available, change the Front to point the next node. Otherwise set Front and Rear to point the NULL
if (front->next == NULL) {
front = rear = NULL;
} else {
front = front->next;
}
// Step 4: Delete the node stored in temporary pointer
delete tmp;
return element;
}
// Traverse and display the Queue
void Queue::display(string msg) {
cout << msg << endl;
if (isEmpty()) {
return;
}
if (front == rear) {
cout << front->element << " <-- front, rear" << endl;
return;
}
cout << front->element << " <-- front" << endl;
for (Node* node=front->next; node != rear; node = node->next) {
cout << node->element << endl;
}
cout << rear->element << " <-- rear" << endl;
}
// The main function to begin the execution
int main()
{
// Create a Queue
Queue queue;
// Push the elements (10, 20, 30, 40 and 50)
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.display("Queue after inserting 10 20 30 and 40");
queue.enqueue(50);
queue.display("Queue after inserting 50");
// Get the peek element
int element = queue.peek();
cout << "Peek element returned " << element << endl;
// Pop the elements from Queue
element = queue.dequeue();
cout << "Dequeue element returned " << element << endl;
element = queue.dequeue();
cout << "Dequeue element returned " << element << endl;
queue.display("Queue after removing two elements");
}
Output
Queue after inserting 10 20 30 and 40
10 <-- front
20
30
40 <-- rear
Queue after inserting 50
10 <-- front
20
30
40
50 <-- rear
Peek element returned 10
Dequeue element returned 10
Dequeue element returned 20
Queue after removing two elements
30 <-- front
40
50 <-- rear
Operations of Queue
Here, we discuss the step-by-step workflow for Enqueue and Dequeue operations using a Linked List.
Enqueue with Linked List
Enqueue inserts the new element into the queue at the Rear side. Create a new node and link it to the Rear side.
Algorithm
- Create a new Node
- If the Queue is empty, connect the new node at the Front. Otherwise, connect to the Rear side.
- Finally, update the Rear to point to the new node
Enqueue works in O(1) Time Complexity since it has a direct pointer to the Rear.
Examples
The queue is empty initially and the Front and Rear pointers are set to the NULL value. The following steps illustrate enqueuing the first element to an empty Queue.
The Front and Rear point to some valid node when the queue is not empty. Insert the new element by creating a new node on the rear side. Then, update the Rear to point to the new node.
Dequeue with Linked List
Dequeue removes the element from the queue on the Front side. It can return failure when the Queue is empty.
Algorithm
- Retrieve the value of the Front node.
- Initialize a temporary pointer to remember the front node.
- If the next node is available, change the Front to point to the next node. Otherwise set Front and Rear to point the NULL to indicate the Queue is empty.
- Finally, Delete the node referenced in the temporary pointer.
Examples
The queue must be non-empty to perform the Dequeue operation. Retrieve the element present at the Front side and change the Front to point to the next node.
The procedure for Dequeuing the last element differs. The Front pointer can’t move further because the next node is unavailable. In such a case, reset the Front and Rear to NULL to indicate the queue is empty.
Frequently Asked Questions
When to Implement Queue using Linked List
Linked List implementation can be the preferred choice when the data is dynamic and large. Unlike the array implementation, it does not have a drawback in memory usage. Since the linked list work by dynamic allocations, it is suitable for handling dynamic data.
References
- Also, see Queue Implementation using Array
- Linked List implementation of Queue in C at PrepInsta