You're online now.

Hurray! you are online now.

# 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 operation.

## What is Queue?

Queue is linear data structures that follows the first in, first our 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 nest points to the node containing the next item. There are two pointers in a linked queue, namely 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 the 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

1. Insertion operation
2. Deletion operation

## Insertion in Queue

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

## Algorithm to perform 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 read will be NULL if the queue is empty.
``````*ptr -> data = val;
if(front == NULL){
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}``````
1. If there is at least one element in the queue, then the condtion 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){
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(){

printf("Front element of the queue %d\n", front -> data);
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.

## Enqueue function (PUSH Function)

The enqueue(PUSH) function adds an element to the end of the queue. It takes O(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 of 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.

## 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 empty 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).

## 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 empty print “No element in the queue”.
• Else, define a node pointer and initilize 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 langauge

``````// 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){
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
{
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
default:
break;
}
printf("\nDo You want to perform more Operation press[y/Y] : ");
scanf("%s", &ch);
} while (ch=='y' || ch=='Y');

return 0;
}``````
🖤 0