Deque – Everything You Need To Know
Data Structures are referred to as the most important part of programming. And the most important data structures are Stacks and Queues. In the sub-context comes the operations and we are going to discuss deque operation in this article. Deque is often referred to as a double-ended queue.
Introduction
A Queue can be implemented in many ways. Like it can be implemented using basic arrays to complex linked lists. Each method has its own definition of performing a deque operation.
What is a Queue?
A queue is a basic data structure that follows FIFO(First in First Out) rule meaning the element that entered first is deleted first. We call these operations Enqueue and Deque.
What is Deque?
A deque, also known as a double-ended queue, and it is a data structure that allows for the insertion and removal of elements from both the front and the back of the queue. It is similar to a queue or a stack, but with the added capability of adding and removing elements from both ends. This allows for more efficient implementation of certain algorithms, such as those that involve both pushing and popping elements. Deque can also be implemented with both dynamic and circular arrays.
Representation of Deque
A deque can be represented as a linear data structure, similar to an array or a linked list, with two pointers, one to the front of the deque and one to the back. The front pointer points to the first element in the deque, while the back pointer points to the last element.
Types of Deque
Input-restricted Deque
An Input-restricted deque is a type of queue where we can perform deletion from both ends but, Insertion can only be done from one end. Even though it ruins the basic definition of the queue we are considering this due to the requirements and also by using this method the queue can be very customized.
Output-restricted Deque
An Output-restricted deque is a type of queue where we can insert the required elements on both ends precisely from both rear and front. But, Deletion can be done from only one end.
Operations on Deque
InsertFront()
The function InsertFront can be used to add an element to the queue at the beginning of the queue.
Let us consider an example of a queue implemented using a single linked list. In this example, we can simply create a new node containing the data we need to store and refer to it as a head. And, finally, change the address pointer of this node to the previous head node. Thus, by following these steps, we can insert an element at the beginning of a queue.
struct Node *newNoder;
newNoder = (struct Node *)malloc(sizeof(struct Node));
newNoder->data = value;
// assign value to the node
if (head == NULL) {
newNoder->next = NULL;
} else {
newNoder->next = head;
}
head = newNoder;
// head always points to the newly created node
Code language: C/AL (cal)InsertRear()
The function InsertFront can be used to add an element to the queue at the end of the queue.
Let us consider an example of a queue implemented using a single linked list. In this example, we can simply create a new node containing the data we need to store. Then, that node is added to the address part of the rear pointer node. You can check the algorithm below.
void InsertRear(int value)
//value contains the data to be stored.
{
struct node * kr;
kr = (struct node * ) malloc(sizeof(struct node));
kr ->data = value;
ptr ->next = NULL;
if ((front == NULL) && (rear == NULL)) {
front = rear = kr;
}
else {
rear -> next = kr;
rear = kr;
}Code language: C/AL (cal)DeleteFront()
The function DeleteFront() is used to delete the starting element in the queue, it is the conventional method of deque in a normal queue.
Let us consider a single linked list with some data stored in it. We can delete the data stored in front by simply reassigning the head to the second node and freeing the memory allocated to the previous node.
int DeleteFront(){
if (fronte == NULL) {
printf("\nUnderflow");
return -1;
} else
{
struct node * tempe = fronte;
int temp_data = fronte -> data;
fronte = fronte -> next;
free(tempe);
return temp_data;
}
}Code language: C/AL (cal)DeleteRear()
The function DeleteRear() is used to delete the last element in the queue, it is the conventional method of popping in a stack.
Let us consider a single linked list with some data stored in it. we can delete the last element by traversing the linked list till the end and assign the last but one node’s address to null.
int DeleteRear()
{
if (header == NULL) {
printf("\nStack Underflow\n");
} else {
struct Node *temper = header;
int temp_data = top->data;
top = top->next;
free(temper);
return temp_data;
}
}Code language: C/AL (cal)GetFront()
We can find the data stored in the front element using this function. Since the front pointer always points to the first element, we can simply access its data.
void GetFront()
{
printf("%d",front->data);
}Code language: C/AL (cal)GetRear()
We can find the last entered element into the queue using the function GetRear(). As the rear pointer always points to the last element of the queue, we can simply get the last element by accessing its data.
void GetRear()
{
printf("%d",reare->data);
}Code language: JavaScript (javascript)IsEmpty()
This condition is usually prompted when we try to delete an element from an empty queue. We can check this condition by checking whether the rear and the front pointer point to the same node except the first node, then, we can print that the queue is empty.
int isEmpty()
{
if (fronte == NULL) {
printf("\nUnderflowing queue\n");
return -1;
}Code language: C/AL (cal)IsFull()
This is a special function as it can only be checked if the queue is implemented using arrays only, As linked lists use dynamic allocation, there is no condition that the queue is full.
void isFull()
{
if(fronte == reare)
{
printf("Queue Overflow");
}Code language: C/AL (cal)Applications
- Many websites like IRCTC use queue applications to allocate tickets based on a first come first serve basis.
- In CPU Scheduling algorithms, ready queues are used to store the context switches.
Implementation Of Deque
#define MAX_SIZE 100
#include<stdio.h>
#include<stdlib.h>
int deque[MAX_SIZE];
int front = -1;
int rear = -1;
void insert_front(int item) {
if ((front == 0 && rear == MAX_SIZE-1) || front == rear+1 ) {
printf("Deque is full\n");
return;
}
if (front == 0)
front = MAX_SIZE-1;
else
front--;
deque[front] = item;
}
void insert_rear(int item) {
if ((front == 0 && rear == MAX_SIZE-1) || front == rear+1 ) {
printf("Deque is full\n");
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
rear++;
}
deque[rear] = item;
}
void delete_front() {
if (front == -1) {
printf("Deque is empty\n");
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else {
front++;
if (front == MAX_SIZE)
front = 0;
}
}
void delete_rear() {
if (front == -1) {
printf("Deque is empty\n");
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else {
rear--;
}
}
int main() {
insert_rear(1);
insert_rear(2);
insert_rear(3);
insert_front(0);
insert_front(-1);
printf("The front element is: %d\n", deque[front]);
printf("The rear element is: %d\n", deque[rear]);
delete_front();
delete_rear();
printf("The new front element is: %d\n", deque[front]);
printf("The new rear element is: %d\n", deque[rear]);
return 0;
}
Code language: C/AL (cal)Click here to run the code by yourself!
OUTPUT
The front element is: -1
The rear element is: 3
The new front element is: 0
The new rear element is: 2Code language: C/AL (cal)Conclusion
Queue being one of the easiest data structures, it is easy to implement it using a linked list due to dynamic memory allocation. We have learned here about input-restricted and output-restricted methods of the deque and some other basic operations. These things less practice. Hence, master them.
Frequently Asked Questions to Resolve (FAQs)
What do you mean by deque?
A deque (short for “double-ended queue”) is a type of data structure that allows for efficient insertion and deletion at both its front and rear. It is similar to a queue, but unlike a queue, where insertion and deletion can only happen at one end (usually the rear for insertion and front for deletion), a deque allows for insertion and deletion at both the front and rear. This makes it more versatile, and it can be used in a variety of algorithms and data structures.
What is the difference between dequeue and deque?
Deque and dequeue are the same things, they are just two different ways to spell the same word. Deque is short for “double-ended queue” and dequeue is short for “double-ended queue” as well. They both refer to a data structure that allows for efficient insertion and deletion at both its front and rear. Deque is more commonly used in computer science and programming, while “dequeue” is more commonly used in other fields like operations research, manufacturing, and queuing theory.
Why is deque used?
Deques are used in a variety of algorithms and data structures because of their ability to efficiently insert and delete elements at both the front and rear.
Some common use cases include:
Implementing a queue with O(1) enqueue and dequeue operations: By using a deque, it is possible to implement a queue data structure where elements can be added to the rear and removed from the front in O(1) time.
Implementing a stack with O(1) push and pop operations: By using a deque, it is possible to implement a stack data structure where elements can be added to the front and removed from the front in O(1) time.
What are deque and its types?
Deque refers to a double-ended queue. Array Deque, Linked List Deque Circular Deque, Input-restricted, and Output-restricted deques are some of their types.
What is deque and how does it work?
It is a Double-Ended queue and can perform insertion and deletion from both sides of the queue. A deque is implemented using an array or a linked list, and it has two pointers, one for the front of the deque and one for the rear. The array stores the elements of the deque, and the pointers indicate the positions of the front and rear elements in the array.
Sharing is caring
Did you like what Krishna Bethina wrote? Thank them for their work by sharing it on social media.