Queue using Singly Linked List Implementation (With C++ Program Code)

Understand how queue using linked list can be implemented with working & diagram simulation. In this tutorial we will implement a queue data structure using singly linked list data structure. We will make a singly linked list work like a queue which means it will work in a FIRST IN FIRST OUT (FIFO) mode. Lastly we will write a C++Program to implement this Queue using Singly Linked List.

We will also see the algorithm & pseudocode of individual queue operations like –

1. enqueue() – Add a new node from rear end.
2. dequeue() – Remove a node from front end.
3. count() – Return number of notes in the queue.
4. isEmpty() – Check if queue is empty.
5. display() – Display all nodes in the queue.
6. checkIfNodeExist() – Check if node exist in queue with same key value.

1. Queue enqueue() pseudocode –

2. Queue dequeue() pseudocode –

3. Queue count() pseudocode –

4. Queue isEmpty() pseudocode –

5. Queue checkIfNodeExist() pseudocode –

6. Queue display() pseudocode –

C++ Program of Queue using Singly Linked List –

#include<iostream>

using namespace std;

class Node {
  public:
   int key;
   int data; // value
   Node * next;

  Node() {
    key = 0;
    data = 0;
    next = NULL;
  }
  Node(int k, int d) {
    key = k;
    data = d;
    next = NULL;
  }
};

class Queue 
{
  public:
   Node *front;
   Node *rear;
   
    Queue() 
  {
      front = NULL;
      rear = NULL;
    }
    
    bool isEmpty()
    {
     if(front==NULL && rear==NULL)
     {
      return true;
  }
  else
  {
   return false;
  }
  }
  
  bool checkIfNodeExist(Node *n)
  {
   Node *temp = front;
   bool exist=false;
   while(temp!=NULL)
   {
    if(temp->key==n->key)
         {
          exist=true;
          break;
       }
       temp=temp->next;
  }
  return exist;
  }
  
 void enqueue(Node *n) 
   {
    if (isEmpty())
      {
        front = n;
        rear = n;
        cout<<"Node  ENQUEUED successfully"<<endl;
      }
    else if(checkIfNodeExist(n))
    {
      cout<<"Node already exist with this Key value." 
      <<"Enter different Key value"<<endl;
    }
    else
    {
      rear->next=n;
      rear=n;
      //top = n;
      cout<<"Node  ENQUEUED successfully"<<endl;
    }
    
   }
 
 Node* dequeue() 
    {
        Node *temp=NULL;
      if (isEmpty()) 
      {
          cout << "Queue is Empty" << endl;
          return NULL;
      } 
      else 
      {
        if(front==rear)
        {
          temp=front;
          front = NULL;
          rear = NULL;  
          return temp;
        }
        else
        {
          temp=front;
          front = front->next;  
          return temp;
        }
          
       }
    }
  
  int count() 
    {
      int count=0;
      Node *temp=front;
      while(temp!=NULL)
      {
        count++;
        temp=temp->next;
     }
     return count;
    }
  
  void display() 
    {
      if(isEmpty())
      {
        cout << "Queue is Empty" << endl;
      }
    else
    {
      cout << "All values in the Queue are :" << endl;
        Node *temp=front;
        while(temp!=NULL)
        {
          cout<<"("<<temp->key<<","<<temp->data<<")"<<" -> ";
          temp=temp->next;
       }
      cout<<endl;
    }
    
    }
  
   
};
 
int main() {
  Queue q;
  int option,key, data;
 
  do {
    cout << "What operation do you want to perform?"
  <<"Select Option number. Enter 0 to exit." << endl;
    cout << "1. Enqueue()" << endl;
    cout << "2. Dequeue()" << endl;
    cout << "3. isEmpty()" << endl;
    cout << "4. count()" << endl;
    cout << "5. display()" << endl;
    cout << "6. Clear Screen" << endl << endl;
   cin >> option;
   
   //Node n1 = new Node();
  Node * new_node = new Node();
  
    
    switch (option) {
    case 0:
      break;
    case 1:
     cout << "ENQUEUE Function Called -" <<endl;
      cout << "Enter KEY and VALUE of NODE to ENQUEUE "
  <<"in the Queue"
  <<endl;
      cin >> key;
      cin >> data;
      new_node->key = key;
      new_node->data = data;
      q.enqueue(new_node);
      break;
    case 2:
      cout << "DEQUEUE Function Called - " <<endl;
      new_node = q.dequeue();
      cout<<"Dequeued Value is: ("<<new_node->key<<","
  <<new_node->data<<")";
      delete new_node;
  cout<<endl;
      
      break;
    case 3:
     cout << "isEmpty Function Called - " << endl;
      if (q.isEmpty())
        cout << "Queue is Empty" << endl;
      else
        cout << "Queue is NOT Empty" << endl;
      break;
    case 4:
     cout << "Count Function Called - " << endl;
      cout << "No of nodes in the Queue: " <<q.count()
  <<endl;
      break;
    case 5:
      cout << "Display Function Called - " << endl;
      q.display();
      cout << endl;
      break;
    
    case 6:
      system("cls");
      break;
    default:
      cout << "Enter Proper Option number " << endl;
    }
 
  } while (option != 0);
 
  return 0;
}

YouTube video tutorial –