Implement Queue using Linked List

Problem Statement: Implement Queue using Singly LinkedList

Prerequisites: Queue and LinkedList Data Structure.

Detailed Explanation of the Queue and LinkedList Data Structures is Discussed here

Queue Can be Implemented in two ways :

Static Implementation (Using Arrays)
Dynamic implementation (Using LinkedList) .

In this article, we would discuss the implementation of queue using LinkedList.

Comparison between Implementation of Queue using LinkedList and Array.

Array	LinkedList
It is Static, Needs to provide space Before implementation. Overflow occurs when queue size reaches its maximum capacity	Nodes are allocated dynamically, so the queue can grow and shrink as much as needed. Overflow is not possible until and unless the heap memory got exhausted.

Operations Associated with queue are :

Enqueue (Insert Node at Rare End )
Dequeue (Delete Node from Front )
Peek (Return value of Front Node without Dequing)
Empty (Returns True when queue is empty else False)
Size (Returns size of Queue)

Let the Initial Queue be 10→20→30→40→Null.

Enqueue:

Let’s Enqueue Node with val 50 to Queue. Enqueue is 3 step process

Create a node with a value that is to be Enqueued.
Make the Rare Pointers next, point to the newly created Node.
As the newly created Node is inserted at the rear end, this is the last value in Queue.

Dequeue :

Let’s Dequeue the front value that is, 10 from Queue.

First create a ListNode pointer temp, and make it point to the Front value of Queue.
We should delete the Front Value in Queue. So move the Front pointer to the next node after Front Node. That means Front = Front→next
Temp is pointing to the previous Front value, temp→next is pointing to the newFront value, as we are interested to delete the temp, Make the temp→next point null.
We don’t require temp anymore, So delete the temp.

Peek:

If Queue is not empty return Front value of Queue.

Empty:

If Front is Null then Queue is empty else not.

Size:

Maintain a variable size, initially set to zero. Upon Enqueue increment size and on Dequeue decrement size.

Code :

C++ Code

#include<bits/stdc++.h> 
using namespace std;

class QueueNode
{
 public: 
    int val;
    QueueNode *next;
    QueueNode(int data)
    {
       val = data;
       next = nullptr;
    }
};  
QueueNode *Front = nullptr, *Rare = nullptr;

class Queue
{
public:
    int size = 0;
    bool Empty();
    void Enqueue(int value);
    void Dequeue();
    int Peek();
};  
bool Queue ::  Empty()
{
    return Front == nullptr;
}  
int Queue :: Peek()
{
    if(Empty())  
     {  cout<<"Queue is Empty"<<endl;
        return -1;
     } 
    else 
      return Front->val;
}   
void Queue :: Enqueue(int value)
{
    QueueNode *Temp;
    Temp = new QueueNode(value); 
    if (Temp == nullptr)  //When heap exhausted 
        cout << "Queue is Full" << endl;
    else
    {
        if (Front == nullptr)
        {
            Front = Temp;
            Rare = Temp;
        } 
        else
        {
            Rare->next = Temp;
            Rare = Temp;
        }
        cout<<value <<" Inserted into Queue "<<endl;
        size++;
    } 
}      
void Queue :: Dequeue() 
{
    if (Front == nullptr) 
        cout << "Queue is Empty" << endl;
    else
    { 
        cout<<Front->val <<" Removed From Queue"<<endl;
        QueueNode *Temp = Front;
        Front = Front->next;
        delete Temp;
        size--;
    }  
}   
int main()

{
    Queue Q;
    Q.Enqueue(10);
    Q.Enqueue(20);
    Q.Enqueue(30);
    Q.Enqueue(40);
    Q.Enqueue(50);
    Q.Dequeue();
    cout<<"The size of the Queue is "<<Q.size<<endl;
    cout<<"The Peek element of the Queue is "<<Q.Peek()<<endl;
    return 0;
}

Output:

10 Inserted into Queue
20 Inserted into Queue
30 Inserted into Queue
40 Inserted into Queue
50 Inserted into Queue
10 Removed From Queue
The size of the Queue is 4
The Peek element of the Queue is 20

Time complexity: O(1).

Space Complexity: O(1)

Java Code

import java.util.*;

class QueueNode
{
    int val;
    QueueNode next;
    QueueNode(int data)
    {
       val = data;
       next = null;
    }
}  


class Queue
{
    QueueNode Front = null, Rear = null;
    int size = 0;

boolean Empty()
{
    return Front == null;
}  
int Peek()
{
    if(Empty())  
     {  System.out.println("Queue is Empty");
        return -1;
     } 
    else 
      return Front.val;
}   
void Enqueue(int value)
{
    QueueNode Temp;
    Temp = new QueueNode(value); 
    if (Temp == null)  //When heap exhausted 
        System.out.println("Queue is Full");
    else
    {
        if (Front == null)
        {
            Front = Temp;
            Rear = Temp;
        } 
        else
        {
            Rear.next = Temp;
            Rear = Temp;
        }
        System.out.println(value+" Inserted into Queue ");
        size++;
    } 
}      
void Dequeue() 
{
    if (Front == null) 
        System.out.println("Queue is Empty");
    else
    { 
        System.out.println(Front.val+" Removed From Queue");
        QueueNode Temp = Front;
        Front = Front.next;
        size--;
    }  
}  
public static void main(String args[])

{
    Queue Q=new Queue();
    Q.Enqueue(10);
    Q.Enqueue(20);
    Q.Enqueue(30);
    Q.Enqueue(40);
    Q.Enqueue(50);
    Q.Dequeue();
    System.out.println("The size of the Queue is "+Q.size);
    System.out.println("The Peek element of the Queue is "+Q.Peek());
}
}

Output:

10 Inserted into Queue
20 Inserted into Queue
30 Inserted into Queue
40 Inserted into Queue
50 Inserted into Queue
10 Removed From Queue
The size of the Queue is 4
The Peek element of the Queue is 20

Time complexity: O(1).

Space Complexity: O(1)

Special thanks to SaiSri Angajala for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article