Implementation of Queue using Linked list

Introduction 

In this article, we will look at how to create a queue data structure in C using Linked List. Using a linked list implies that we'll be storing data in the form of nodes that match the Queue's rules. According to the queue rule, insertion occurs at one end, and deletion occurs at the other, i.e., First In, First Out (FIFO).

A queue is a linear Data Structure that operates on the concept of first-in, first-out (FIFO). Enqueue and dequeue activities are supported by Queue. The advantage of utilizing linked lists instead of arrays to create a queue is that it allows the Queue to grow as needed, i.e., memory may be allocated dynamically.

Insertion Algorithm 

• Make a new pointer for a node.
   
• Now there are two possibilities: either the queue is empty or the queue has at least one piece.
   
• If the queue is empty, the new node will be both front and rear, with the next pointer of both front and rear pointing to NULL.
   
• The condition front == NULL becomes false if the queue has at least one element. As a result, direct the next pointer of the rear to the newly generated node ptr and the rear pointer to the newly created node ptr.

Implementation in C

#include <stdio.h>
#include <stdlib.h>

struct node {
int val;
struct node* next;
};
/* Creating structure for rear and front*/
struct node* rear;
struct node* front;


/* creating separate inserting function */
void insertfun(struct node *pt, int item) {

pt = (struct node *) malloc (sizeof(struct node));
if (pt == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
pt -> val = item;
if (front == NULL) {
front = pt;
rear = pt;
front -> next = NULL;
rear -> next = NULL;
} else {
rear -> next = pt;
rear = pt;
rear->next = NULL;
}
}
}

int main() {
struct node* head = NULL;
insertfun(head, 10);
insertfun(head, 20);
/* Printing function use to show the output*/
printf("front element: %d", front->val);
return 0;
} 

Output

front element: 10

Deletion Algorithm

• Check to see if the queue is empty.
   
• We just print 'underflow' on the screen and quit if the Queue is empty, i.e., front==NULL.
   
• Delete the element at which the front pointer is pointing if the queue is not empty. To delete a node, copy the front pointer's node into the pointer ptr, make the front pointer refer to the front's next node, and release the node indicated by the node ptr. The following sentence may be used to do this:
   

#include <stdio.h>
#include <stdlib.h>

struct node {
int val;
struct node* next;
};

struct node* front;
struct node* rear;

/* creating separate inserting function */
void insertfun(struct node *pt, int item) {

pt = (struct node *) malloc (sizeof(struct node));
if (pt == NULL) {
printf("\nOVERFLOW\n");
return;
} else {
pt -> val = item;
if (front == NULL) {
front = pt;
rear = pt;
front -> next = NULL;
rear -> next = NULL;
} else {
rear -> next = pt;
rear = pt;
rear->next = NULL;
}
}
}
/* creating septate function for deletion of node*/
void deleteNode (struct node *pt) {  
    if (front == NULL) {  
        printf("Underflow");  
        return;  
    } else {  
        pt = front;  
        front = front -> next;  
        free(pt);  
    }  
}  
/*main function */ 
int main() {
struct node* head = NULL;
insertfun(head, 10);
insertfun(head, 20);
/* Printing function use to show the output*/
      printf("front element: %d\n", front->val);
deleteNode(head); 
printf("front element: %d", front->val);
return 0;
}

Output

front element: 10
front element: 20

Queue's Applications

• Processes and threads are scheduled in the operating system.
   
• CPU and disc scheduling are two different types of scheduling.
   
• Files will be queued to be printed in the Printer.
   
• When data is transmitted between two processes asynchronously (data is not necessarily received at the same pace as it is sent). IO Buffers, pipelines, and file IO are just a few examples.

Complexity

Time Complexity: 

O(1) is the Time complexity of EnQueue and DeQueue operations.

O(n) is traversing to print each n(number of elements), the time complexity of the Display operation.

Space Complexity:

O(n) The space complexity is O(n), where n is the number of elements.

Frequently asked questions

Is it possible to use a linked list to implement a queue?

A linked list data structure can be used to build a queue data structure. The linked list queue can handle a limitless number of values. That is to say, a queue utilizing a linked list can handle data of varying sizes (No need to fix the size at the beginning of the implementation).

Is it possible to implement a stack using a queue?

The first element is withdrawn from the stack (Out) and might be the final thing inserted at the top of the stack (In). A Queue class extends the Collection interface and offers first-in-first-out insert and delete actions (FIFO). In the program below, we may also implement a Stack using Queue.

What is an example of FIFO?

Consider what would happen if a corporation bought 100 products for $10 each, then bought 100 more for $15 each. The firm then sold 60 goods. Because the first goods acquired are the first goods sold, the cost of goods sold for each of the 60 items is $10/unit using the FIFO technique.

What is an example of a linked list in practice?

A line for a cashier is the archetypal real-life example. A stack can also be implemented using a linked list. One of those plate dispensers at a buffet restaurant that pulls the top plate off the top of the stack would be a good analogy.

Is it true that a linked list is LIFO?

The sequence in which elements are placed into LinkedList is preserved.
The LinkedList class can represent a first-in, first-out (FIFO) or last-in, first-out (LIFO) storage system.

Conclusion

This article has gone through The First in, First Out Principle that governs a queue, a linear data structure (FIFO). Concept of first-in, first-out (FIFO). Queue supports Enqueue and dequeue activities. 

Want to learn more about the Data Structure in java? Click here.

Check out the Queue implementation and also the Advantages of Circular Queue. It will clear the concept.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?

Please go check out our Operating system course. 

Attempt our Online Mock Test Series on CodeStudio now!

Ninja, have a great time learning.