Queue using linked listQueue using an array - drawbackIf we implement the queue using an array, we need to specify the array size at the beginning(at compile time). Show We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements. SolutionWe can implement the queue data structure using the linked list. In the linked list, we can change its size at runtime. Let's implement the queue using linked listIf you are not familiar with linked list and queue, kindly visit the below links before we get started. Linked List BasicsQueue using array Node structure for Queuestruct node
{
int data;
struct node *next;
};
To point the front and rear nodestruct node *front = NULL, *rear = NULL;
Enqueue functionEnqueue function will add the element at the end of the linked list. Using the rear pointer, we can track the last inserted element. 1. Declare a new node and allocate memory for it. 2. If front == NULL, make both front and rear points to the new node. 3. Otherwise, add the new node in rear->next. make the new node as the rear node. i.e. rear = new node void enqueue(int val)
{
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;
//if it is the first node
if(front == NULL && rear == NULL)
//make both front and rear points to the new node
front = rear = newNode;
else
{
//add newnode in rear->next
rear->next = newNode;
//make the new node as the rear node
rear = newNode;
}
}
Visual representation of the above algorithmInsert 10 Insert 20Insert 30Dequeue functionDequeue function will remove the first element from the queue. 1.Check whether the queue is empty or not 2.If it is the empty queue (front == NULL) We can't dequeue the element. 3.Otherwise, Make the front node points to the next node. i.e front = front->next; if front pointer becomes NULL, set the rear pointer also NULL. Free the front node's memory. void dequeue()
{
//used to freeing the first node after dequeue
struct node *temp;
if(front == NULL)
printf("Queue is Empty. Unable to perform dequeue\n");
else
{
//take backup
temp = front;
//make the front node points to the next node
//logically removing the front element
front = front->next;
//if front == NULL, set rear = NULL
if(front == NULL)
rear = NULL;
//free the first node
free(temp);
}
}
Implementation of the queue using linked list/*
* Program : Queue using linked list
* Language : C
*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front = NULL, *rear = NULL;
void enqueue(int val)
{
struct node *newNode = malloc(sizeof(struct node));
newNode->data = val;
newNode->next = NULL;
//if it is the first node
if(front == NULL && rear == NULL)
//make both front and rear points to the new node
front = rear = newNode;
else
{
//add newnode in rear->next
rear->next = newNode;
//make the new node as the rear node
rear = newNode;
}
}
void dequeue()
{
//used to free the first node after dequeue
struct node *temp;
if(front == NULL)
printf("Queue is Empty. Unable to perform dequeue\n");
else
{
//take backup
temp = front;
//make the front node points to the next node
//logically removing the front element
front = front->next;
//if front == NULL, set rear = NULL
if(front == NULL)
rear = NULL;
//free the first node
free(temp);
}
}
void printList()
{
struct node *temp = front;
while(temp)
{
printf("%d->",temp->data);
temp = temp->next;
}
printf("NULL\n");
}
int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
printf("Queue :");
printList();
dequeue();
printf("After dequeue the new Queue :");
printList();
dequeue();
printf("After dequeue the new Queue :");
printList();
return 0;
}
Run it Page -- Page ++ Topics You Might Like |
