What is Deque?
- Double Ended Queue which is also called Deque is a type of queue data structure in which insertion and deletion of elements can be either in front or rear.
- It doesn’t follow First In First Out (FIFO) rule
- We will be using a Circular Array for implementing Deque, if the array is FULL , we again start from the beginning . The first element is considered as the next of the Last element .
Types of Deque:
There are 2 types of Deque:
- Input Restricted Queue: Insertion can only be performed at any one end but deletion can be done from both the ends
2. Output Restricted Queue: Insertion can only be performed from both ends but deletion can be done from any one end
Operations that can be applied on a given deque:
- Delete an element from the front
- Delete an element from the rear
- Insert an element from the front
- Insert an element from the rear
- Get the front item from deque
- Get the rear element from deque
- Check whether deque is full or not
- Check whether deque is empty or not
Front – It is used to refer to the first element of the deque. By using it we can fetch the first element of a deque
Rear – It is used to refer to the last element of the deque. By using it we can fetch the last element of a deque
Before performing the above-mentioned operations, we will do the following steps :
- Declare an Array of size N. This array will be used as a deque
- Set 2 pointers at the first position where Front = -1 and Rear = 0
Insert at the Front
Algorithm:
- Check the position of the front
- If front < 1 , reinitialize front = N-1 ( last index )
- Then add new element to Array[front]
Insert at Rear
Algorithm:
- Check if the array is full or not
- If it’s full , reinitialize rear = 0 else increase rear by 1.
- Then add the element to Array[rear]
Delete from Front
Algorithm:
- Check if deque is Empty or not Empty.
- If deque is Empty, then deletion operation cannot be performed . In this case , we will simply print UNDERFLOW. In this condition , the front will be -1.
- If deque has only 1 element , then only 1 operation of deletion is possible. In case of 1 element , front == rear.
- We will set front =-1 and rear = -1
- If the front is at the last index ( front == n-1 ) , set front = 0.
- Else set Front = Front + 1.
Delete from Rear
Algorithm:
- Check if the deque is empty or not empty. If it’s empty, then we cannot perform a deletion operation. We will directly print UNDERFLOW.
- If the deque has only 1 element i.e front==rear, we will set front = -1 and rear =-1
- If rear is at 0 , then set rear = n-1
- Else rear = rear-1
- Check if Deque is Empty or Not Empty
If front = -1, then deque is empty else it’s not empty.
- Check if Deque is Full or Not Full
If front == 0 and rear == n-1 , then deque is Full
->If front == rear + 1 , then also deque is Full.
->If the deque is Full ,then any new element cannot be inserted . We will directly print OVERFLOW.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std ;
#define MAX 100
class Deque {
int array[MAX] ;
int rear, front, size ;
public:
Deque(int size) {
front = -1 ;
rear = 0 ;
this->size = size ;
}
void InsertFront(int element) ;
void InsertRear(int element) ;
void DeleteFront() ;
void DeleteRear() ;
int GetFront();
int GetRear() ;
bool isFull() ;
bool isEmpty() ;
} ;
bool Deque :: isFull() {
if (front == 0 && rear == size - 1) return 1 ;
if (front == rear + 1 ) return 1 ;
return 0 ;
}
bool Deque :: isEmpty() {
if (front == -1) return 1 ;
return 0 ;
}
void Deque::InsertRear(int element) {
if (isFull()) {
cout << "Overflow\n" ;
return ;
}
if (rear == size - 1) {
rear = 0 ;
}
else if (front == -1) {
rear = 0 ;
front = 0 ;
}
else {
rear++ ;
}
array[rear] = element ;
}
void Deque::InsertFront(int element) {
if (isFull()) {
cout << "Overflow\n" ;
return ;
}
if (front == 0) {
front = size - 1;
}
else if (front == -1) {
rear = 0 ;
front = 0 ;
}
else {
front-- ;
}
array[front] = element ;
}
void Deque :: DeleteFront() {
if (isEmpty()) {
cout << "Underflow\n" ;
return ;
}
if (front == size - 1) {
front = 0 ;
}
else if (front == rear) {
rear = -1 ;
front = -1;
}
else {
front++ ;
}
}
void Deque::DeleteRear() {
if (isEmpty()) {
cout << "Underflow\n" ;
return ;
}
if (rear == 0) {
rear = size - 1;
}
else if (front == rear) {
rear = -1 ;
front = -1;
}
else {
rear-- ;
}
}
int Deque::GetRear() {
if (rear < 0 ) {
cout << "Underflow\n" ;
return -1 ;
}
if (isEmpty()) {
cout << "Underflow\n" ;
return -1;
}
return array[rear] ;
}
int Deque::GetFront() {
if (isEmpty()) {
cout << "Underflow\n" ;
return -1;
}
return array[front] ;
}
int main() {
Deque dq(30);
cout << "Inserting element at front end \n";
dq.InsertFront(100);
cout << "Getting front element " << " " << dq.GetFront() << "\n";
dq.DeleteFront();
cout << "After deleting front element new front will be " << dq.GetFront()
<< endl;
cout << "Inserting element at rear end : 50 \n";
dq.InsertRear(50);
cout << "Inserting element at rear end : 10 \n";
dq.InsertRear(10);
cout << "Rear element " << dq.GetRear() << endl;
dq.DeleteRear();
cout << "After deleting rear element new rear will be " << dq.GetRear() <<
"\n";
return 0 ;
}
Time Complexity : Operations like InsertRear(), InsertFront() , DeleteRear(), DeleteFront() have time complexity of O(1) (Constant).
Space Complexity: O(1)
Java Code
class Deque {
static final int MAX = 100;
int array[];
int rear;
int front;
int size;
public Deque(int size) {
array = new int[MAX];
front = -1;
rear = 0;
this.size = size;
}
boolean isFull() {
if (front == 0 && rear == size - 1)
return true;
if (front == rear + 1)
return false;
return false;
}
boolean isEmpty() {
if (front == -1)
return true;
return false;
}
void InsertRear(int element) {
if (isFull()) {
System.out.println("Overflow");
return;
}
if (rear == size - 1) {
rear = 0;
} else if (front == -1) {
rear = 0;
front = 0;
} else {
rear++;
}
array[rear] = element;
}
void InsertFront(int element) {
if (isFull()) {
System.out.println("Overflow");
return;
}
if (front == 0) {
front = size - 1;
} else if (front == -1) {
rear = 0;
front = 0;
} else {
front--;
}
array[front] = element;
}
void DeleteFront() {
if (isEmpty()) {
System.out.println("Underflow");
return;
}
if (front == size - 1) {
front = 0;
} else if (front == rear) {
rear = -1;
front = -1;
} else {
front++;
}
}
void DeleteRear() {
if (isEmpty()) {
System.out.println("Underflow");
return;
}
if (rear == 0) {
rear = size - 1;
} else if (front == rear) {
rear = -1;
front = -1;
} else {
rear--;
}
}
int GetRear() {
if (rear < 0) {
System.out.println("Underflow");
return -1;
}
if (isEmpty()) {
System.out.println("Underflow");
return -1;
}
return array[rear];
}
int GetFront() {
if (isEmpty()) {
System.out.println("Underflow");
return -1;
}
return array[front];
}
public static void main(String[] args) {
Deque dq = new Deque(30);
System.out.println("Inserting element at front end");
dq.InsertFront(100);
System.out.println("Getting front element " + dq.GetFront());
dq.DeleteFront();
System.out.println("After deleting front element new front will be " +
dq.GetFront());
System.out.println("Inserting element at rear end : 50");
dq.InsertRear(50);
System.out.println("Inserting element at rear end : 10");
dq.InsertRear(10);
System.out.println("Rear element " + dq.GetRear());
dq.DeleteRear();
System.out.println("After deleting rear element new rear will be " + dq.GetRear
());
}
}
Time Complexity : Operations like InsertRear(), InsertFront() , DeleteRear(), DeleteFront() have time complexity of O(1) (Constant).
Space Complexity: O(1)
Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article