What is Deque in Data Structure?
The Deque stands for "Double Ended Queue".
Deque is an another type of queue which allows elements to be added or removed from both the front and the back which means we can insert and delete an element at the front end or rear end both.
Deque provides greater flexibility than a standard queue. This makes it particularly useful for scenarios where we need to access elements from both ends efficiently.
The following diagram represents a Deque in data structure.
Deque does not apply the concept of the FIFO (First-In-First-Out) so we can insert and delete elements from both ends of the queue.
Types of Deque in Data Structure
There are mainly two types of Deque in data structure:
- Input restricted queue
- Output restricted queue
Let's discuss them in details.
Input restricted queue: It allows to perform the insert operation only at one end and the delete operation from both ends of the queue.
Let's see the diagram given below for understanding.
Output restricted queue: It allows to perform the delete operation only at one end and the insert operation from both ends of the queue.
Let's see the diagram given below for understanding.
Operations performed on Deque
In a Deque, we can perform the following operations, as given below:
- Insertion at front
- Insertion at rear
- Deletion at front
- Deletion at rear
Apart from the insert and delete operations, we can also perform the following operations on the deque data structure.
- Get the front element
- Get the rear element
- Check whether the deque is full or not
- Checks whether the deque is empty or not
Example: Deque Implementation in Java
After understanding Deque with the help of the given definition and diagram, let's look at how it's implemented in Java.
// A Java program to implement Deque with all operations
class Deque {
int dequeArray[];
int front;
int rear;
int size;
public Deque(int size) {
// Create an int data type array that stores 10 elements.
dequeArray = new int[10];
front = -1;
rear = 0;
this.size = size;
}
// Function to check Deque is full
boolean isFull() {
return ((front == 0 && rear == size - 1) || front == rear + 1);
}
// Function to check Deque is empty
boolean isEmpty() {
return (front == -1);
}
// Function to insert an element from front
void insertFront(int element) {
// Before inserting, make sure queue should not be full
if (isFull()) {
System.out.println("Overflow");
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else if (front == 0) {
front = size - 1;
} else {
front = front - 1;
}
dequeArray[front] = element;
}
// Function to insert an element at rear
void insertRear(int element) {
// Before inserting, make sure queue should not be full
if (isFull()) {
System.out.println(" Overflow ");
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else if (rear == size - 1) {
rear = 0;
} else {
rear = rear + 1;
}
dequeArray[rear] = element;
}
// Function to delete an element from the front
void deleteFront() {
// Before deleting, make sure queue should not be empty
if (isEmpty()) {
System.out.println("Queue Underflow\n");
return;
}
// Deque has only one element
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1) {
front = 0;
} else {
front = front + 1;
}
}
// Function to delete an element from the rear
void deleteRear() {
// Before deleting, make sure queue should not be empty
if (isEmpty()) {
System.out.println(" Underflow");
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0) {
rear = size - 1;
} else {
rear = rear - 1;
}
}
// Function to get a value from the front
int getFront() {
// Before accessing element, make sure queue should not be empty
if (isEmpty()) {
System.out.println(" Underflow");
return -1;
}
return dequeArray[front];
}
// Function to get a value from rear
int getRear() {
// Before accessing element, make sure queue should not be empty
// Or, rear should not be less than 0
if (isEmpty() || rear < 0) {
System.out.println(" Underflow\n");
return -1;
}
return dequeArray[rear];
}
public static void main(String[] args) {
Deque deque = new Deque(5);
System.out.println("Insert element 10 at the REAR end");
deque.insertRear(10);
System.out.println("insert element 20 at the REAR end");
deque.insertRear(20);
System.out.println("get REAR element: " + deque.getRear());
deque.deleteRear();
System.out.println("After deletion, get REAR: " + deque.getRear());
System.out.println("Insert element 30 at the FRONT end");
deque.insertFront(30);
System.out.println("Insert element 40 at the FRONT end.");
deque.insertFront(40);
System.out.println("get FRONT: " + deque.getFront());
deque.deleteFront();
System.out.println("After deletion, FRONT element: "+ deque.getFront());
}
}Insert element at REAR end: 10 insert element at REAR end: 20 get REAR element : 20 After delete, get REAR element: 10 Insert element at FRONT end: 30 Insert element at FRONT end: 40 get FRONT element: 40 After delete, FRONT element: 30
Time and Space Complexity of Deque Operations
| Operations | Time Complexity | Space Complexity |
|---|---|---|
| Insert Front | O(1) | O(n) |
| Insert Rear | O(1) | O(n) |
| Delete Front | O(1) | O(n) |
| Delete Rear | O(1) | O(n) |
| Search | O(n) | O(n) |
Advantages of Deque
- Deque allows to insert and delete elements from both the front and back ends of the queue.
- Deques size is not fixed. It can grow or shrink its size dynamically when required.
- Deques provide an efficient time complexity of O(1) for the insertion and deletion of elements from both ends.
- Deques can be implemented as stacks (LIFO), queues (FIFO), or a combination of both of them.
- Deques do not require reallocation of memory when elements are inserted or removed.
- When elements are inserted or deleted from a deque, no memory reallocation is required.
- Deque is more efficient and fast in inserting and deleting the elements to the end or beginning of the queue.
- Deques can be thread-safe if properly synchronized.
Disadvantages of Deque
- Deques required extra pointers to maintain the double-ended structure, so than other data structures, it has higher memory overhead.
- Compared to a normal queue, Deques are less memory efficient.
- It has synchronization issues when working with multiple threads.
- Not every platform may support deques.
- Not suitable to implement sorting or searching operations.
- Compared to other data structures, Deque has a lower number of functionalities.