Queue Using Linked List
Table of Content
- What is a Queue?
- What is a Linked List?
- Implementing Queue Using Linked List
- Implementing Queue using Linked List in Python
- Implementing Queue using Linked List in C++
- Implementing Queue using Linked List in Java
- Real-World Application of Queue
What is a Queue?
A queue is a linear data structure with both ends open for operations and follows the principle of First In, First Out (FIFO).
The FIFO principle states that the first element getting inside a queue (i.e., enqueue) has to be the first element that gets out of the queue(i.e., dequeue). To better understand a queue, think of a line to board a bus. The first person in the line will be the first person to board the bus and vice-versa.
Take a look at the image below for reference.
What is a Linked List?
A linked list is a node-based linear data structure used to store data elements. Each node in a linked list is made up of two key components, namely data and next, that store the data and the address of the next none in the linked list, respectively.
A single node in a linked list appears in the image below.
A linked list with multiple nodes typically looks like in the image below.
In the above image, 'HEAD' refers to the first node of the linked list, and 'Null' in Node 3's 'next' pointer/reference indicates that there is no additional node following it, meaning the linked list ends at the third node.
Implementing Queue using Linked list
Follow the below steps to implement a queue using a linked list
Create a New Node
1. When enqueuing an element, first create a new node (say NEW_NODE).
2. Initialize two pointers, FRONT and REAR, which represent the head and the tail of the queue, respectively. These should be set to NULL initially when the queue is created (this step is typically done during the initialization of the queue, not during each enqueue operation).
Set Data and Next Pointer of the New Node
1. Assign the value to be enqueued to the data field of NEW_NODE(say DATA).
2. Set the next pointer of NEW_NODE to NULL.
Enqueue Operation
1. Check if the queue is empty, indicated by FRONT being NULL.
If the queue is empty ( FRONT is NULL)
- Set both FRONT and REAR to NEW_NODE, as this node will be the only one in the queue.
If the queue is not empty ( FRONT is not NULL)
- Update the next pointer of the current REAR node to point to NEW_NODE.
- Update REAR to NEW_NODE, making it the new last node in the queue.
Exit Enqueue Process
This step marks the completion of the enqueue operation. (In the context of coding, this would be the end of the function, and there is no explicit "exit" command required.)
Algorithm
Step 1: [Initialization] (done once when the queue is first created)
- SET FRONT = NULL, SET REAR = NULL
Step 2: [Enqueue Operation]
- CREATE NEW_NODE
- SET DATA of NEW_NODE = VALUE, NEW_NODE NEXT = NULL
- If FRONT is NULL (Queue is empty)
-> SET FRONT = NEW_NODE
-> SET REAR = NEW_NODE
- Else
-> SET REAR NEXT = NEW_NODE
-> SET REAR = NEW_NODE
Implementing Queue using Linked List in Python
In the code below, we have implemented a queue using a linked list in Python. Comments have been added for better readability.
# initialize a nodeclass Node: def __init__(self, value): self.data = value self.next = None
class Queue: def __init__(self): self.front = None self.rear = None
def do_enqueue(self, value): # Create a new node new_node = Node(value) # If queue is empty, set # new node as front and rear if self.front is None: self.front = new_node self.rear = new_node else: # If queue is not empty, # add new node at the rear self.rear.next = new_node self.rear = new_node
def display(self): # Display the elements in the queue current = self.front if current is None: print("Queue is empty") return while current is not None: print(current.data, end=" < - ") current = current.next print("rear")
def do_dequeue(self): # Check if queue is empty if self.front is None: print("Queue is empty, cannot dequeue") return None else: # dequeue the front element temp = self.front self.front = self.front.next if self.front is None: self.rear = None return temp.data
# Example usequeue = Queue()queue.do_enqueue(1)queue.do_enqueue(2)queue.do_enqueue(3)
# Display the elements in the queuequeue.display() dequeued_value = queue.do_dequeue()print(f"Dequeued value: {dequeued_value}")
# Display the elements after do_dequeuequeue.display()
Output
1 <- 2 <- 3 <- rear
Dequeued value: 1
2 <- 3 <- rear
Implementing Queue using Linked List in C++
In the code below, we have implemented a queue using a linked list in C++. Comments have been added for better readability.
#include < iostream >
// the node classclass Node {public: int data; Node* next;
Node(int value) : data(value), next(nullptr) {}};
// the queueclass Queue {private: Node* front; Node* rear;
public: Queue() : front(nullptr), rear(nullptr) {}
void do_enqueue(int value) { // Create a new node Node* new_node = new Node(value);
// If queue is empty, set // new node as front and rear if (front == nullptr) { front = new_node; rear = new_node; } else { // If queue is not empty, // add new node at the rear rear- > next = new_node; rear = new_node; } }
void display() { // Display the elements in the queue Node* current = front; if (current == nullptr) { std::cout < < "Queue is empty" < < std::endl; return; } while (current != nullptr) { std::cout < < current- > data < < " < - "; current = current- > next; } std::cout < < "rear" < < std::endl; }
int do_dequeue() { // Check if queue is empty if (front == nullptr) { std::cout < < "Queue is empty, cannot dequeue" < < std::endl; // Return a default value to // indicate empty queue return -1; } else { // Dequeue the front element Node* temp = front; front = front- > next; if (front == nullptr) { rear = nullptr; } int dequeued_value = temp- > data; // Free the memory delete temp; return dequeued_value; } }};
int main() { Queue queue; queue.do_enqueue(1); queue.do_enqueue(2); queue.do_enqueue(3);
// Display the elements in the queue queue.display();
int dequeued_value = queue.do_dequeue(); std::cout < < "Dequeued value: " < < dequeued_value < < std::endl;
// Display the elements after dequeue queue.display(); return 0;}
class Node { int data; Node next;
public Node(int value) { data = value; next = null; }}
class Queue { private Node front; private Node rear;
public Queue() { front = null; rear = null; }
public void do_enqueue(int value) { Node new_node = new Node(value); if (front == null) { front = new_node; rear = new_node; } else { rear.next = new_node; rear = new_node; } }
public void display() { Node current = front; if (current == null) { System.out.println("Queue is empty"); return; } while (current != null) { System.out.print(current.data + " < - "); current = current.next; } System.out.println("rear"); }
public int do_dequeue() { if (front == null) { System.out.println("Queue is empty, cannot dequeue"); return -1; } else { Node temp = front; front = front.next; if (front == null) { rear = null; } int dequeuedValue = temp.data; return dequeuedValue; } }}
class Main { public static void main(String[] args) { Queue queue = new Queue(); queue.do_enqueue(1); queue.do_enqueue(2); queue.do_enqueue(3);
queue.display();
int dequeuedValue = queue.do_dequeue(); System.out.println("Dequeued value: " + dequeuedValue);
queue.display(); }}
Output
1 <- 2 <- 3 <- rear
Dequeued value: 1
2 <- 3 <- rear
Real-World Application of Queue
Below listed are some real-world use cases of the queue data structure
- Operating Systems: Queues are often used to schedule processes to be executed by the CPU. Queues are used to prioritize tasks by various scheduling algorithms within the operating system. It is also used to manage the I/O requests in operating systems.
- Data Traffic Management: Devices like Routers and switches use queues to manage data buffers for data packet transmission.
- Web Servers: Web servers use a queue data structure to manage and optimize incoming requests. All requests to the server is added to the queue and are processed using the FIFO principle.
- Printers: Printers, while printing multiple documents, use queues to manage the workload and process each printing task based on the queue.
- Banking Systems: Banking transactions like RTGS are managed using queues, as the bank receives many customer transaction requests. Each such request is put into a queue and is processed one at a time.
- Call Center Systems: The queue data structure manages customer connect requests to the support representative. It works on a first-come, first-serve basis.
- Television Broadcast: Television stations manage the broadcast queue, ensuring programs or advertisements are played in the intended sequence.
Conclusion
Thus, implementing a queue using a linked list is a fundamental and efficient approach in data structure and algorithm design. This method utilizes the dynamic nature of linked lists to manage data in a FIFO (First In, First Out) manner, ensuring a easy and flexible operation of enqueue (adding) and dequeue (removing) elements.
Contributed by: Raju Kumar
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
