Double-Ended Queue (Deque)

A Deque (pronounced as “deck”) stands for Double-Ended Queue. It is a linear data structure in which insertion and deletion operations can be performed from both the front and rear ends.

A deque combines the features of

• Queue → FIFO (First In First Out)
• Stack → LIFO (Last In First Out)

Because of this flexibility, deque is considered one of the most powerful queue variations.

Basic Idea of Deque

In a normal queue:

• Insertion occurs only from the rear
• Deletion occurs only from the front

But in a deque:

• Insertion can happen from both ends
• Deletion can happen from both ends

This provides greater flexibility in data handling.

Structure of Deque

A deque usually contains two pointers:

Deque can be implemented using:

1. Array
2. Circular Array
3. Doubly Linked List

The Circular Array implementation is the most common because it efficiently utilizes memory.

Types of Deque

1. Input Restricted Deque

In this type:

• Insertion is allowed only from one end
• Deletion is allowed from both ends

Allowed Operations

Example

Suppose the deque contains:

10 20 30

Allowed:

• Insert at rear → 10 20 30 40
• Delete from front → 20 30
• Delete from rear → 10 20

Not Allowed:

• Insert at front

2. Output Restricted Deque

In this type:

• Insertion is allowed from both ends
• Deletion is allowed from only one end

Allowed Operations

Example

Deque:

10 20 30

Allowed:

• Insert Front → 5 10 20 30
• Insert Rear → 10 20 30 40
• Delete Front → 20 30

Not Allowed:

• Delete Rear

3. Simple or Regular Deque

This is the normal deque where:

• Insertion is allowed from both ends
• Deletion is allowed from both ends

Allowed Operations

This is the most commonly used type of deque.

Operations of Deque

1. Insert Front

This operation inserts an element at the front side of the deque.

Working Process

• Move front pointer backward
• Insert new element at the front

Example

Initial deque:

20 30 40

Insert Front(10)

Result:

10 20 30 40

Step-by-Step Explanation

Algorithm

INSERT_FRONT(value)

1. Check if deque is full
2. If empty:
       front = rear = 0
3. Else move front backward
4. Insert value at front

2. Insert Rear

This operation inserts an element at the rear side.

Working Process

• Move rear pointer forward
• Insert new element at rear

Example

Initial deque:

10 20 30

Insert Rear(40)

Result:

10 20 30 40

Step-by-Step Explanation

Algorithm

INSERT_REAR(value)

1. Check if deque is full
2. If empty:
       front = rear = 0
3. Else move rear forward
4. Insert value at rear

3. Delete Front

This operation removes the front element.

Working Process

• Remove front element
• Move front pointer forward

Example

Initial deque:

10 20 30 40

Delete Front()

Result:

20 30 40

Step-by-Step Explanation

Algorithm

DELETE_FRONT()

1. Check if deque is empty
2. Remove front element
3. Move front pointer forward
4. Update front position

4. Delete Rear

This operation removes the rear element.

Working Process

• Remove rear element
• Move rear pointer backward

Example

Initial deque:

10 20 30 40

Delete Rear()

Result:

10 20 30

Step-by-Step Explanation

Algorithm

DELETE_REAR()

1. Check if deque is empty
2. Remove rear element
3. Move rear backward
4. Update rear position

5. Peek Front

This operation displays the front element without deleting it.

Example

Deque:

10 20 30

Peek Front = 10

Explanation

• Front element is simply accessed
• No deletion occurs
• Deque remains unchanged

Algorithm

PEEK_FRONT()

1. Check if deque is empty
2. Return front element

6. Peek Rear

This operation displays the rear element without deleting it.

Example

Deque:

10 20 30

Peek Rear = 30

Explanation

• Rear element is accessed directly
• No modification occurs in deque

Algorithm

PEEK_REAR()

1. Check if deque is empty
2. Return rear element

7. isEmpty()

Checks whether deque contains elements or not.

Condition

front == -1

If true:

• Deque is empty

Otherwise:

• Deque contains elements

8. isFull()

Checks whether deque is full.

Circular Queue Full Condition

(front == (rear + 1) % SIZE)

This condition occurs when no empty space remains in the circular array.

Circular Array Representation of Deque

Deque is commonly implemented using circular arrays.

Why Circular Array?

In a simple array implementation:

• Wasted memory occurs after deletion

Circular array solves this by:

• Reusing empty positions
• Wrapping indices around the array

Example

Array Size = 5

Index:   0   1   2   3   4
Data :  10  20  30  --  --

After deleting 10 and inserting 40:

Index:   0   1   2   3   4
Data :  40  20  30  --  --

The array behaves like a circle.

Time Complexity of Deque Operations

Deque operations are very efficient because insertion and deletion happen directly at the ends.

Applications of Deque

Deque is widely used in computer science and real-world systems.

Common Applications

1. Undo and Redo Operations

Text editors use deque for:

• Undo
• Redo functionality

2. Browser History

Web browsers use deque to:

• Move backward
• Move forward

3. CPU Scheduling

Tasks can be inserted or removed from both ends depending on priority.

4. Sliding Window Problems

Deque is heavily used in:

• Maximum sliding window problems
• Competitive programming

5. Palindrome Checking

Characters can be compared from both front and rear.

Advantages of Deque

• Fast insertion and deletion
• Flexible operations
• Can work as stack and queue
• Efficient memory usage with circular arrays

Disadvantages of Deque

• More complex than simple queue
• Circular implementation can be difficult
• Requires careful pointer management

C Program for Deque Using Circular Array

#include <stdio.h>

#define SIZE 5

int deque[SIZE];
int front = -1;
int rear = -1;

int isFull() {
    return ((rear + 1) % SIZE == front);
}

int isEmpty() {
    return (front == -1);
}

void insertFront(int value) {

    if(isFull()) {
        printf("Deque Overflow\n");
        return;
    }

    if(isEmpty()) {
        front = rear = 0;
    }
    else if(front == 0) {
        front = SIZE - 1;
    }
    else {
        front--;
    }

    deque[front] = value;
}

void insertRear(int value) {

    if(isFull()) {
        printf("Deque Overflow\n");
        return;
    }

    if(isEmpty()) {
        front = rear = 0;
    }
    else {
        rear = (rear + 1) % SIZE;
    }

    deque[rear] = value;
}

void deleteFront() {

    if(isEmpty()) {
        printf("Deque Underflow\n");
        return;
    }

    printf("Deleted Element = %d\n", deque[front]);

    if(front == rear) {
        front = rear = -1;
    }
    else {
        front = (front + 1) % SIZE;
    }
}

void deleteRear() {

    if(isEmpty()) {
        printf("Deque Underflow\n");
        return;
    }

    printf("Deleted Element = %d\n", deque[rear]);

    if(front == rear) {
        front = rear = -1;
    }
    else if(rear == 0) {
        rear = SIZE - 1;
    }
    else {
        rear--;
    }
}

void display() {

    if(isEmpty()) {
        printf("Deque is Empty\n");
        return;
    }

    int i = front;

    printf("Deque Elements: ");

    while(1) {

        printf("%d ", deque[i]);

        if(i == rear)
            break;

        i = (i + 1) % SIZE;
    }

    printf("\n");
}

int main() {

    insertRear(10);
    insertRear(20);
    insertFront(5);
    insertRear(30);

    display();

    deleteFront();

    display();

    deleteRear();

    display();

    return 0;
}

Output

Deque Elements: 5 10 20 30

Deleted Element = 5
Deque Elements: 10 20 30

Deleted Element = 30
Deque Elements: 10 20