A Deque (Double-Ended Queue) is a type of linear data structure that allows insertion and deletion of elements from both the front and the rear ends. Unlike a standard queue, it does not strictly follow the FIFO (First In, First Out) principle.
Types of Deque
Input Restricted Deque
In this deque, input is restricted at a single end but allows deletion at both the ends.Output Restricted Deque
In this deque, output is restricted at a single end but allows insertion at both the ends.
Operations on a Deque
Below is the circular array implementation of deque. In a circular array, if the array is full, we start from the beginning.
But in a linear array implementation, if the array is full, no more elements can be inserted. In each of the operations below, if the array is full, "overflow message" is thrown.
Before performing the following operations, these steps are followed.
- Take an array (deque) of size
n
. Set two pointersfront = -1
andrear = 0
.
1. Insert at the Front
This operation adds an element at the front.
- Check if the deque is full.
- If the deque is full (i.e.
(front == 0 && rear == n - 1) || (front == rear + 1)
), insertion operation cannot be performed (overflow condition). - If the deque is empty, reinitialize
front = 0
. And, add the new key intoarray[front]
. - If
front = 0
, reinitializefront = n-1
(last index).
- Else, decrease
front
by 1. - Add the new key
5
intoarray[front]
.
2. Insert at the Rear
This operation adds an element to the rear.
If the deque is full, insertion operation cannot be performed (overflow condition).
If the deque is empty, reinitialize
rear = 0
. And, add the new key intoarray[rear]
.If
rear = n - 1
, reinitializereal = 0
(first index).Else, increase
rear
by 1.
- Add the new key
5
intoarray[rear]
.
3. Delete from the Front
The operation deletes an element 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
), setfront = -1
andrear = -1
. - Else if front is at the last index (i.e.
front = n - 1
), setfront = 0
. - Else,
front = front + 1
.
4. Delete from the Rear
This operation deletes an element from the 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
), setfront = -1
andrear = -1
, else follow the steps below. - If rear is at the first index (i.e.
rear = 0
), reinitializerear = n - 1
. - Else,
rear = rear - 1
5. Check Empty
This operation checks if the deque is empty. If front = -1
, the deque is empty.
6. 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 Code:
class Deque {
constructor(size) {
this.size = size;
this.arr = new Array(size);
this.front = -1;
this.rear = 0;
}
isFull() {
return (
(this.front === 0 && this.rear === this.size - 1) ||
this.front === this.rear + 1
);
}
isEmpty() {
return this.front === -1;
}
insertFront(key) {
if (this.isFull()) {
console.log('Overflow! Cannot insert at front');
return;
}
if (this.isEmpty()) {
this.front = 0;
this.rear = 0;
} else if (this.front === 0) {
this.front = this.size - 1;
} else {
this.front--;
}
this.arr[this.front] = key;
console.log(`Inserted ${key} at front`);
}
insertRear(key) {
if (this.isFull()) {
console.log('Overflow! Cannot insert at rear');
return;
}
if (this.isEmpty()) {
this.front = 0;
this.rear = 0;
} else if (this.rear === this.size - 1) {
this.rear = 0;
} else {
this.rear++;
}
this.arr[this.rear] = key;
console.log(`Inserted ${key} at rear`);
}
deleteFront() {
if (this.isEmpty()) {
console.log('Underflow! Cannot delete from front');
return;
}
console.log('Deleting from front...', this.front);
const removed = this.arr[this.front];
this.arr[this.front] = null; // <-- clear the slot
if (this.front === this.rear) {
this.front = -1;
this.rear = -1;
} else if (this.front === this.size - 1) {
this.front = 0;
} else {
this.front++;
}
console.log(`Deleted ${removed} from front`, this.arr);
}
deleteRear() {
if (this.isEmpty()) {
console.log('Underflow! Cannot delete from rear');
return;
}
const removed = this.arr[this.rear];
this.arr[this.rear] = null; // <-- clear the slot
if (this.front === this.rear) {
this.front = -1;
this.rear = -1;
} else if (this.rear === 0) {
this.rear = this.size - 1;
} else {
this.rear--;
}
console.log(`Deleted ${removed} from rear`);
}
getFront() {
if (this.isEmpty()) {
console.log('Deque is empty');
return null;
}
return this.arr[this.front];
}
getRear() {
if (this.isEmpty()) {
console.log('Deque is empty');
return null;
}
return this.arr[this.rear];
}
printDeque() {
if (this.isEmpty()) {
console.log('Deque is empty');
return;
}
let i = this.front;
let result = [];
while (true) {
result.push(this.arr[i]);
if (i === this.rear) break;
i = (i + 1) % this.size;
}
console.log('Deque contents:', result.join(' -> '));
}
}
// Example usage:
const dq = new Deque(4);
dq.insertFront(5);
dq.insertRear(6);
dq.insertRear(7);
dq.insertFront(8);
dq.printDeque(); // Expected: 2 -> 5 -> 10 -> 20
dq.deleteRear(); // Expected: Deleted 20
dq.deleteFront(); // Expected: Deleted 2
dq.printDeque(); // Expected: 5 -> 10
Time Complexity
The time complexity of all the above operations is constant i.e. O(1).
Applications of Deque Data Structure
- In undo operations on software.
- To store history in browsers.
- For implementing both stacks and queues.
Top comments (0)