Implementation of Queue using Linked List in C++

Queue using Linked List

In this section, we will learn how the implementation of Queue using Linked List in C++ which is dynamic in nature and it’s size is variable so we do not need to reallocate the entire Linked List. This implementation of the queue is more efficient as compared to the array implementation of the queue.

Implementation of a queue using Linked list

Steps to Implement Queue using Linked List in C++

  • We will create a Linked list to perform the operations on the queue.
  • Create a linked list to insert the elements .
  • Similarly, Perform the deletion operation in Linked List.
  • Implement all the methods of the queue in a Linked List.
 
The Linked List Implementation of queue is also better in terms of
  • space
  • memory
  • time complexity
Implementation of Queue using Linked List

Algorithm for Enqueue:-

  1. Return Queue full
  2. Else
  3. Rear+Rear+1
  4. Queue[Rear]=Data
  5. If(Front== -1)
  6. Front= 0

Algorithm for Dequeue:-

  1. If(Front==-1||Front==Rear+1)
  2. Return
  3. Else
  4. Queue[Front]=0
  5. Front=Front+1

Implementation of Queue using Linked List in C++:

Run
#include<iostream>
using namespace std;

class Node
{
public:
  int data;
  Node *next;
};

void enqueue (Node ** head, int data)
{

  Node *new_node = new Node ();

  // assign data value
  new_node->data = data;
  // change the next node of this new_node 
  // to current head of Linked List
  new_node->next = *head;

  //changing the new head to this newly entered node
  *head = new_node;

}

void dequeue (Node ** head)
{
  Node *temp = *head;

  // if there are no nodes in Linked List can't delete
  if (*head == NULL)
    {
      cout << ("Linked List Empty, nothing to delete");
      return;
    }

  // move head to next node
  *head = (*head)->next;
  //cout<< ("Deleted: %d\n", temp->data);
  delete (temp);
}

void display (Node * node)
{

  //as linked list will end when Node is Null
  while (node != NULL)
    {
      cout << node->data << " ";
      node = node->next;
    }
  cout << endl;
}

int main ()
{

  Node *head = NULL;

  enqueue (&head, 10);
  enqueue (&head, 11);
  enqueue (&head, 12);
  enqueue (&head, 13);
  enqueue (&head, 14);
  enqueue (&head, 15);
  enqueue (&head, 16);
  enqueue (&head, 17);
  enqueue (&head, 18);
  cout << "Queue before deletion: ";
  display (head);
  dequeue (&head);
  cout << endl << "Queue after deletion: ";
  display (head);
  return 0;
}
Output:-
Queue before deletion: 18 17 16 15 14 13 12 11 10 

Queue after deletion: 17 16 15 14 13 12 11 10 

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

  • Introduction to Stack in Data Structure
    Click Here
  • Operations on a Stack
    Click Here
  • Stack: Infix, Prefix and Postfix conversions
    Click Here
  • Stack Representation in –
    C | C++ | Java
  • Representation of a Stack as an Array. –
    C | C++ | Java
  • Representation of a Stack as a Linked List. –
    C | C++ | Java
  • Infix to Postfix Conversion –
    C | C++ | Java
  • Infix to prefix conversion in –
    C | C++ | Java
  • Postfix to Prefix Conversion in –
    C | C++ | Java

Queues

  • Queues in Data Structures (Introduction)
    Click Here
  • Queues Program in C and implementation
    Click Here
  • Implementation of Queues using Arrays | C Program
    Click Here
  • Types of Queues in Data Structure
    Click Here
  • Application of Queue Data Structure
    Click Here
  • Insertion in Queues Program (Enqueuing) –
    C | C++ | Java
  • Deletion (Removal) in Queues Program(Dequeuing) –
    C | C++ | Java
  • Reverse a Queue –
    C | C++ | Java
  • Queues using Linked Lists –
    C | C++ | Java
  • Implement Queue using Stack –
    C | C++ | Java
  • Implement Queue using two Stacks –
    C | C++ | Java

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction –
    C | C++ | Java
  • Priority Queue Implementation using Array –
    C | C++ | Java
  • Priority Queue using Linked List –
    C | C++ | Java
  • Priority Queue Insertion and Deletion-
    C | C++ | Java

Stacks

Queues

Circular Queues

Priority Queue

  • Application of Priority Queue
  • Priority Queue Example
  • Priority Queue Introduction – C | C++ | Java
  • Priority Queue Implementation using Array – C | C++ | Java
  • Priority Queue using Linked List – C | C++ | Java
  • Priority Queue Insertion and Deletion- C | C++ | Java