Queue Linked List Implementation

Last Updated on March 12, 2022 by Ria Pathak

Problem Statement

We need to implement basic functionalities of a queue using a linked list.

A queue is a linear data structure that allows elements to be added and deleted on the first in first out principle (FIFO) i.e., the element added first will be accessible before elements added after it.

Some basic functionalities of a queue are:

1) enQueue – This function takes an integer as input and adds it to the queue.
2) deQueue – This function deletes an element from the queue.
3) front – This function will give the element that is present in front of the queue.
4) rear – This function will give the data present at the end of the queue.
5) size – This function will return the number of elements in the queue.
6) isEmpty – This function returns true when the list is empty and returns false otherwise.

Approach

• We will use a singly linked list to implement the queue.
• We will keep track of two pointers, i.e., the head and tail node of the list, which will act as front and rear of the queue, respectively.
• Furthermore, we need to maintain a size variable as well to keep track of the present size of the list.
• If we want to add an element to the list (enQueue operation), we will insert it at the end of the list, i.e., after the tail of the list, and the addition of an element increases the size of the queue by one.
• If we want to remove an element from the list (deQueue operation), we will remove the head node of the list, and the removal of an element decreases the size of the queue by one.

Queue Operations

At first, we will define a class of Queue which will contain a head pointer, a tail pointer and an integer variable named size.

enQueue Operation

1) First, we will create a new node having the data passed in the function while calling.
2) Then, we will increment the size variable by one.
3) Then, we will check if tail is NULL.

• If it is NULL, that means the list is empty, so we need to update the head as well as the tail node with the newly created node and finally return.
• Else, we will insert the new node after the tail node as tail->next = new_node.
• Then, we will update tail with the newly created node.
  

  Function Implementation

  • C++

  void enQueue(int x){
      // create the new node with 'x'
      // as data
      Node* new_node = new Node(x);
  
      // increment the 'size' by one
      ++size;
      // When queue is empty, update
      // both 'head' and 'tail'
      if (tail == NULL) {
          head = tail = new_node;
          return;
      }
  
      // Insert the new node after 'tail'
      tail->next = new_node;
      // update the 'tail' with new node's
      // address
      tail = new_node;
  }
  

Time Complexity: O(1), as we are only changing few pointers.

deQueue Operation

1) If the head is NULL, we need to return from the function, as the list is empty and there is nothing to delete.
2) We will decrement the size variable by one.
3) Now, we will store the address of head in another variable, say temp.
4) Then, we need to update the head with head->next.
5) Now, If head is NULL, that means the list is empty so, we need to make the tail NULL.
6) Now, we will delete the temp node to free the memory used by the temp node.

Function Implementation

void deQueue(){
    // If queue is empty, return NULL.
    if (head == NULL)
        return;
    // decrement the 'size' by one
    --size;
    // Store previous head and
    // move head one node ahead
    Node* temp = head;
    head = head->next;

    // If head becomes NULL, then
    // change tail also as NULL
    if (head == NULL)
        tail = NULL;

    delete (temp);
}

Time Complexity: O(1), as we are only changing few pointers.

front Operation

1) We will check if the size is zero.

• If the size is zero, we will simply return -1 from the function, i.e., the queue is empty as there is no node in the list.
• Else, we will return the data of the head node.

Function Implementation

int front(){
    if(size == 0) return -1;
    return (head->data);
}

Time Complexity: O(1), as we only checking if size is zero or not.

rear Operation

1) We will check if the size is zero.

• If the size is zero, we will simply return -1 from the function, i.e., the queue is empty as there is no node in the list.
• Else, we will return the data of the tail node.

Function Implementation

int rear(){
    if(size == 0) return -1;
    return (tail->data);
}

Time Complexity: O(1), as we only checking if size is zero or not.

size Operation

• We need to simply return the size from the function.

isEmpty Operation

• We will return true if the size is zero and false otherwise.

Dry Run

Code Implementation

#include 
using namespace std;

class Node {
    public:
    int data;
    Node* next;
    Node(int d)
    {
        data = d;
        next = NULL;
    }
};

class Queue {
    public:
    Node *head, *tail;
    int size;
    Queue()
    {
        head = tail = NULL;
        size = 0;
    }

    void enQueue(int x)
    {
        // create the new node with 'x'
        // as data
        Node* new_node = new Node(x);

        // increment the 'size' by one
        ++size;
        // When queue is empty, update
        // both 'head' and 'tail'
        if (tail == NULL) {
            head = tail = new_node;
            return;
        }

        // Insert the new node after 'tail'
        tail->next = new_node;
        // update the 'tail' with new node's
        // address
        tail = new_node;
    }

    // Function to remove
    // a key from given queue q
    void deQueue()
    {
        // If queue is empty, return NULL.
        if (head == NULL)
            return;
        // decrement the 'size' by one
        --size;
        // Store previous head and
        // move head one node ahead
        Node* temp = head;
        head = head->next;

        // If head becomes NULL, then
        // change tail also as NULL
        if (head == NULL)
            tail = NULL;

        delete (temp);
    }

    // this function returns true when list is empty
    // and returns false otherwise
    bool isEmpty(){
        return (size==0);
        }

    // this function returns front element 
    // of the queue
    int front(){
        if(size == 0) return -1;
        return (head->data);
    }
    // this function returns rear element 
    // of the queue
    int rear(){
        if(size == 0) return -1;
        return (tail->data);
    }
};

// Driven Program
int main()
{

    Queue list_queue;
    list_queue.enQueue(5);
    list_queue.enQueue(8);
    list_queue.enQueue(3);
    cout<<"Size of list after inserting three elements "<<(list_queue.size)<<"\n";
    list_queue.deQueue();
    cout<<"Front element of the list is "<

						 

Output

Size of list after inserting three elements 3
Front element of the list is 8
Rear element of the list is 3

Time Complexity: All the above operations have a time complexity of O(1), as we are only changing few pointers in the above operation and also there is no loop in any of the above operations.

[forminator_quiz id=”5278″]

So, in this blog, we have tried to explain how you can implement a queue using Linked List most optimally. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.