What is Double ended queue / deque in Data Structures
Apart from the conventional queue in data structures that follows the principle of first in first out, we have a special and updated version of the queue that violates this principle. Here, insertion and deletion are possible at both ends.
Why do we need deque in Data Structures?
One practical application of deque is to handle data that needs to be pruned after some time. Eg- a browser’s history.
The recently visited sites are added at one end, say the rear. Now we obviously want a limit on the number of sites which are stored in our history deque. So when that limit is reached, the elements at the front are removed from the deque, to accommodate new insertions. This is where a deque is useful over a stack in data structures.
But we may also want to remove the newly visited sites at the rear of our history deque. This is where a deque is useful over a queue.
So you see, a deque provides the functionality of both a stack and a queue, and is useful where both of them can’t provide efficient solutions on their own.
There are some other applications too like job scheduling, which use a deque.
Further, it is classified into input-restricted and output-restricted. The queue where input is possible from one end only but deletion is done from both ends is called input restricted. Whereas, if the output is restricted from one end but insertion can be done on both ends is called output restricted queue.
Operations on deque –
Before performing operations of enqueue, and dequeue, we need to initialize some pointers in the doubly-ended queue which is popularly known as deque.
Take an array (deque) of size n.
Set two pointers at the first position and set front = -1 and rear = 0.
Now, the following operations are performed –
- Insertion at the front
- Check the position of the front.
- If front < 1, reinitialize front = n-1 (last index).
Else, decrease front by 1.
- Add the new key into the array[front]
- Insertion at the rear end
- Check if the array is full.
- If the deque is full, reinitialize rear = 0.
- Else, increase the rear by 1.
- Add the new key into the array[rear].
- Deletion from the front
- Check if the deque is empty.
- If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
- If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.
- Else if the front is at the end (i.e. front = n – 1), set go to the front = 0.
- Else, front = front + 1.
- Deletion from Rear
- Check if the deque is empty.
- If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
- If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else follow the steps below.
- If the rear is at the front (i.e. rear = 0), set go to the front-rear = n – 1.
- Else, rear = rear – 1
- Check Empty
This operation checks if the deque is empty. If front = -1, the deque is empty.
- Check Full
This operation checks if the deque is full. If front = 0 and rear = n – 1 OR front = rear + 1, the deque is full.
Deque Programming example
#include <iostream>
using namespace std;
#define MAX 10
class Deque {
int arr[MAX];
int front;
int rear;
int size;
public:
Deque(int size) {
front = -1;
rear = 0;
this->size = size;
}
void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();
};
bool Deque::isFull() {
return ((front == 0 && rear == size - 1) ||
front == rear + 1);
}
bool Deque::isEmpty() {
return (front == -1);
}
void Deque::insertfront(int key) {
if (isFull()) {
cout << "Overflow\n"
<< endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (front == 0)
front = size - 1;
else
front = front - 1;
arr[front] = key;
}
void Deque ::insertrear(int key) {
if (isFull()) {
cout << " Overflow\n " << endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (rear == size - 1)
rear = 0;
else
rear = rear + 1;
arr[rear] = key;
}
void Deque ::deletefront() {
if (isEmpty()) {
cout << "Queue Underflow\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1)
front = 0;
else
front = front + 1;
}
void Deque::deleterear() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
int Deque::getFront() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[front];
}
int Deque::getRear() {
if (isEmpty() || rear < 0) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[rear];
}
int main() {
Deque dq(4);
cout << "insert element at rear end \n";
dq.insertrear(5);
dq.insertrear(11);
cout << "rear element: "
<< dq.getRear() << endl;
dq.deleterear();
cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;
cout << "insert element at front end \n";
dq.insertfront(8);
cout << "front element: " << dq.getFront() << endl;
dq.deletefront();
cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}
Time Complexity of deque
The time complexity of all the operations in O(1) in each case.
Applications of Dequeue in Data Structure –
- In undo operations on the software.
- To store history in browsers.
- For implementing both stacks and queues.
Try this quiz
