Mental Model

A deque lets you add or remove items from both the front and the back easily.

Analogy: Think of a line of people where you can join or leave from either the front or the end of the line.

front -> [ ] -> [ ] -> [ ] -> back
↑head                        ↑tail

Dry Run Walkthrough

Input: Start with empty deque, then add 10 at front, add 20 at back, add 5 at front, remove from back

Goal: Show how items are added and removed from both ends of the deque

Step 1: Add 10 at front

front -> [10] -> back
↑head/tail

Why: First element goes to both front and back

Step 2: Add 20 at back

front -> [10] -> [20] -> back
↑head          ↑tail

Why: Add new element after tail at the back

Step 3: Add 5 at front

front -> [5] -> [10] -> [20] -> back
↑head               ↑tail

Why: Add new element before head at the front

Step 4: Remove from back

front -> [5] -> [10] -> back
↑head          ↑tail

Why: Remove last element to shrink deque from back

Result:

front -> [5] -> [10] -> back
↑head          ↑tail

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

typedef struct {
    int arr[MAX];
    int front;
    int rear;
} Deque;

void initDeque(Deque* dq) {
    dq->front = -1;
    dq->rear = -1;
}

int isEmpty(Deque* dq) {
    return dq->front == -1;
}

int isFull(Deque* dq) {
    return ((dq->front == 0 && dq->rear == MAX - 1) || (dq->front == dq->rear + 1));
}

void addFront(Deque* dq, int val) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->front == 0) {
        dq->front = MAX - 1;
    } else {
        dq->front = dq->front - 1;
    }
    dq->arr[dq->front] = val;
}

void addRear(Deque* dq, int val) {
    if (isFull(dq)) {
        printf("Deque is full\n");
        return;
    }
    if (isEmpty(dq)) {
        dq->front = 0;
        dq->rear = 0;
    } else if (dq->rear == MAX - 1) {
        dq->rear = 0;
    } else {
        dq->rear = dq->rear + 1;
    }
    dq->arr[dq->rear] = val;
}

void removeFront(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    } else if (dq->front == MAX - 1) {
        dq->front = 0;
    } else {
        dq->front = dq->front + 1;
    }
}

void removeRear(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    if (dq->front == dq->rear) {
        dq->front = -1;
        dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    } else {
        dq->rear = dq->rear - 1;
    }
}

void printDeque(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    int i = dq->front;
    printf("Deque: ");
    while (1) {
        printf("%d ", dq->arr[i]);
        if (i == dq->rear) break;
        i = (i + 1) % MAX;
    }
    printf("\n");
}

int main() {
    Deque dq;
    initDeque(&dq);

    addFront(&dq, 10);  // Step 1
    printDeque(&dq);

    addRear(&dq, 20);   // Step 2
    printDeque(&dq);

    addFront(&dq, 5);   // Step 3
    printDeque(&dq);

    removeRear(&dq);    // Step 4
    printDeque(&dq);

    return 0;
}

if (isFull(dq)) { ... return; }

check if deque is full before adding

if (isEmpty(dq)) { dq->front = 0; dq->rear = 0; }

initialize front and rear when deque was empty

dq->front = (dq->front == 0) ? MAX - 1 : dq->front - 1;

move front pointer backward circularly for addFront

dq->rear = (dq->rear == MAX - 1) ? 0 : dq->rear + 1;

move rear pointer forward circularly for addRear

if (dq->front == dq->rear) { dq->front = -1; dq->rear = -1; }

reset deque to empty when last element removed

dq->front = (dq->front == MAX - 1) ? 0 : dq->front + 1;

move front pointer forward circularly for removeFront

dq->rear = (dq->rear == 0) ? MAX - 1 : dq->rear - 1;

move rear pointer backward circularly for removeRear

while (1) { print arr[i]; if (i == rear) break; i = (i + 1) % MAX; }

iterate circularly from front to rear to print deque

OutputSuccess

Deque: 10 Deque: 10 20 Deque: 5 10 20 Deque: 5 10

Complexity Analysis

Time: O(1) for add and remove operations because pointers move without shifting elements

Space: O(n) because we store up to n elements in the fixed-size array

vs Alternative: Compared to a normal queue that only adds/removes at one end, deque supports both ends with same O(1) cost

Edge Cases

empty deque

add operations initialize front and rear; remove operations print empty message

DSA C

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

deque full

add operations print full message and do not add

DSA C

if (isFull(dq)) { printf("Deque is full\n"); return; }

removing last element

front and rear reset to -1 to mark empty

DSA C

if (dq->front == dq->rear) { dq->front = -1; dq->rear = -1; }

When to Use This Pattern

When a problem needs adding or removing items from both ends efficiently, use a deque to handle both ends in constant time.

Common Mistakes

Mistake: Not handling wrap-around when front or rear reaches array ends
Fix: Use modulo or conditional logic to wrap pointers circularly within array bounds

Mistake: Not resetting front and rear to -1 when deque becomes empty
Fix: Check if front equals rear on removal and reset both to -1

Summary

A deque lets you add or remove elements from both front and back quickly.

Use it when you need flexible insertion and deletion at both ends of a list.

The key is to move front and rear pointers circularly to reuse array space efficiently.