Last Updated on July 27, 2023 by Mayank Dham
Queues are basic data structures that are used extensively in computer science and programming. They adhere to the First-In-First-Out (FIFO) principle, making them ideal for data management in situations where order is critical. While there are several approaches to implementing a queue, a doubly linked list provides a flexible and efficient solution. In this article, we will look at how to implement a queue in the C programming language using a doubly linked list. We can create a dynamic data structure capable of handling operations like enqueueing (adding elements) and dequeuing (removing elements) by combining the benefits of a queue and a doubly linked list.So we will see how we can implement queue using doubly linked list in C.
What is a Queue?
The FIFO (First in First out) principle, which states that the element that is inserted first will be withdrawn first, is followed by a queue, which is a linear data structure. Enqueue operation and dequeue operation are terms used to describe operations that add and remove elements, respectively.
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:
-
Enqueue: With the help of this function, an element can be added to the rear end queue. The double linked list has a ref pointer that contains a rear, front, and size pointer. When enqueueing, we shall add data to the new node and transmit it to the rear node’s next pointer. Additionally, in the event of insertion, the size pointer will be increased by 1.
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; } -
Dequeue: Using this function, a front end queue piece can be removed. The size pointer will decrease by 1 and the front pointer will transfer from the ref to the front->next. provide the info that was kept in the deleted node as well.
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; } } -
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; } -
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; } } -
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; } } -
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;
}
In this post, we have described how to implement a queue using a doubly linked list. The functions enqueue(), dequeue(), isSize(), peek(), isEmpty(), and printQdata() have all been attempted to be explained in detail. Additionally, inquiries of this nature aid in honing implementation skills.
Conclusion
Implementing a queue using a doubly linked list in C provides a flexible and efficient solution for managing data in a First-In-First-Out (FIFO) manner. Throughout this article, we looked at how to build a queue using a doubly linked list step by step and delved into the complexities of this data structure implementation. We created a dynamic data structure capable of handling enqueue and dequeue operations by combining the advantages of a queue and a doubly linked list. The implementation enabled us to add elements to the queue’s back end (enqueue) and remove elements from the front end (dequeue) in real time.
FAQ related to Queue using Doubly Linked List in C
Q1: Why use a doubly linked list for implementing a queue?
Ans. Using a doubly linked list for implementing a queue provides several advantages. It allows for efficient insertion and removal of elements at both ends of the list, making enqueue and dequeue operations constant time. Additionally, it enables easy implementation of operations such as peeking at the front and back elements of the queue.
Q2: How does a queue implemented with a doubly linked list differ from an array-based implementation?
Ans. Unlike an array-based implementation, a queue using a doubly linked list does not have a fixed size limitation. It can dynamically grow or shrink as elements are added or removed. This flexibility avoids the need for resizing the underlying array and reduces the risk of overflow or underflow conditions.
Q3: What are the key operations involved in implementing a queue using a doubly linked list?
Ans. The main operations involved in implementing a queue using a doubly linked list are: initializing the queue, enqueueing (adding) elements to the back of the queue, dequeuing (removing) elements from the front of the queue, and checking if the queue is empty.
Q4: How can I handle memory management when implementing a queue with a doubly linked list?
Ans. Proper memory management is crucial to avoid memory leaks and efficiently utilize system resources. When implementing a queue with a doubly linked list, ensure that you free the memory occupied by nodes that are dequeued to prevent memory leaks. Additionally, handle memory allocation failures gracefully and release allocated memory upon program termination.