{"id":5276,"date":"2021-09-27T19:49:00","date_gmt":"2021-09-27T19:49:00","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5276"},"modified":"2022-03-12T00:19:01","modified_gmt":"2022-03-12T00:19:01","slug":"queue-linked-list-implementation","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/queue-linked-list-implementation\/","title":{"rendered":"Queue Linked List Implementation"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

We need to implement basic functionalities of a queue using a linked list.<\/p>\n<\/p>\n

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.<\/p>\n

Some basic functionalities of a queue are:<\/h4>\n

1) enQueue<\/strong> – This function takes an integer as input and adds it to the queue.
\n2) deQueue<\/strong> – This function deletes an element from the queue.
\n3) front<\/strong> – This function will give the element that is present in front of the queue.
\n4) rear<\/strong> – This function will give the data present at the end of the queue.
\n5) size<\/strong> – This function will return the number of elements in the queue.
\n6) isEmpty<\/strong> – This function returns true when the list is empty and returns false otherwise.<\/p>\n

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

    Queue Operations<\/h3>\n

    At first, we will define a class of Queue which will contain a head pointer, a tail pointer and an integer variable named size.<\/p>\n

    enQueue Operation<\/h4>\n

    1) First, we will create a new node having the data passed in the function while calling.
    \n2) Then, we will increment the size<\/strong> variable by one.
    \n3) Then, we will check if tail<\/strong> is NULL.<\/p>\n

      \n
    • If it is NULL, that means the list is empty, so we need to update the head<\/strong> as well as the tail<\/strong> node with the newly created node and finally return.<\/li>\n
    • Else, we will insert the new node after the tail<\/strong> node as tail->next = new_node<\/strong>.<\/li>\n
    • Then, we will update tail<\/strong> with the newly created node.
      \n
      Function Implementation<\/h5>\n\t\t\t\t\t\t