Codewhoop

# Queue using linked list

  • Queue is a linear data structure which follows FIFO i.e. First-In-First-Out method.

  • The two ends of a queue are called Front and Rear, where Insertion always takes place at the Rear and the elements are accessed or removed from the Front.

  • While implementing queues using arrays:

    1. We cannot increase the size of array, if we have more elements to insert than the capacity of array.
    2. If we create a very large array, we will be wasting a lot of memory space.

  • Therefore if we implement Queue using Linked list we can solve these problems, as in Linked list Nodes are created dynamically as an when required.

  • So using a linked list we can create a Queue of variable size and depending on our need we can increase or decrease the size of the queue.

  • Thus instead of using the head pointer with Linked List, we will use two pointers, front and rear to keep track of both ends of the list, so that we can perfrom all the operations in O(1).

# Source Code - C++

#include <iostream>
using namespace std;

// Structure of Node.
struct Node
{
int data;

Node *link;
};

Node *front = NULL;
Node *rear = NULL;

//Function to check if queue is empty or not
bool isempty()
{
 if(front == NULL && rear == NULL)
 return true;
 else
 return false;
}

//function to enter elements in queue
void enqueue ( int value )
{
 Node *ptr = new Node();
 ptr->data= value;
 ptr->link = NULL;

 //If inserting the first element/node
 if( front == NULL )
 {
  front = ptr;
  rear = ptr;
 }
 else
 {
  rear ->link = ptr;
  rear = ptr;
 }
}

//function to delete/remove element from queue
void dequeue ( )
{
 if( isempty() )
 cout<<"Queue is empty\n";
 else
 //only one element/node in queue.
 if( front == rear)
 {
  free(front);
  front = rear = NULL;
 }
 else
 {
  Node *ptr = front;
  front = front->link;
  free(ptr);
 }
}

//function to show the element at front
void showfront( )
{
 if( isempty())
 cout<<"Queue is empty\n";
 else
 cout<<"element at front is:"<<front->data;
}

//function to display queue
void displayQueue()
{
 if (isempty())
  cout<<"Queue is empty\n";
 else
 {
  Node *ptr = front;
  while( ptr !=NULL)
  {
   cout<<ptr->data<<" ";
   ptr= ptr->link;
  }
 }
}

//Main Function
int main()
{
 int choice, flag=1, value;
 while( flag == 1)
 {
  cout<<"\n1.enqueue 2.dequeue 3.showfront 4.displayQueue 5.exit\n";
  cin>>choice;
  switch (choice)
  {
  case 1: cout<<"Enter Value:\n";
          cin>>value;
          enqueue(value);
          break;
  case 2: dequeue();
          break;
  case 3: showfront();
          break;
  case 4: displayQueue();
          break;
  case 5: flag = 0;
          break;
  }
 }

 return 0;
}

Time Complexity - Each Operation is O(1)