Queue Using Linked List


A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning that the element that is inserted first will be the first one to be removed. Think of it like a real-world queue, such as people waiting in line; the first person who joins the queue is the first one to be served.

Implementing a queue using a linked list involves defining a structure for the nodes of the linked list and implementing functions to perform queue operations like enqueue (insertion) and dequeue (deletion)

Defining the node and Initializing the queue
struct Node
{
 int data;
 struct Node *next;
}*front=NULL,*rear=NULL;

Enqueue (Insertion) Algorithm:

1.Create a new node:
    Allocate memory for a new node.
    Set the data field of the new node with the given element.

2.Update pointers:
    If the queue is empty, set both the front and rear pointers to the new node.
    Otherwise, set the next pointer of the current rear node to the new node.
    Update the rear pointer to the new node.

void enqueue()
{
 struct Node *newnode=(struct Node*)malloc(sizeof(struct Node));
 printf("Enter data:");
 scanf("%d",&newnode->data);
 newnode->next=NULL;
 if(front==NULL)
 {
  front=newnode;
  rear=newnode;
 }
 else
 {
  rear->next=newnode;
  rear=newnode;
 }
}

Dequeue (Deletion) Algorithm:

1.Check for an empty queue:
    If the queue is empty, print an error message or return a special value to indicate an empty queue.

2.Retrieve data and update pointers:
    Retrieve the data from the front node.
    Move the front pointer to the next node.
    If the front becomes NULL (indicating the queue is now empty), update the rear pointer to NULL as     well.

3.Free memory:
    Free the memory occupied by the node that was dequeued.
int dequeue()
{
    if (front==NULL)
       {printf("Queue is empty...underflow");return -1;}
    else
    {
     struct Node *temp;
     temp=front;
     int rv=front->data;
     front=front->next;
     if(front==NULL) rear=NULL;
     free(temp);
     return(rv);
    }
}

Display Algorithm for Queue Using Linked List:

1.Check if the queue is empty:
    If the front pointer is NULL, print "Queue is empty."

2.Traverse the linked list from front to rear:
    Initialize a temporary pointer to the front of the queue.
    While the temporary pointer is not NULL:
        Print the data of the current node.
        Move the temporary pointer to the next node.
void displayQ()
{
 struct Node *temp=front;
 while(temp!=NULL)
 {
  printf(" %d---->",temp->data);
  temp=temp->next;
 }
 printf(" NULL");
}

Complexity Analysis

let's analyze the time and space complexity of the enqueue, dequeue, and display operations in a queue implemented using a linked list.

Time Complexity

Enqueue (Insertion):Time complexity: O(1)
Enqueuing involves creating a new node and updating the rear pointer. Since these operations take a constant amount of time, the time complexity is constant.

Dequeue (Deletion):Time complexity: O(1)
Dequeuing involves updating the front pointer and freeing the memory of the dequeued node. These operations also take a constant amount of time.

Display:Time complexity: O(n)
Displaying all elements of the queue requires traversing the linked list from the front to the rear. In the worst case, where there are n elements in the queue, this takes O(n) time.

Space Complexity

Enqueue (Insertion):Space complexity: O(1)
Enqueuing involves creating a new node, which takes constant space.

Dequeue (Deletion):Space complexity: O(1)
Dequeuing involves freeing the memory of the dequeued node, which also takes constant space.

Display:Space complexity: O(1)
Explanation: The space required for displaying the queue elements is constant, as it does not depend on the size of the queue.

The linked list-based implementation of a queue provides efficient enqueue and dequeue operations with a constant time complexity of O(1). Displaying the entire queue takes O(n) time, where n is the number of elements in the queue. The space complexity for all operations is constant (O(1)) as each node consumes a fixed amount of memory.

These complexities make linked list-based queues a good choice for scenarios where frequent enqueue and dequeue operations are expected, and the size of the queue is not too large.

Queue using linked List - C Implementation
/*******************************************************************************/
#include<stdio.h>

#include<conio.h>
#include <stdlib.h>
struct Node
{
 int data;
 struct Node *next;
}*front=NULL,*rear=NULL;
void enqueue()
{
 struct Node *newnode=(struct Node*)malloc(sizeof(struct Node));
 printf("Enter data:");
 scanf("%d",&newnode->data);
 newnode->next=NULL;
 if(front==NULL)
 {
  front=newnode;
  rear=newnode;
 }
 else
 {
  rear->next=newnode;
  rear=newnode;
 }
}
int dequeue()
{
    if (front==NULL)
       {printf("Queue is empty...underflow");return -1;}
    else
    {
     struct Node *temp;
     temp=front;
     int rv=front->data;
     front=front->next;
     if(front==NULL) rear=NULL;
     free(temp);
     return(rv);
    }
}
void displayQ()
{
 struct Node *temp=front;
 while(temp!=NULL)
 {
  printf(" %d---->",temp->data);
  temp=temp->next;
 }
 printf(" NULL");
}
void main()
{
 int ch;
 
 do
 {
  printf("\nMenu\n----\n1.Enqueue\n2.Dequeue\n3.Display\n4.Exit");
  printf("\nEnter the choice:");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
        enqueue();
        displayQ();
         break;
   case 2:
        int data;
        data=dequeue();
        if(data!=-1)
            printf("The dequed data is:%d\n",data);
        displayQ();
        break;
   case 3:
    displayQ();
    break;
   case 4:
    exit(0);
   default:
    printf("There is no such operation:");
  }
 }
 while(1);
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Stack

Image
A stack is a fundamental data structure in computer science and programming that follows the Last-In, First-Out (LIFO) principle . It is named "stack" because it resembles a stack of items, like a stack of plates or books, where you can only add or remove items from the top. Stacks are used for various purposes in programming and are essential in many algorithms and applications. Let's delve into the details of stacks: Key Operations:  A stack typically supports two primary operations: Push: This operation adds an element to the top of the stack. It is analogous to placing an item on top of the stack. Pop: This operation removes and returns the top element of the stack. It is like taking the top item off the stack. Additionally, stacks often provide the following operations: Peek (or Top): This operation retrieves the top element without removing it. It allows you to examine the top item without modifying the stack. IsEmpty: This operation checks if the stack is empty.
Read more

Quick Sort

Quick sort is a popular sorting algorithm that uses a divide-and-conquer strategy to efficiently sort an array or list. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted. Here's a detailed algorithm for the Quick Sort algorithm: Algorithm: Quick Sort 1.Choose a pivot element from the array. This can be done in various ways, such as selecting the first element, the last element, or a random element. The choice of the pivot can affect the algorithm's performance. 2,Partition the array into two sub-arrays:     Elements less than the pivot (left sub-array).     Elements greater than the pivot (right sub-array). 3.Recursively apply the Quick Sort algorithm to the left and right sub-arrays. 4.Combine the sorted left sub-array, pivot, and sorted right sub-array to obtain the final sorted ar
Read more