Queue - Linked List Implementation Last Updated : 25 Mar, 2025 Summarize Suggest changes Share Like Article Like Report In this article, the Linked List implementation of the queue data structure is discussed and implemented. Print '-1' if the queue is empty.Approach: To solve the problem follow the below idea:we maintain two pointers, front and rear. The front points to the first item of the queue and rear points to the last item.enQueue(): This operation adds a new node after the rear and moves the rear to the next node.deQueue(): This operation removes the front node and moves the front to the next node.Queue using Linked ListFollow the below steps to solve the problem:Create a class Node with data members integer data and Node* nextA parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as NULLCreate a class Queue with data members Node front and rearEnqueue Operation with parameter x:Initialize Node* temp with data = xIf the rear is set to NULL then set the front and rear to temp and return(Base Case)Else set rear next to temp and then move rear to tempDequeue Operation:If the front is set to NULL return(Base Case)Initialize Node temp with front and set front to its nextIf the front is equal to NULL then set the rear to NULLDelete temp from the memoryBelow is the Implementation of the above approach: C++ #include <iostream> using namespace std; // Node class definition class Node { public: int data; Node* next; Node(int new_data) { data = new_data; next = nullptr; } }; // Queue class definition class Queue { private: Node* front; Node* rear; public: Queue() { front = rear = nullptr; } // Function to check if the queue is empty bool isEmpty() { return front == nullptr; } // Function to add an element to the queue void enqueue(int new_data) { Node* new_node = new Node(new_data); if (isEmpty()) { front = rear = new_node; printQueue(); return; } rear->next = new_node; rear = new_node; printQueue(); } // Function to remove an element from the queue void dequeue() { if (isEmpty()) { return; } Node* temp = front; front = front->next; if (front == nullptr) rear = nullptr; delete temp; printQueue(); } // Function to print the current state of the queue void printQueue() { if (isEmpty()) { cout << "Queue is empty" << endl; return; } Node* temp = front; cout << "Current Queue: "; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl; } }; // Driver code to test the queue implementation int main() { Queue q; // Enqueue elements into the queue q.enqueue(10); q.enqueue(20); // Dequeue elements from the queue q.dequeue(); q.dequeue(); // Enqueue more elements into the queue q.enqueue(30); q.enqueue(40); q.enqueue(50); // Dequeue an element from the queue (this should print 30) q.dequeue(); return 0; } C #include <stdio.h> #include <stdlib.h> // Node structure definition struct Node { int data; struct Node* next; }; // Queue structure definition struct Queue { struct Node* front; struct Node* rear; }; // Function to create a new node struct Node* newNode(int new_data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = new_data; node->next = NULL; return node; } // Function to initialize the queue struct Queue* createQueue() { struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue)); q->front = q->rear = NULL; return q; } // Function to check if the queue is empty int isEmpty(struct Queue* q) { return q->front == NULL; } // Function to add an element to the queue void enqueue(struct Queue* q, int new_data) { struct Node* new_node = newNode(new_data); if (isEmpty(q)) { q->front = q->rear = new_node; printQueue(q); return; } q->rear->next = new_node; q->rear = new_node; printQueue(q); } // Function to remove an element from the queue void dequeue(struct Queue* q) { if (isEmpty(q)) { return; } struct Node* temp = q->front; q->front = q->front->next; if (q->front == NULL) q->rear = NULL; free(temp); printQueue(q); } // Function to print the current state of the queue void printQueue(struct Queue* q) { if (isEmpty(q)) { printf("Queue is empty\n"); return; } struct Node* temp = q->front; printf("Current Queue: "); while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // Driver code to test the queue implementation int main() { struct Queue* q = createQueue(); // Enqueue elements into the queue enqueue(q, 10); enqueue(q, 20); // Dequeue elements from the queue dequeue(q); dequeue(q); // Enqueue more elements into the queue enqueue(q, 30); enqueue(q, 40); enqueue(q, 50); // Dequeue an element from the queue (this should print 30) dequeue(q); return 0; } Java // Node class definition class Node { int data; Node next; Node(int new_data) { data = new_data; next = null; } } // Queue class definition class Queue { private Node front; private Node rear; public Queue() { front = rear = null; } // Function to check if the queue is empty public boolean isEmpty() { return front == null; } // Function to add an element to the queue public void enqueue(int new_data) { Node new_node = new Node(new_data); if (isEmpty()) { front = rear = new_node; printQueue(); return; } rear.next = new_node; rear = new_node; printQueue(); } // Function to remove an element from the queue public void dequeue() { if (isEmpty()) { return; } Node temp = front; front = front.next; if (front == null) rear = null; temp = null; printQueue(); } // Function to print the current state of the queue public void printQueue() { if (isEmpty()) { System.out.println("Queue is empty"); return; } Node temp = front; System.out.print("Current Queue: "); while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } } // Driver code to test the queue implementation public class Main { public static void main(String[] args) { Queue q = new Queue(); // Enqueue elements into the queue q.enqueue(10); q.enqueue(20); // Dequeue elements from the queue q.dequeue(); q.dequeue(); // Enqueue more elements into the queue q.enqueue(30); q.enqueue(40); q.enqueue(50); // Dequeue an element from the queue (this should print 30) q.dequeue(); } } Python class Node: def __init__(self, new_data): self.data = new_data self.next = None class Queue: def __init__(self): self.front = self.rear = None # Function to check if the queue is empty def isEmpty(self): return self.front is None # Function to add an element to the queue def enqueue(self, new_data): new_node = Node(new_data) if self.isEmpty(): self.front = self.rear = new_node self.printQueue() return self.rear.next = new_node self.rear = new_node self.printQueue() # Function to remove an element from the queue def dequeue(self): if self.isEmpty(): return temp = self.front self.front = self.front.next if self.front is None: self.rear = None self.printQueue() # Function to print the current state of the queue def printQueue(self): if self.isEmpty(): print("Queue is empty") return temp = self.front queue_string = "Current Queue: " while temp is not None: queue_string += str(temp.data) + " " temp = temp.next print(queue_string) q = Queue() # Enqueue elements into the queue q.enqueue(10) q.enqueue(20) # Dequeue elements from the queue q.dequeue() q.dequeue() # Enqueue more elements into the queue q.enqueue(30) q.enqueue(40) q.enqueue(50) # Dequeue an element from the queue q.dequeue() JavaScript // Node class class Node { constructor(new_data) { this.data = new_data; this.next = null; } } // Queue class class Queue { constructor() { this.front = this.rear = null; } // Function to check if the queue is empty isEmpty() { return this.front === null; } // Function to add an element to the queue enqueue(new_data) { const new_node = new Node(new_data); if (this.isEmpty()) { this.front = this.rear = new_node; this.printQueue(); return; } this.rear.next = new_node; this.rear = new_node; this.printQueue(); } // Function to remove an element from the queue dequeue() { if (this.isEmpty()) { return; } const temp = this.front; this.front = this.front.next; if (this.front === null) { this.rear = null; } this.printQueue(); } // Function to print the current state of the queue printQueue() { if (this.isEmpty()) { console.log("Queue is empty"); return; } let temp = this.front; let queue_string = "Current Queue: "; while (temp !== null) { queue_string += temp.data + " "; temp = temp.next; } console.log(queue_string); } } const q = new Queue(); // Enqueue elements into the queue q.enqueue(10); q.enqueue(20); // Dequeue elements from the queue q.dequeue(); q.dequeue(); // Enqueue more elements into the queue q.enqueue(30); q.enqueue(40); q.enqueue(50); // Dequeue an element from the queue q.dequeue(); OutputCurrent Queue: 10 Current Queue: 10 20 Current Queue: 20 Queue is empty Current Queue: 30 Current Queue: 30 40 Current Queue: 30 40 50 Current Queue: 40 50 Time Complexity: O(1), The time complexity of both operations enqueue() and dequeue() is O(1) as it only changes a few pointers in both operationsAuxiliary Space: O(1), The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is requiredRelated Article:Array Implementation of Queue Advertise with us Next Article Applications, Advantages and Disadvantages of Queue K kartik Follow Similar Reads Queue Data Structure A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of "First in, First out" (FIFO), where the first element added to the queue is the first one to be removed. It is used as a buffer in computer systems 2 min read Introduction to Queue Data Structure Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first element inserted is the first to be popped out. FIFO Principle in Queue:FIFO Principle states that the first element added to the Queue will be the first one to be removed or processed. So, Queue is like 5 min read Introduction and Array Implementation of Queue Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginn 2 min read Queue - Linked List Implementation In this article, the Linked List implementation of the queue data structure is discussed and implemented. Print '-1' if the queue is empty.Approach: To solve the problem follow the below idea:we maintain two pointers, front and rear. The front points to the first item of the queue and rear points to 8 min read Applications, Advantages and Disadvantages of Queue A Queue is a linear data structure. This data structure follows a particular order in which the operations are performed. The order is First In First Out (FIFO). It means that the element that is inserted first in the queue will come out first and the element that is inserted last will come out last 5 min read Different Types of Queues and its Applications Introduction : A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. In this article, the diff 8 min read Queue implementation in different languagesQueue in C++ STLIn C++, queue container follows the FIFO (First In First Out) order of insertion and deletion. According to it, the elements that are inserted first should be removed first. This is possible by inserting elements at one end (called back) and deleting them from the other end (called front) of the dat 4 min read Queue Interface In JavaThe Queue Interface is a part of java.util package and extends the Collection interface. It stores and processes the data in order means elements are inserted at the end and removed from the front. Key Features:Most implementations, like PriorityQueue, do not allow null elements.Implementation Class 12 min read Queue in PythonLike a stack, the queue is a linear data structure that stores items in a First In First Out (FIFO) manner. With a queue, the least recently added item is removed first. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. Operations 6 min read C# Queue with ExamplesA Queue in C# is a collection that follows the First-In-First-Out (FIFO) principle which means elements are processed in the same order they are added. It is a part of the System.Collections namespace for non-generic queues and System.Collections.Generic namespace for generic queues.Key Features:FIF 6 min read Implementation of Queue in JavascriptA Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Elements are inserted at the rear and removed from the front.Queue Operationsenqueue(item) - Adds an element to the end of the queue.dequeue() - Removes and returns the first element from the queue.peek() - Ret 7 min read Queue in Go LanguageA queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). Now if you are familiar with other programming languages like C++, Java, and Python then there are inbuilt queue libraries that can be used for the implementat 4 min read Queue in ScalaA queue is a first-in, first-out (FIFO) data structure. Scala offers both an immutable queue and a mutable queue. A mutable queue can be updated or extended in place. It means one can change, add, or remove elements of a queue as a side effect. Immutable queue, by contrast, never change. In Scala, Q 3 min read Some question related to Queue implementationImplementation of Deque using doubly linked listA Deque (Double-Ended Queue) is a data structure that allows adding and removing elements from both the front and rear ends. Using a doubly linked list to implement a deque makes these operations very efficient, as each node in the list has pointers to both the previous and next nodes. This means we 9 min read Queue using StacksGiven a stack that supports push and pop operations, your task is to implement a queue using one or more instances of that stack along with its operations.Table of ContentBy Making Enqueue Operation CostlyBy Making Dequeue Operation Costly Queue Implementation Using One Stack and RecursionBy Making 11 min read implement k Queues in a single arrayGiven an array of size n, the task is to implement k queues using the array.enqueue(qn, x) : Adds the element x into the queue number qn dequeue(qn, x) : Removes the front element from queue number qn isFull(qn) : Checks if the queue number qn is fullisEmpty(qn) : Checks if the queue number qn is em 15+ min read LRU Cache - Complete TutorialWhat is LRU Cache? Cache replacement algorithms are efficiently designed to replace the cache when the space is full. The Least Recently Used (LRU) is one of those algorithms. As the name suggests when the cache memory is full, LRU picks the data that is least recently used and removes it in order t 8 min read Easy problems on QueueDetect cycle in an undirected graph using BFSGiven an undirected graph, the task is to determine if cycle is present in it or not.Examples:Input: V = 5, edges[][] = [[0, 1], [0, 2], [0, 3], [1, 2], [3, 4]]Undirected Graph with 5 NodeOutput: trueExplanation: The diagram clearly shows a cycle 0 → 2 → 1 → 0.Input: V = 4, edges[][] = [[0, 1], [1, 6 min read Breadth First Search or BFS for a GraphGiven a undirected graph represented by an adjacency list adj, where each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right according to the adjacency list, and return a list conta 15+ min read Traversing directory in Java using BFSGiven a directory, print all files and folders present in directory tree rooted with given directory. We can iteratively traverse directory in BFS using below steps. We create an empty queue and we first enqueue given directory path. We run a loop while queue is not empty. We dequeue an item from qu 2 min read Vertical Traversal of a Binary TreeGiven a Binary Tree, the task is to find its vertical traversal starting from the leftmost level to the rightmost level. If multiple nodes pass through a vertical line, they should be printed as they appear in the level order traversal of the tree.Examples: Input:Output: [[4], [2], [1, 5, 6], [3, 8] 10 min read Print Right View of a Binary TreeGiven a Binary Tree, the task is to print the Right view of it. The right view of a Binary Tree is a set of rightmost nodes for every level.Examples: Example 1: The Green colored nodes (1, 3, 5) represents the Right view in the below Binary tree. Example 2: The Green colored nodes (1, 3, 4, 5) repre 15+ min read Find Minimum Depth of a Binary TreeGiven a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. For example, minimum depth of below Binary Tree is 2. Note that the path must end on a leaf node. For example, the minimum depth of below Bi 15 min read Check whether a given graph is Bipartite or notGiven a graph with V vertices numbered from 0 to V-1 and a list of edges, determine whether the graph is bipartite or not.Note: A bipartite graph is a type of graph where the set of vertices can be divided into two disjoint sets, say U and V, such that every edge connects a vertex in U to a vertex i 8 min read Intermediate problems on QueueFlatten a multilevel linked list using level order traversalGiven a linked list where in addition to the next pointer, each node has a child pointer, which may or may not point to a separate list. These child lists may have one or more children of their own to produce a multilevel linked list. Given the head of the first level of the list. The task is to fla 9 min read Level with maximum number of nodesGiven a binary tree, the task is to find the level in a binary tree that has the maximum number of nodes. Note: The root is at level 0.Examples: Input: Binary Tree Output : 2Explanation: Input: Binary tree Output:1Explanation Using Breadth First Search - O(n) time and O(n) spaceThe idea is to traver 12 min read Find if there is a path between two vertices in a directed graphGiven a Directed Graph and two vertices src and dest, check whether there is a path from src to dest.Example: Consider the following Graph: adj[][] = [ [], [0, 2], [0, 3], [], [2] ]Input : src = 1, dest = 3Output: YesExplanation: There is a path from 1 to 3, 1 -> 2 -> 3Input : src = 0, dest = 11 min read All nodes between two given levels in Binary TreeGiven a binary tree, the task is to print all nodes between two given levels in a binary tree. Print the nodes level-wise, i.e., the nodes for any level should be printed from left to right. Note: The levels are 1-indexed, i.e., root node is at level 1.Example: Input: Binary tree, l = 2, h = 3Output 8 min read Find next right node of a given keyGiven a Binary tree and a key in the binary tree, find the node right to the given key. If there is no node on right side, then return NULL. Expected time complexity is O(n) where n is the number of nodes in the given binary tree.Example:Input: root = [10 2 6 8 4 N 5] and key = 2Output: 6Explanation 15+ min read Minimum steps to reach target by a Knight | Set 1Given a square chessboard of n x n size, the position of the Knight and the position of a target are given. We need to find out the minimum steps a Knight will take to reach the target position.Examples: Input: KnightknightPosition: (1, 3) , targetPosition: (5, 0)Output: 3Explanation: In above diagr 9 min read Islands in a graph using BFSGiven an n x m grid of 'W' (Water) and 'L' (Land), the task is to count the number of islands. An island is a group of adjacent 'L' cells connected horizontally, vertically, or diagonally, and it is surrounded by water or the grid boundary. The goal is to determine how many distinct islands exist in 15+ min read Level order traversal line by line (Using One Queue)Given a Binary Tree, the task is to print the nodes level-wise, each level on a new line.Example:Input:Output:12 34 5Table of Content[Expected Approach – 1] Using Queue with delimiter – O(n) Time and O(n) Space[Expected Approach – 2] Using Queue without delimiter – O(n) Time and O(n) Space[Expected 12 min read First non-repeating character in a streamGiven an input stream s consisting solely of lowercase letters, you are required to identify which character has appeared only once in the stream up to each point. If there are multiple characters that have appeared only once, return the one that first appeared. If no character has appeared only onc 15+ min read Article Tags : Linked List Queue DSA Amazon Oracle Qualcomm Samsung +3 More Practice Tags : AmazonOracleQualcommSamsungLinked ListQueue +2 More Like