Queue – Linked List Implementation

Last Updated : 12 Jan, 2023

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.

Follow the below steps to solve the problem:

Create a class QNode with data members integer data and QNode* next
- A parameterized constructor that takes an integer x value as a parameter and sets data equal to x and next as NULL
Create a class Queue with data members QNode front and rear
Enqueue Operation with parameter x:
- Initialize QNode* temp with data = x
- If 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 temp
Dequeue Operation:
- If the front is set to NULL return(Base Case)
- Initialize QNode temp with front and set front to its next
- If the front is equal to NULL then set the rear to NULL
- Delete temp from the memory

Below is the Implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
struct QNode {
    int data;
    QNode* next;
    QNode(int d)
    {
        data = d;
        next = NULL;
    }
};
 
struct Queue {
    QNode *front, *rear;
    Queue() { front = rear = NULL; }
 
    void enQueue(int x)
    {
 
        // Create a new LL node
        QNode* temp = new QNode(x);
 
        // If queue is empty, then
        // new node is front and rear both
        if (rear == NULL) {
            front = rear = temp;
            return;
        }
 
        // Add the new node at
        // the end of queue and change rear
        rear->next = temp;
        rear = temp;
    }
 
    // Function to remove
    // a key from given queue q
    void deQueue()
    {
        // If queue is empty, return NULL.
        if (front == NULL)
            return;
 
        // Store previous front and
        // move front one node ahead
        QNode* temp = front;
        front = front->next;
 
        // If front becomes NULL, then
        // change rear also as NULL
        if (front == NULL)
            rear = NULL;
 
        delete (temp);
    }
};
 
// Driver code
int main()
{
 
    Queue q;
    q.enQueue(10);
    q.enQueue(20);
    q.deQueue();
    q.deQueue();
    q.enQueue(30);
    q.enQueue(40);
    q.enQueue(50);
    q.deQueue();
    cout << "Queue Front : " << ((q.front != NULL) ? (q.front)->data : -1)<< endl;
    cout << "Queue Rear : " << ((q.rear != NULL) ? (q.rear)->data : -1);
}
// This code is contributed by rathbhupendra

C

// A C program to demonstrate linked list based
// implementation of queue
#include <stdio.h>
#include <stdlib.h>
 
// A linked list (LL) node to store a queue entry
struct QNode {
    int key;
    struct QNode* next;
};
 
// The queue, front stores the front node of LL and rear
// stores the last node of LL
struct Queue {
    struct QNode *front, *rear;
};
 
// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
    struct QNode* temp
        = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;
    return temp;
}
 
// A utility function to create an empty queue
struct Queue* createQueue()
{
    struct Queue* q
        = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}
 
// The function to add a key k to q
void enQueue(struct Queue* q, int k)
{
    // Create a new LL node
    struct QNode* temp = newNode(k);
 
    // If queue is empty, then new node is front and rear
    // both
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
 
    // Add the new node at the end of queue and change rear
    q->rear->next = temp;
    q->rear = temp;
}
 
// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
    // If queue is empty, return NULL.
    if (q->front == NULL)
        return;
 
    // Store previous front and move front one node ahead
    struct QNode* temp = q->front;
 
    q->front = q->front->next;
 
    // If front becomes NULL, then change rear also as NULL
    if (q->front == NULL)
        q->rear = NULL;
 
    free(temp);
}
 
// Driver code
int main()
{
    struct Queue* q = createQueue();
    enQueue(q, 10);
    enQueue(q, 20);
    deQueue(q);
    deQueue(q);
    enQueue(q, 30);
    enQueue(q, 40);
    enQueue(q, 50);
    deQueue(q);
    printf("Queue Front : %d \n", ((q->front != NULL) ? (q->front)->key : -1));
    printf("Queue Rear : %d", ((q->rear != NULL) ? (q->rear)->key : -1));
    return 0;
}

Java

// Java program for linked-list implementation of queue
 
// A linked list (LL) node to store a queue entry
class QNode {
    int key;
    QNode next;
 
    // constructor to create a new linked list node
    public QNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
// A class to represent a queue
// The queue, front stores the front node of LL and rear
// stores the last node of LL
class Queue {
    QNode front, rear;
 
    public Queue() { this.front = this.rear = null; }
 
    // Method to add an key to the queue.
    void enqueue(int key)
    {
 
        // Create a new LL node
        QNode temp = new QNode(key);
 
        // If queue is empty, then new node is front and
        // rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
 
        // Add the new node at the end of queue and change
        // rear
        this.rear.next = temp;
        this.rear = temp;
    }
 
    // Method to remove an key from queue.
    void dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
            return;
 
        // Store previous front and move front one node
        // ahead
        QNode temp = this.front;
        this.front = this.front.next;
 
        // If front becomes NULL, then change rear also as
        // NULL
        if (this.front == null)
            this.rear = null;
    }
}
 
// Driver code
public class Test {
    public static void main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.dequeue();
        q.dequeue();
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);
        q.dequeue();
        System.out.println("Queue Front : " + ((q.front != null) ? (q.front).key : -1));
        System.out.println("Queue Rear : " + ((q.rear != null) ? (q.rear).key : -1));
    }
}
// This code is contributed by Gaurav Miglani

Python3

# Python3 program to demonstrate linked list
# based implementation of queue
 
# A linked list (LL) node
# to store a queue entry
 
 
class Node:
 
    def __init__(self, data):
        self.data = data
        self.next = None
 
# A class to represent a queue
 
# The queue, front stores the front node
# of LL and rear stores the last node of LL
 
 
class Queue:
 
    def __init__(self):
        self.front = self.rear = None
 
    def isEmpty(self):
        return self.front == None
 
    # Method to add an item to the queue
    def EnQueue(self, item):
        temp = Node(item)
 
        if self.rear == None:
            self.front = self.rear = temp
            return
        self.rear.next = temp
        self.rear = temp
 
    # Method to remove an item from queue
    def DeQueue(self):
 
        if self.isEmpty():
            return
        temp = self.front
        self.front = temp.next
 
        if(self.front == None):
            self.rear = None
 
 
# Driver Code
if __name__ == '__main__':
    q = Queue()
    q.EnQueue(10)
    q.EnQueue(20)
    q.DeQueue()
    q.DeQueue()
    q.EnQueue(30)
    q.EnQueue(40)
    q.EnQueue(50)
    q.DeQueue()
    print("Queue Front : " + str(q.front.data if q.front != None else -1))
    print("Queue Rear : " + str(q.rear.data if q.rear != None else -1))

C#

// C# program for linked-list
// implementation of queue
using System;
 
// A linked list (LL) node to
// store a queue entry
class QNode {
    public int key;
    public QNode next;
 
    // constructor to create
    // a new linked list node
    public QNode(int key)
    {
        this.key = key;
        this.next = null;
    }
}
 
// A class to represent a queue The queue,
// front stores the front node of LL and
// rear stores the last node of LL
class Queue {
    public QNode front, rear;
 
    public Queue() { this.front = this.rear = null; }
 
    // Method to add an key to the queue.
    public void enqueue(int key)
    {
 
        // Create a new LL node
        QNode temp = new QNode(key);
 
        // If queue is empty, then new
        // node is front and rear both
        if (this.rear == null) {
            this.front = this.rear = temp;
            return;
        }
 
        // Add the new node at the
        // end of queue and change rear
        this.rear.next = temp;
        this.rear = temp;
    }
 
    // Method to remove an key from queue.
    public void dequeue()
    {
        // If queue is empty, return NULL.
        if (this.front == null)
            return;
 
        // Store previous front and
        // move front one node ahead
        this.front = this.front.next;
 
        // If front becomes NULL,
        // then change rear also as NULL
        if (this.front == null)
            this.rear = null;
    }
}
 
// Driver code
public class Test {
    public static void Main(String[] args)
    {
        Queue q = new Queue();
        q.enqueue(10);
        q.enqueue(20);
        q.dequeue();
        q.dequeue();
        q.enqueue(30);
        q.enqueue(40);
        q.enqueue(50);
        q.dequeue();
        Console.WriteLine("Queue Front : " + ((q.front != null) ? (q.front).key : -1));
        Console.WriteLine("Queue Rear : " + ((q.rear != null) ? (q.rear).key : -1));
    }
}
 
// This code has been contributed by Rajput-Ji

Javascript

<script>
// JavaScript program for linked-list implementation of queue
class QNode
{
    constructor(key)
    {
        this.key = key;
        this.next = null;
    }
}
 
let front = null, rear = null;
 
function enqueue(key)
{
    // Create a new LL node
        let temp = new QNode(key);
   
        // If queue is empty, then new node is front and rear both
        if (rear == null) {
            front = rear = temp;
            return;
        }
   
        // Add the new node at the end of queue and change rear
        rear.next = temp;
        rear = temp;
}
 
 
function dequeue()
{
    // If queue is empty, return NULL.
        if (front == null)
            return;
   
        // Store previous front and move front one node ahead
        let temp = front;
        front = front.next;
   
        // If front becomes NULL, then change rear also as NULL
        if (front == null)
            rear = null;
}
 
 
enqueue(10);
enqueue(20);
dequeue();
dequeue();
enqueue(30);
enqueue(40);
enqueue(50);
dequeue();
document.write("Queue Front : " +  ((front != null) ? (front).key : -1) +"<br>");
document.write("Queue Rear : " +  ((rear != null) ? (rear).key : -1) +"<br>");
 
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

Queue Front : 40
Queue Rear : 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 operations
Auxiliary Space: O(1), The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is required

Related Article:
Introduction and Array Implementation of Queue

GeeksforGeeks

Improve

Previous Article

Introduction and Array Implementation of Queue

Applications, Advantages and Disadvantages of Queue

Similar Reads

Should we declare as Queue or Priority Queue while using Priority Queue in Java?

Queue: Queue is an Interface that extends the collection Interface in Java and this interface belongs to java.util package. A queue is a type of data structure that follows the FIFO (first-in-first-out ) order. The queue contains ordered elements where insertion and deletion of elements are done at different ends. Priority Queue and Linked List are

Circular Linked List Implementation of Circular Queue

Prerequisite – Circular Singly Linked List We have discussed basics and how to implement circular queue using array in set 1. Circular Queue | Set 1 (Introduction and Array Implementation) In this post another method of circular queue implementation is discussed, using Circular Singly Linked List. Operations on Circular Queue: Front:Get the front i

What is Priority Queue | Introduction to Priority Queue

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values. In a priority queue, each element has a priority value associated with it. When you add an element to the queue, it is inserted in a position based on its

Stack and Queue in Python using queue Module

A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generally created in languages such as C/C++ and Java. 1.

Check if a queue can be sorted into another queue using a stack

Given a Queue consisting of first n natural numbers (in random order). The task is to check whether the given Queue elements can be arranged in increasing order in another Queue using a stack. The operation allowed are: Push and pop elements from the stack Pop (Or Dequeue) from the given Queue. Push (Or Enqueue) in the another Queue. Examples : Inp

Reversing a Queue using another Queue

Given a queue. The task is to reverse the queue using another empty queue. Examples: Input: queue[] = {1, 2, 3, 4, 5} Output: 5 4 3 2 1 Input: queue[] = {10, 20, 30, 40} Output: 40 30 20 10 Approach: Given a queue and an empty queue.The last element of the queue should be the first element of the new queue.To get the last element there is a need to

Advantages of circular queue over linear queue

Linear Queue: A Linear Queue is generally referred to as Queue. It is a linear data structure that follows the FIFO (First In First Out) order. A real-life example of a queue is any queue of customers waiting to buy a product from a shop where the customer that came first is served first. In Queue all deletions (dequeue) are made at the front and a

Difference between Queue and Deque (Queue vs. Deque)

Queue: The queue is an abstract data type or linear data structure from which elements can be inserted at the rear(back) of the queue and elements can be deleted from the front(head) of the queue. The operations allowed in the queue are:insert an element at the reardelete element from the frontget the last elementget the first elementcheck the size

Why can't a Priority Queue wrap around like an ordinary Queue?

Priority Queue: A priority queue is a special type of queue in which each element is assigned a priority value. And elements are served based on their priority. This means that elements with higher priority are served first. However, if elements with the same priority occur, they will be served in the order in which they were queued. A priority que

Can we use Simple Queue instead of Priority queue to implement Dijkstra's Algorithm?

What is Dijkstra's Algorithm? Dijkstra's Algorithm is used for finding the shortest path between any two vertices of a graph. It uses a priority queue for finding the shortest path. For more detail, about Dijkstra's Algorithm, you can refer to this article. Why Dijkstra's Algorithm uses a Priority Queue? We use min heap in Dijkstra's Algorithm beca

Article Tags :

Practice Tags :