How To Implement Queue Using Doubly Linked List In C

In the article, we will implement queue using doubly linked list.Before moving to the conversion, firstly we will discuss the queue and doubly linked list in C as we have to implement queue using doubly linked list.

What is a Queue?

A queue is a linear data structure that follows the principle of FIFO (First in First out) i.e. element which is inserted first will be removed first. The operation for the insertion of elements is known as enqueue operation and the operation for the deletion of elements is known as dequeue operation.

Next, we’ll discuss the doubly linked list.

What is a Doubly Linked List?

A doubly Linked List is a type of linked list that contains three components:

  • *prev – It is a pointer having the address of the previous node of the linked list.
  • data – It is used to store the data of the node.
  • *next – It is a pointer having the address of the next node of the linked list.

Here is the representation of the DLL node:

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

Now, let’s discuss our main topic, how to implement queue using a doubly linked list in c.

How to implement queue using doubly linked list in c:

We will implement the following functions of queue using doubly linked list in c:

  1. Enqueue: This function is used to add an element in the queue in the rear end. There is a ref pointer of the doubly linked list which has a rear, front, and size pointer. In the case of enqueueing, we will add data in the new node and will pass it to the next pointer of the rear node. Also, we will increment the size pointer by 1 in case of insertion.
    Let’s add some nodes to the queue.

void enqueue(MyQueue * ref, int data)
{
	QNode * node = getQNode(data, ref->rear);
	if (ref->front == NULL)
	{
		ref->front = node;
		ref->size = 1;
	}
	else
	{
		ref->rear->next = node;
		ref->size = ref->size + 1;
	}
	ref->rear = node;
}
  1. Dequeue: This function is used to delete an element from the queue from the front end. From the ref, the front pointer will move to the front->next and will decrease the size pointer by 1. Also, return the data which is stored in the deleted node.

int dequeue(MyQueue * ref)
{
	if (isEmpty(ref) == 1)
	{
		return -1;
	}
	else
	{
		int data = peek(ref);
		QNode * temp = ref->front;
		if (ref->front == ref->rear)
		{
			ref->rear = NULL;
			ref->front = NULL;
		}
		else
		{
			ref->front = ref->front->next;
			ref->front->prev = NULL;
		}
		ref->size--;
		return data;
	}
}
  1. isSize: This function will return the size of the queue built using a doubly linked list in c.
int isSize(MyQueue * ref)
{
	return ref->size;
}
  1. peek: This function will return the element’s data stored in the front position of the queue.

    int peek(MyQueue * ref)
    {
    	if (isEmpty(ref) == 1)
    	{
    		printf("\n Empty Queue");
    		// When stack is empty
    		return -1;
    	}
    	else
    	{
    		return ref->front->data;
    	}
    }
    

  2. isEmpty: This function will return true if the element queue is empty else it will return false.

int isEmpty(MyQueue * ref)
{
	if (ref->size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
  1. printQdata: This function will print all the node’s data of the queue.

How To Implement Queue Using Doubly Linked List In C 7

void printQdata(MyQueue * ref)
{
	QNode * node = ref->front;
	printf("\n Queue Element\n");
	while (node != NULL)
	{
		printf(" %d", node->data);
		node = node->next;
	}
	printf("\n");
}

Here is the code implementation of queue using doubly linked list:
a

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

typedef struct QNode
{
	int data;
	struct QNode * next;
	struct QNode * prev;
}QNode;

typedef struct MyQueue
{
	struct QNode * front;
	struct QNode * rear;
	int size;
}MyQueue;

QNode * getQNode(int data, QNode * prev)
{
	QNode * ref = (QNode * ) malloc(sizeof(QNode));
	if (ref == NULL)
	{
		return NULL;
	}
	ref->data = data;
	ref->next = NULL;
	ref->prev = prev;
	return ref;
}

MyQueue * getMyQueue()
{
	MyQueue * ref = (MyQueue * ) malloc(sizeof(MyQueue));
	if (ref == NULL)
	{
		return NULL;
	}
	ref->front = NULL;
	ref->rear = NULL;
	return ref;
}

void enqueue(MyQueue * ref, int data)
{
	QNode * node = getQNode(data, ref->rear);
	if (ref->front == NULL)
	{
		ref->front = node;
		ref->size = 1;
	}
	else
	{
		ref->rear->next = node;
		ref->size = ref->size + 1;
	}
	ref->rear = node;
}

int isEmpty(MyQueue * ref)
{
	if (ref->size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

int peek(MyQueue * ref)
{
	if (isEmpty(ref) == 1)
	{
		printf("\n Empty Queue");
		// When stack is empty
		return -1;
	}
	else
	{
		return ref->front->data;
	}
}

int isSize(MyQueue * ref)
{
	return ref->size;
}

int dequeue(MyQueue * ref)
{
	if (isEmpty(ref) == 1)
	{
		return -1;
	}
	else
	{
		int data = peek(ref);
		QNode * temp = ref->front;
		if (ref->front == ref->rear)
		{
			ref->rear = NULL;
			ref->front = NULL;
		}
		else
		{
			ref->front = ref->front->next;
			ref->front->prev = NULL;
		}
		ref->size--;
		return data;
	}
}
void printQdata(MyQueue * ref)
{
	QNode * node = ref->front;
	printf("\n Queue Element\n");
	while (node != NULL)
	{
		printf(" %d", node->data);
		node = node->next;
	}
	printf("\n");
}
int main()
{
	MyQueue * q = getMyQueue();
	enqueue(q, 1);
	enqueue(q, 3);
	enqueue(q, 5);
	enqueue(q, 6);
	enqueue(q, 7);
	printQdata(q);
	printf(" Size : %d", isSize(q));
	
	printf("\n Dequeue Node : %d", dequeue(q));
	printf("\n Dequeue Node : %d", dequeue(q));
	printf("\n Dequeue Node : %d", dequeue(q));
	printQdata(q);
	printf(" Size : %d\n", isSize(q));
  	return 0;
}

We have explained how to implement queue using doubly linked list in this article. We have tried to explain all the functions we need to implement to queue using doubly linked list in c i.e.enqueue(), dequeue(), isSize(), peek(), isEmpty(), printQdata(). These type of questions also help in brushing up the skills of implementation. If you want to solve more questions , you can follow link Linked List., which is curated by our expert mentors at PrepBytes

FAQ related to queue using doubly linked list in c:

1. Can a queue be implemented using a linked list?
Queue supports operations like enqueue and dequeue. It can be implemented using arrays and linked lists.

2. Which companies asked Doubly linked list and Queue in their interview?
Companies like Samsung, Josh Technologies, PrepBytes, Zscaler, Gemini Solution, and Infosys had recently asked for a Doubly Linked List in their interview round.

3. Why is a doubly linked list used?
The most common reason to use a doubly linked list is that it is easier to implement than a singly linked list. While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug.

Leave a Reply

Your email address will not be published. Required fields are marked *