Deque in Data Structure

Learn via video course
FREE
View all courses
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
DSA Problem Solving for Interviews using Java
DSA Problem Solving for Interviews using Java
by Jitender Punia
1000
4.9
Start Learning
Topics Covered

Overview

In this article, we are going to learn about the topic deque in data structure. Before getting started with the deque in data structure let us get a short overview of what is a data structure in this article.

Deque in data structure : A deque is a linear data structure, which stands for Double Ended Queue. Unlike queue, where the data can be only inserted from one end and deleted from another, in a deque, the data can be inserted and deleted from both front and rear ends.

What is a Deque in Data Structure?

The deque in data structure stands for Double Ended Queue. We can say the deque in data structure is a generalized version of the queue. Now you must be wondering what is a queue, so let's see a brief description of the queue.

Queue A queue is a data structure that follows the FIFO policy (First in first out) , that is, whatever comes first will go out first. In a queue, the data is inserted from one end which is called as the rear end or tail, whereas the data is deleted from another end which is called as the front end or head of the queue.

A deque in data structure is a linear data structure that does not follow the FIFO rule (First in first out) , that is, in a deque data structure, the data can be inserted and deleted from both front and rear ends. However, in a queue, we may only insert and remove data from one end.

The representation of a deque in data structure is represented below -

representation of a deque in data structure

Types of Deque in Data Structure

Basically, there are two types of deque in data structure

  • Input restricted queue
  • Output restricted queue

Let us discuss about them in detail.

Input restricted queue

In an input restricted queue, the data can be inserted from only one end, while it can be deleted from both the ends.

Let's see a diagram to understand it more clearly.

Input restricted queue

Explanation: In the above example we can see how the data has been inserted from only one end that is the front end, and how it has been deleted from both the ends that are front and rear ends.

Output restricted queue

In an Output restricted queue, the data can be deleted from only one end, while it can be inserted from both the ends.

Let's see a diagram to understand it more clearly.

Output restricted queue

Explanation: In the above example, we can see how the data has been inserted from both the ends(front and rear), and how it has been deleted from only one end(rear).

Operations on Deque in Data Structure

In this section, we are going to implement a dequ in data structure using the circular queue or array. So before going further let's get a brief idea about what is a circular array.

Circular array: It is an array where the last element of the array is connected to the first element. Thus, it forms a circle like structure, that makes it reusable for the empty spaces in the previous indexes caused due to deletion operations.

In a circular array, if the array is full, we again start from the beginning. However in a linear array, if the array is full, we can't insert elements anymore. In each of the operations explained below, if the array is full, an "overflow message" will be thrown.

In a deque in data structure we can perform the following operations:

  • Insertion at front
  • Insertion at rear
  • Deletion at front
  • Deletion at rear

Before performing the following operations, we must follow the below steps :

  • Take a deque(array) of size n
  • Set two pointers variables front = -1 and rear = 0 at the first position.

Operations on deque in data structure

Now, let us understand the operations performed on deque in data structure with examples.

Insertion at the front end

With the help of the Insertion at the front end operation we can insert the element from the front end of the deque in data structure. There is a criterion before implementing the operation, at first we need to check whether the deque is full or not. If the deque is not full, then we can insert the element from the front end, by following the below conditions -

  1. Initially, we will check the position of the front variable in our array

Insertion at the front end

  1. In case, the front variable is less than 1 (front < 1), we will reinitialize the front as the last index of the array (front = n-1).

shift front to the end

  1. Otherwise, we will decrease the front by 1.
  2. Add the new key for example 5 here into our array at the index front - array[front].
  3. Every time we insert a new element inside the deque the size increases by 1.

insert the element at front

Insertion at the rear end

With the help of the Insertion at the rear end operation, we can insert the element from the rear end of the deque in data structure. We can insert the element from the rear end by following the below conditions -

  1. At first, we need to check whether the deque in data structure is full or not.

check if deque is full

  1. If the deque data structure is full, we have to reinitialize the rear with 0 (rear = 0).
  2. Else increase the rear by 1.

increase the rear

  1. Add the new key for example 5 here into our array at the index rear - array[rear].
  2. Every time we insert a new element inside the deque the size increases by 1.

Insertion at the rear end

Deletion at the front end

With the help of the Deletion at the front end operation, we can delete the element from the front end of the deque in data structure. We can delete the element from the front end by following the below conditions -

  1. At first, we need to check whether the deque in data structure is empty or not.

Deletion at the front end

  1. If the deque data structure is empty i.e. front = -1, we cannot perform the deletion process and it will throw an error of underflow condition.
  2. If the deque data structure contains only one element i.e. front = rear, set front = -1 and rear = -1.
  3. Else if the front is at the last index i.e. front = n - 1, we point the front to the starting index of the deque data structure i.e. front = 0.
  4. If none of the cases satisfy we simply increment our front by 1, front = front + 1.
  5. Every time we delete any element from the deque data structure the size decreases by 1.

Deletion at the front end 2

Deletion at the rear end

With the help of Deletion at the rear end operation, we can delete the element from the rear end of the deque in data structure. We can delete the element from the rear end by following the below conditions -

  1. At first, we need to check whether the deque data structure is empty or not.

Deletion at the rear end

  1. If the deque data structure is empty i.e. front = -1, we cannot perform the deletion process and it will throw an error of underflow condition.
  2. If the deque data structure contains only one element i.e. front = rear, set front = -1 and rear = -1.
  3. Else if the rear is at the starting index of the deque i.e. rear = 0, point the rear to the last index of the deque data structure i.e. rear = n-1.
  4. If none of the cases satisfy we simply decrement our rear by 1, rear = rear - 1.
  5. Every time we delete any element from the deque the size decreases by 1.

Deletion at the rear end 2

Check empty

With the help of the Check empty operation we can check whether the deque in data structure is empty or not. The deque in data structure is empty if the front is -1 (front = -1).

Check full

With the help of the Check full operation in our deque in data structure, we can check whether the deque data structure is full or not. If the front is at the starting index (front = 0) and the rear is at the last index (rear = n-1) OR the front is ahead of rear by one unit (front = rear + 1), the deque data structure is full.

Other operations like peek can also be performed in the deque in data structure. Usually with the peek operation we can get the front or rear elements from deque in data structure. So along with the above operations, we can also perform different peek operations as stated below :

  • To Get the front item from the deque in data structure
  • To Get the rear item from the deque in data structure
  • To check whether the deque data structure is full or not
  • To check whether the deque data structure is empty or not

Shape Your Coding Future! Join Our DSA Course and Navigate the World of Efficient Algorithms. Enroll Now!

Deque Implementation in Java, Python, C, and C++

Now, let us see the implementation of deque in data structure in different programming languages.

Deque Implementation in Java

The code for the implementation of Deque in data structure in Java is given below.

code:

Output:

Explanation

In the above code, we have implemented deque in data structure in the java programming language.

We are going to perform the following operations in our deque in data structure in this code:

  • isFull() : This function is used to check whether the deque data structure is full or not.
  • isEmpty() : This function is used to check whether the deque data structure is empty or not.
  • insertFront() : This function is used to insert an element at the front end of the deque data structure
  • insertRear() : This function is used to insert element at the rear end of the deque data structure
  • deleteFront(): This function is used to delete elements from the front end of the deque in data structure
  • deleteRear(): This function is used to delete elements from the rear end of the deque in data structure
  • getFront(): This function is used to get or peek element from the front end of the deque in data structure
  • getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Deque Implementation in Python

The code for the implementation of deque in data structure in Python is given below.

code:

Output:

Explanation:

We are basically performing the following operations in our deque in data structure in this code:

  • size() : This function is used to get the size of the deque in data structure.
  • isEmpty() : This function is used to check whether the deque in data structure is empty or not.
  • addFront() : This function is used to insert element at the front end of the deque in data structure
  • addRear() : This function is used to insert element at the rear end of the deque in data structure
  • removeFront(): This function is used to delete elements from the front end of the deque in data structure
  • removeRear(): This function is used to delete elements from the rear end of the deque in data structure
  • getFront(): This function is used to get or peek elements from the front end of the deque in data structure
  • getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Deque Implementation in C

The code for the implementation of deque in data structure in C is given below.

code:

Output:

Explanation:

We are going to perform the following operations in our deque in data structure in this code:

  • count() : This function is used to count the total number of elements in the deque in data structure. This can be done by iterating over the whole deque in data structure.
  • addFront() : This function is used to insert an element at the front end of the deque in data structure.
  • addRear() : This function is used to insert element at the rear end of the deque in data structure
  • delFront(): This function is used to delete elements from the front end of the deque in data structure
  • delRear(): This function is used to delete elements from the rear end of the deque in data structure
  • display(): This function is used to get or peek all the elements from the deque in data structure

Deque Implementation in C++

The code for the implementation of deque in data structure in C++ is given below.

code:

Output:

Explanation: We are going to perform the following operations in our deque in data structure in this code:

  • isFull() : This function is used to check whether the deque in data structure is full or not.
  • isEmpty() : This function is used to check whether the deque in data structure is empty or not.
  • insertFront() : This function is used to insert an element at the front end of the deque in data structure
  • insertRear() : This function is used to insert an element at the rear end of the deque in data structure
  • deleteFront(): This function is used to delete elements from the front end of the deque in data structure
  • deleteRear(): This function is used to delete elements from the rear end of the deque in data structure
  • getFront(): This function is used to get or peek elements from the front end of the deque in data structure
  • getRear(): This function is used to get or peek element from the rear end of the deque in data structure

Applications of the deque in data structure

There are innumerable applications of the deque in the data structure. It is vastly applied in most fields of computer science. Let us look into a few of them to understand their importance.

  • Palindrome Checker: The string or a number that is the same when we read it from both forward and backward directions is known as a palindrome. Some of the examples of palindrome are "aba", 121, 1001, etc. Our deque in data structure can be used to implement the program to check whether a number is a palindrome or not.
  • Multiprocessor Scheduling: When multiple processes in a system are being carried out by multiple processors like CPU, or Core, at that time that system uses a multiprocessor scheduling algorithm. All the processors use our deque data structure to store all the different threads of processes. We also call this algorithm the A-Steal algorithm for scheduling.
  • Deque can be also used for implementing both the stack and queue, and it supports both of their operations.
  • Deque can be also used to store the history in the browser, or the browsing history
  • Deque is widely implemented for the undo operations in software.

Equip yourself to tackle complex C++ projects with confidence. Enroll in C++ Data Structures Course by Scaler Topics now!

Conclusion

In this article, we learned about deque in data structure. Let us recap the points we discussed throughout the article:

  • A data structure helps in organizing the data in a particular manner, such that we can efficiently perform numerous operations on them.
  • A deque in data structure is a linear data structure, which stands for Double Ended Queue. In a deque, the data can be inserted and deleted from both front and rear ends.
  • Unlike queue, deque in data structure doesn't follow the FIFO rule (First in first out).
  • There are two types of deque in data structure Input restricted queue and Output restricted queue
  • In input restricted queue, the data can be inserted from only one end, while it can be deleted from both ends.
  • In Output restricted queue, the data can be deleted from only one end, while it can be inserted from both ends.
  • We usually implement deque in data structure using a circular array. As in a linear array implementation, if the array is full, no more elements can be inserted, and if we try to insert it will throw an "overflow message" error.
  • In a deque in data structure we can perform operations like Insertion at front, Insertion at rear, Deletion at front, Deletion at rear.
  • We can insert the element from the front end and the rear end of the deque.
  • We can delete the element from the front end and the rear end of the deque.
  • We can also check whether a deque is empty or full.
  • We can also use the peek operation to get the front or rear element of the deque.
  • We have also implemented deque in different programming languages like Java, Python, C, and C++.
  • Applications of deque in data structure are like the undo operations, used in storing the browsing history, implementations of stack and queues, etc.