Double-Ended Queue (Deque)
A deque (pronounced deck), short for double-ended queue, is a linear data structure that allows you to add or remove elements from both the front and the rear ends.
Unlike a regular queue (which only allows insertion at the rear and deletion at the front, following the FIFO (First In, First Out) principle, a deque gives you maximum flexibility by supporting insertion and deletion at either end.
This flexibility makes the deque a general-purpose data structure that combines the behavior of both queues and stacks.
For example, you can use it as a stack (LIFO) if you only operate on one end, or as a standard queue (FIFO) if you restrict insertions to one side and deletions to the other.
Internal Structure
In most implementations, a deque is built using either:
- A circular array, where the front and rear indices wrap around when they reach the array boundaries, or
- A doubly linked list, which has explicit next and previous pointers connecting nodes.
Types of Double-Ended Queues (Deque)
Although all deques allow insertion and deletion at both ends, we can classify them into two main types based on which operations are restricted or allowed at each end.
1. Input-Restricted Deque
An input-restricted deque is a type of deque where Insertion is allowed only at one end (usually the rear) and Deletion is allowed at both ends (front and rear).
- Push new elements only from the rear.
- Remove elements from either the front or the rear.
Example: Imagine a system where new tasks can only be added in the usual order (at the back of the line), but cancellations or priority removals can happen from either end.
Useful: It controls how data enters the system but gives flexibility in clearing or removing data.
2. Output-Restricted Deque
An output-restricted deque is the opposite. Insertion is allowed at both ends (front and rear) and Deletion is allowed only at one end (usually the front).
- Add new elements either to the front or the rear.
- Remove elements only from the front.
Example: Think of a buffer where incoming data can be prioritized (added to the front) or come in normally (added to the rear), but processing always happens from the front.
Useful: It gives full control over how data is added but restricts how it’s consumed, ensuring order.
3. Regular Deque (Unrestricted)
In contrast, a general deque allows Insertion at both ends and Deletion at both ends.
This is the most flexible version and is what people usually refer to when they just say “deque.”
Operations of Double-Ended Queue (Deque)
In an array-based deque, four main data operations are supported:
1. Insert Front
You add a new element just before the current front position. This requires moving the front index backward (circularly), which means computing (front - 1 + size) % size. If the deque is initially empty, both front and rear are set to zero.
Algorithm
if (front == (rear + 1) % size) then
print "Deque is full"
return
end if
if front == -1 then
front ← 0
rear ← 0
else if front == 0 then
front ← size - 1
else
front ← front - 1
end if
deque[front] ← value2. Insert Rear
You add a new element just after the current rear position. This requires moving the rear index forward, computed as (rear + 1) % size. Again, if the deque was empty, both front and rear are set to zero.
Algorithm
if (front == (rear + 1) % size) then
print "Deque is full"
return
end if
if front == -1 then
front ← 0
rear ← 0
else if rear == size - 1 then
rear ← 0
else
rear ← rear + 1
end if
deque[rear] ← value
3. Delete Front
You remove the element currently at the front index. After removal, you move the front index forward: (front + 1) % size. If after deletion the deque becomes empty (meaning front == rear), both indices are reset to -1.
Algorithm
if front == -1 then
print "Deque is empty"
return
end if
print "Deleted Element:", deque[front]
if front == rear then
// Only one element was in deque
front ← -1
rear ← -1
else
front ← (front + 1) % size
end if
4. Delete Rear
You remove the element at the rear index. After removal, you move the rear index backward: (rear - 1 + size) % size. Again, if the deque becomes empty, both indices are reset.
Algorithm:
if front == -1 then
print "Deque is empty"
return
end if
print "Deleted Element:", deque[rear]
if front == rear then
// Only one element was in deque
front ← -1
rear ← -1
else
rear ← (rear - 1 + size) % size
end if
5. Peek Front
Check (or read) the element at the front of the deque without removing it.
This is useful when you want to know what’s next to be processed but don’t want to change the deque state.
Algorithm
if front == -1 then
print "Deque is empty"
return
end if
print "Front Element:", deque[front]
- We first check if the deque is empty by checking if
front == -1. - If empty, we report that there’s no element to peek.
- Otherwise, we simply access the value at
deque[front]and display or return it no deletion or shifting.
Additionally, peek operations are often supported (getFront() and getRear()), allowing access to the elements at both ends without modifying the structure.
6. Peek Rear
Check (or read) the element at the rear of the deque without removing it.
This is useful when you want to know what was most recently added at the back.
Algorithm
if front == -1 then
print "Deque is empty"
return
end if
print "Rear Element:", deque[rear]
- we first check if the deque is empty by checking
front == -1. - If empty, we report no element to peek.
- Otherwise, we access the value at
deque[rear]and display or return it.
Real-World Applications
Deques are useful in many real-world problems:
- Text editors, for managing undo/redo operations.
- Web browsers, to track forward and backward navigation history.
- Scheduling systems, where tasks might need to be prioritized by pushing to the front or added regularly at the rear.
- Algorithmic problems, such as finding the maximum in a sliding window over an array.
Deque Implementation in C Programming Deque (Circular Array-Based Deque)
#include <stdio.h>
#define SIZE 5
int deque[SIZE];
int front = -1, rear = -1;
// Check if deque is full
int isFull() {
return (front == (rear + 1) % SIZE);
}
// Check if deque is empty
int isEmpty() {
return (front == -1);
}
// Insert at front
void insertFront(int value) {
if (isFull()) {
printf("Deque is full\n");
return;
}
if (isEmpty()) {
front = rear = 0;
} else if (front == 0) {
front = SIZE - 1;
} else {
front--;
}
deque[front] = value;
}
// Insert at rear
void insertRear(int value) {
if (isFull()) {
printf("Deque is full\n");
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % SIZE;
}
deque[rear] = value;
}
// Delete from front
void deleteFront() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
printf("Deleted from front: %d\n", deque[front]);
if (front == rear) {
front = rear = -1; // Now empty
} else {
front = (front + 1) % SIZE;
}
}
// Delete from rear
void deleteRear() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
printf("Deleted from rear: %d\n", deque[rear]);
if (front == rear) {
front = rear = -1; // Now empty
} else if (rear == 0) {
rear = SIZE - 1;
} else {
rear--;
}
}
// Peek front
void peekFront() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
printf("Front element: %d\n", deque[front]);
}
// Peek rear
void peekRear() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
printf("Rear element: %d\n", deque[rear]);
}
// Display deque
void display() {
if (isEmpty()) {
printf("Deque is empty\n");
return;
}
printf("Deque elements: ");
int i = front;
while (1) {
printf("%d ", deque[i]);
if (i == rear)
break;
i = (i + 1) % SIZE;
}
printf("\n");
}
// Main function to test
int main() {
insertRear(10);
insertRear(20);
insertFront(5);
insertFront(2);
display();
peekFront();
peekRear();
deleteFront();
deleteRear();
display();
insertRear(30);
insertRear(40);
display();
insertRear(50); // Should show full
deleteFront();
insertRear(60);
display();
return 0;
}