Deque is a data structure that inherits the properties of both queues and stacks. Additionally, the implementation of this data structure requires constant time, i.e., time complexity = O(1). This means you can use deque to your advantage to implement both the queue and stack. So, in this tutorial, you will discover deque in a data structure to understand its functionalities and applications.
What Is Deque in Data Structure?
Deque is a more generalized version of a linear queue. As you know, the linear queue has some restrictions while performing the insertion and deletion of elements. The insertion in a linear queue must happen from the rear end and deletion from the front end. But, in deque, you can perform both insertion and deletion operations at both of its ends. That’s why it is called a Double-Ended Queue (Deque).
The image above represents how different operations take place at both ends of the deque.
Properties of Deque
Now, you will look into the primary properties of deque in a data structure.
A deque can perform both the insertion and deletion using the LIFO (Last In First Out) principle.
The insertion and deletion in deque can be limited to one node. When you do that, the deque becomes a stack. Hence, it follows the Last In First Out Principle for insertion and deletion.
As shown in the image above, initially, there were four elements inside this deque. However, after repeating the removal of an element twice, data elements 2 and 12 get removed from the deque, respectively. You inserted element 2 at last and removed it at first. This example demonstrates the LIFO principle.
A Deque can perform insertion and deletion operations using the FIFO (First In First Out) principle.
As deque can operate on both ends, you can extract queue properties by limiting insertion at the front node and removal at the rear node. Doing this will allow deque to act as a linear queue.
As shown in the image above, the element which enters at first will also leave the queue first. This is how deque can use the FIFO principle to perform insertion and deletion.
Types of Deque in Data Structure
There are two types of deque which are created by restricting certain operations. Let’s clearly understand them.
Input-Restricted Deque: It is a deque with some limitations while performing insertion operations. In the Input-Restricted Deque, it will perform the deletion at both ends, whereas it performs the insertion at only one end. The image below shows how input restricted deque limits insertion at one end.
Output-Restricted Deque: It is a deque with some limitations while performing deletion operations. In the Output-Restricted Deque, it will perform the insertion at both ends, whereas it performs the deletion of elements at only one end. The image below shows how output restricted deque limits removal at one end.
Operations on Deque
Four basic operations are performed on deque, they are as follows:
Insertion at Rear
Insertion at Front
Deletion at Front
Deletion at Rear
Along with these primary operations, you can also perform isEmpty(), isFull() and Peek() operations. These operations are called supportive queue operations. But, in this tutorial, you will only implement primary queue operations. The time required to implement all these functions must be constant, i.e., time-complexity = O(1).
Representation of Deque Using Circular Queue
The Deque can be implemented using either a circular queue or a doubly-linked list. The circular queue implementation of the deque is the most straightforward approach to implement a double-ended queue. Hence, in this tutorial, you will only focus on the circular queue representation of deque. Primarily, understand what a circular queue is.
What Is a Circular Queue?
A circular queue is an extended version of a linear queue as it follows the First In First Out principle with the exception that it connects the last node of a queue to its first, by forming a circular link. Hence, it is also called a Ring Buffer. The illustration of a circular queue below shows the connectivity between the queue’s first and last node.
Additionally, a circular queue manages memory efficiently because of its circular link. If the rear pointer has reached the maxsize of a queue, it will again arrive at the beginning of a queue. Bringing the rear node to the beginning of a queue is called circular incrementation. The image given below shows how to achieve circular incrementation.
You must be clear about the concept of a circular queue. Now, moving ahead, you will look into how to implement the deque using a circular queue.
To implement deque using a circular queue, you should be able to implement the insertion and deletion at both ends of a queue. Let’s begin with implementing insertion at both ends.
1. Insertion at Rear:
First, understand insertion using the rear node with the help of an example.
Initially, there is only one element inside the queue. Hence, both front and rear are pointing to the index 0. Additionally, as you are inserting elements using a rear node, its incrementation will bring you to the empty space for putting in a new element. The image shown above represents how insertion occurs using a rear pointer.
2. Insertion at Front:
Let’s deal with the insertion using a front pointer. Consider the example given below. In this example, a front node points to index 0, and now you want to insert elements using it. In order to do that, set the front pointer to MAXSIZE - 1. Doing this will allow your front pointer to reach the end of a queue. After that, you can insert a new element at this new location (index 5). But, for further insertions, you will just decrement the value of a front pointer.
The diagrammatic representation above explains insertion at front operation.
3. Deletion at Front:
Consider the diagrammatic representation of a circular array given below. In this representation, a front node is pointing to index 4 and a rear node to index 2. Now, to perform the deletion, you will have to increase the location of the front pointer until it reaches the maxsize of a queue. For further deletions, set a front pointer to index 0. The diagram below will help you to visualize that.
4. Deletion at Rear:
The diagrammatic representation given below explains how you can perform deletion operations using a front node.
In this example, the rear node is at index 2. To perform the removal of elements, reduce the location of a rear pointer until it arrives at index 0. Once it reaches the index 0, you will either set it to MAXSIZE - 1 (if there are elements inside the queue) or -1 along with front = -1 (if there is no element inside the queue).
Once you are clear with the different cases for both insertion and deletion, you will dive into the implementation of deque in a data structure.
Implementation of Deque
As mentioned previously, you will implement four main primary deque operations as listed below:
front_Enqueue(int z): Inserts element using front node in a deque
rear_Enqueue(int z): Inserts element using rear node in a deque
front_Dequeue(): Removes element using front node in a deque
rear_Dequeue(): Removes element using rear node in a deque
You will use the C programming language to implement deque in data structure using a circular array (Queue).
#include<stdio.h>
#include<iostream>
//Global scope
#define size 5
int dq[100];
int front = -1, rear =-1;
//Insertion from front
void front_Enqueue(int z)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf("deque is full, Insertion is not possible");
}
else if((front==-1) && (rear==-1))
{
front=rear=0;
dq[front]=z;
}
else if(front==0)
{
front=size-1;
dq[front]=z;
}
else
{
front=front-1;
dq[front]=z;
}
}
// insertion from rear end
void rear_Enqueue(int z)
{
if((front==0 && rear==size-1) || (front==rear+1))
{
printf("deque is full");
}
else if((front==-1) && (rear==-1))
{
rear=0;
dq[rear]=z;
}
else if(rear==size-1)
{
rear=0;
dq[rear]=z;
}
else
{
rear++;
dq[rear]=z;
}
}
//function to analyze state of queue.
void display()
{
int i=front;
printf("\n Elements inside the double ended queue are : ");
while(i!=rear)
{
printf("%d ",dq[i]);
i=(i+1)%size;
}
printf("%d",dq[rear]);
}
void front_Dequeue()
{
if((front==-1) && (rear==-1))
{
printf("There is no element to delete inside a deque");
}
else if(front==rear)
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=-1;
rear=-1;
}
else if(front==(size-1))
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=0;
}
else
{
printf("\nThe deleted element from the front is %d", dq[front]);
front=front+1;
}
}
// dequeue_rear() function deletes the element from the rear
void rear_Dequeue()
{
if((front==-1) && (rear==-1))
{
printf("Deque is empty");
}
else if(front==rear)
{
printf("\nThe deleted element from rear is %d", dq[rear]);
front=-1;
rear=-1;
}
else if(rear==0)
{
printf("\nThe deleted element from the rear node is %d", dq[rear]);
rear=size-1;
}
else
{
printf("\nThe deleted element from rear node is %d", dq[rear]);
rear = rear-1;
}
}
int main()
{
front_Enqueue(-5);
front_Enqueue(23);
rear_Enqueue(17);
rear_Enqueue(12);
rear_Enqueue(47);
display();
front_Dequeue();
rear_Dequeue();
display();
return 0;
}
The display() function implemented in this program is an additional function that you have to implement to visualize the state of a deque. The image given below is the output that you will receive after running this code in a compiler.
Output
Applications of Deque in Data Structure
The deque can act as both the queue and stack. Thus, all the applications of queue and stacks can be implemented using a double-ended queue. Given below are some critical applications of deque in data structure:
Palindrome Checker
The string or a number that reads the same backward as forward is known as a palindrome. The program to check if the given string is palindrome or not can be implemented using deque in a data structure. If the string reads the same from both the deque ends, it will consider it a palindrome. The image given below is an illustration of a palindrome checker implementation using a double-ended queue.
Multiprocessor Scheduling
When multiple processes are being executed by multiple processors (CPU, Core) in a system, then that system utilizes a multiprocessor scheduling algorithm. In this algorithm, the deque is used by each processor to store different threads of processes. This algorithm is also called the A-Steal algorithm for scheduling. The illustration given below represents the process of multiprocessor scheduling.
Conclusion
In this tutorial, you explored the deque in a data structure in detail. You went through different properties and types of deque along with its representation using a circular queue. You also understood the operations in deque with the help of a pictorial representation. Finally, you also discovered different applications of deque to understand its importance.
What Is a Deque?
A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure. Figure 1 shows a deque of Python data objects.
It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures. It is up to you to make consistent use of the addition and removal operations.
కామెంట్లు లేవు:
కామెంట్ను పోస్ట్ చేయండి