Implement queue using linked list C program

In computing, queue is linear data structures that follow the First In, First Out (FIFO) principle. They are used to perform enqueuing and dequeuing operations.

What  is queue?

Queue is linear data stuctures that follows the first in, first out principle (FIFO), which means that the element added first to the queue will be the first removed.

Operation Queue using Linked List.

A linked queue consists of two fields: data and next (storing address of next node). The data field contains the value assigned to the node, and the next points to the node containing the next item.

There are two pointers in a linked queue, namely the front pointer and the rear pointer. The front pointer contains the address of the first element of the queue, while the rear pointer contains the address of the last element.

When both front and rear points to NULL, it indicates that the queue is empty. Insertion takes place at the rear end and deletion at the front.

The two main operation performed on the linked queue are:

• Insertion operation
• Deletion operation

Insertion in queue

When an element is inserted into a linked queue, a new element is added to the end. This element becomes the queue's last element.

Algorithm to perfrom the insertion on a linked queue:

1. Create a new node pointer. Using ptr =(struct node*)malloc(sizeof(struct node));
2. In this case, either the queue contains at least one element, or the queue is empty.
3. The new node added will be both front and rear, and the next pointer of front and rear will be NULL if the queue is empty.

   *ptr -> data = val;
   
   if(front == NULL){
       front = ptr;
       rear = ptr;
       front -> next = NULL;
       rear -> next = NULL;
   }

4. If there is at least one element in the queue, then the condition front == NULL becomes false. So, point the next pointer of rear to the newly created node pointer.

   rear -> next = ptr;
   rear = ptr;

C program of insertion operation on linked queue.

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

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

struct node *front;
struct node *rear;

void insert(struct node *ptr, int item){
    ptr = (struct node*) malloc(sizeof(struct node));
    if(ptr == NULL){
        printf("\nQUEUE OVERFLOW");
        return;
    }else{
        ptr -> data = item;
        if(front == NULL){
            front = ptr;
            rear = ptr;
            front -> next = NULL;
            rear -> next = NULL;
        }else{
            rear -> next = ptr;
            rear = ptr;
            rear -> next = NULL;
        }
    }
}

int main(){
    struct node *head = NULL;
    insert(head, 12);
    insert(head, 89);
    printf("Front element of the queue %d", front -> data);
    return 0;
}

Deletion in queue:

Whenever a linked queue is deleted, the first element of the queue is removed, i.e., always the first element of the queue is deleted.

Algorithm to perfrom the d deletion  a linked queue:

1. Check if the queue is empty or not.
2. If the queue is empty, i.e., front == NULL, so we just print 'QUEUE IS EMPTY' on the screen and exit.
3. When the queue is not empty, delete the element at which the front pointer is pointing. To delete a node, copy it into the pointer ptr and make the fron pointer point to the front's next node.This can be done using the following statement:

   *ptr = front;
   front = front -> next;
   free(ptr);

C program of insertion operation on linked queue.

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

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

struct node *front;
struct node *rear;

void insert(struct node *ptr, int item){

    ptr = (struct node *) malloc (sizeof(struct node));
    if(ptr == NULL){
        print("\nQUEUE IS OVERFLOW");
        return;
    }else{
        ptr -> data = item;
        if(front == NULL){
            front = ptr;
            rear = ptr;
            front -> next = NULL;
            rear -> next = NULL;
        }else{
            rear -> next = ptr;
            rear = ptr;
            rear -> next = NULL;
        }
    }
}
void delete(struct node *ptr){
    if(front == NULL){
        printf("\nQUEUE IS EMPTY");
        return;
    }else{
        ptr = front;
        front = front -> next;
        free(ptr);
    }
}

int main(){
    struct node *head = NULL;
    insert(head, 12);
    insert(head, 34);
    insert(head, 7);

    printf("Front element of the queue %d\n", front -> data);
    delete(head);
    printf("Front element of the queue %d\n", front -> data);
    return 0;
}

Implementation of queue using linked list in C programming

By implementing a queue using a linked list, we can allocate memory dynamically as needed.

When implement a queue using a linked list, the FIFO principle will not change.

1. Enqueue Function (PUSH Function)

The enqueue (push) function adds an element to the end of the queue. It takes 0(1) time. A rear pointer can be used to track the last element.

• First, build a new node with given data.
• Check if the queue is empty or not.
• If a queue is empty then, a new node is assigned to the front and rear.
• Else make next of rear as new node and rear as a new node.

2. Dequeue Function (POP Function)

A dequeue function removes the first element of a queue in O(1) time. To dequeue, the queue must contain at least one element, otherwise an underflow will occur.

• Check if queue is empth or not.
• If the queue is empty, then dequeue is not possible.
• Else store front in temp
• And make next of front as the front.
• Delete temp, i.e., free(temp).

3. Print function (Display function)

We use the print function to display the content of a queue. Since we iterate over each element of the queue, the time complexity of the print function is O(n).

• Check if queue contains at least one element or not.
• If the queue is empth print "No element in the queue."
• Else, define a node pointer and initialize it with the front.
• Display data of node pointer until the next node pointer becomes NULL.

Code for implementing queue using linked list in c programming language

Method 1:

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

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

struct node * front = NULL;
struct node * rear = NULL;

void enqueue(int value){
    struct node *ptr;
    ptr = (struct node*) malloc(sizeof(struct node));
    ptr -> data = value;
    ptr -> next = NULL;
    if((front == NULL) && (rear == NULL)){
        front = rear = ptr;
    }else{
        rear -> next = ptr;
        rear = ptr;
    }
    printf("\nNode is Inserted\n");
}

int dequeue(){
    if(front == NULL){
        printf("\nQUEUE IS EMPTY");
        return -1;
    }else{
        struct node *temp = front;
        int temp_data = front -> data;
        front = front -> next;
        free(temp);
        return temp_data;
    }
}

void display(){
    struct node *temp;
    if((front == NULL) && (rear == NULL)){
        printf("\nQUEUE IS EMPTY");
    }else{
        printf("The Queue is \n\n");
        temp = front;
        while(temp){
            printf("%d-->", temp -> data);
            temp = temp -> next;
        }
        printf("NULL\n\n");
    }
}

int main(){
    int choice, value;
    printf("\nImplementation of Queue using Linekd List\n");
    while(choice != 4){
        printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n\nEnter your choice : ");
        scanf("%d", &choice);

        switch(choice){
            case 1:
                printf("\nEnter the value to insert : ");
                scanf("%d", &value);
                enqueue(value);
                break;
            case 2:
                printf("Popped Elemetn is : %d\n", dequeue());
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
                break;
            default:
                printf("\nWrong Choice\n");
        }
    }
    return 0;
}

Method 2:

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

struct node{
    int data;
    struct node *next;
};
typedef struct node NODE;
NODE  *front = NULL, *rare = NULL;


void push(){
    NODE *ptr;
    int item;
    printf("\nEnter the item : ");
    scanf("%d", &item);
    ptr = (NODE*)malloc(sizeof(NODE));
    ptr->data = item;
    ptr->next = NULL;

    if(front==NULL){
        front = ptr;
        rare = ptr;
    }
    else{
        rare->next = ptr;
        rare = ptr;
    }
}

void display(){
    NODE *temp=front;
    while (temp!=rare)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
    
}
void pop(){
    NODE *temp = front;
    while(temp->next != rare){
        temp = temp->next;
    }
    temp->next = NULL;
    free(rare);
    rare = temp;
}
int main(){

    char ch;
    int choice;
    do
    {
        printf("\n1.PUSH\n2.POP\n3.Display\nEnter Your Choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            display();
            break;        
        default:
            printf("Please Choose Right Option\n");
            break;
        }
        printf("\nDo You want to perform more Operation press[y/Y] : ");
        scanf("%s", &ch);
    } while (ch=='y' || ch=='Y');
    
    return 0;
}

Please Comment Now...