Double Ended Queue Deque in DSA C

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

Output

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.

Practice

1. What is a Double Ended Queue (Deque)?

easy

A. A queue where insertion happens only at the rear and deletion at the front

B. A data structure where insertion and deletion can happen at both ends

C. A stack where insertion and deletion happen only at one end

D. A list that allows random access to elements

Solution

1. Step 1: Understand the definition of Deque

   A Deque allows adding and removing elements from both front and rear ends.

2. Step 2: Compare with other data structures

   Unlike a queue or stack, Deque supports operations at both ends.

3. Final Answer:

   A data structure where insertion and deletion can happen at both ends -> Option B

4. Quick Check:

   Deque = Both ends insertion/deletion [OK]

Hint: Deque means double-ended queue, both ends allowed [OK]

Common Mistakes:

• Confusing deque with stack or queue
• Thinking insertion is only at one end
• Assuming random access like arrays

2. Which of the following is the correct syntax to initialize an empty deque in C using an array implementation?

easy

A. int deque[] = {}; int front = 0, rear = 0;

B. int deque[SIZE] = NULL; int front = 0, rear = 0;

C. int deque[SIZE]; int front = -1, rear = -1;

D. int deque[SIZE]; int front = 0, rear = -1;

Solution

1. Step 1: Understand initialization of deque with front and rear

   Front and rear are set to -1 to indicate empty deque.

2. Step 2: Check array declaration and initial values

   int deque[SIZE]; int front = -1, rear = -1; correctly declares array and sets front and rear to -1.

3. Final Answer:

   int deque[SIZE]; int front = -1, rear = -1; -> Option C

4. Quick Check:

   Empty deque front and rear = -1 [OK]

Hint: Empty deque front and rear start at -1 [OK]

Common Mistakes:

• Setting front or rear to 0 initially
• Using NULL for array initialization
• Leaving array size unspecified

3. Consider the following operations on an empty deque of size 5 implemented using an array:
insertRear(10); insertRear(20); insertFront(5); deleteRear(); insertFront(15);
What is the content of the deque from front to rear after these operations?

medium

A. 15 -> 5 -> 10 -> null

B. 5 -> 15 -> 10 -> null

C. 15 -> 5 -> null

D. 10 -> 5 -> 15 -> null

Solution

1. Step 1: Perform insertRear(10) and insertRear(20)

   Deque: 10 -> 20

2. Step 2: Perform insertFront(5)

   Deque: 5 -> 10 -> 20

3. Step 3: Perform deleteRear()

   Removes 20, Deque: 5 -> 10

4. Step 4: Perform insertFront(15)

   Deque: 15 -> 5 -> 10

5. Final Answer:

   15 -> 5 -> 10 -> null -> Option A

6. Quick Check:

   Operations result in 15,5,10 order [OK]

Hint: Track front and rear insertions stepwise [OK]

Common Mistakes:

• Forgetting deleteRear removes last element
• Mixing order of insertFront and insertRear
• Assuming insertFront adds at rear

4. Given the following code snippet for deque insertion at front, identify the error:

void insertFront(int deque[], int *front, int *rear, int value) {
  if (*front == 0) {
    printf("Deque is full at front\n");
    return;
  }
  (*front)--;
  deque[*front] = value;
}

medium

A. It incorrectly checks full condition only at front == 0

B. It decrements front before insertion causing invalid index

C. It does not check if deque is empty before insertion

D. It should increment front instead of decrement

Solution

1. Step 1: Analyze the full condition check

   Checking only if front == 0 is not enough to detect full deque.

2. Step 2: Understand circular deque logic

   Deque can be full even if front != 0, so this check is incomplete.

3. Final Answer:

   It incorrectly checks full condition only at front == 0 -> Option A

4. Quick Check:

   Full check must consider rear position too [OK]

Hint: Full deque check needs both front and rear positions [OK]

Common Mistakes:

• Assuming front == 0 means full always
• Not handling circular wrap-around
• Decrementing front without boundary check

5. You have a deque of size 4 implemented using a circular array. Initially empty, you perform:
insertRear(1); insertRear(2); insertFront(3); insertFront(4); deleteRear(); insertRear(5);
What is the final state of the deque from front to rear?

hard

A. 4 -> 3 -> 1 -> null

B. 4 -> 3 -> 5 -> null

C. 3 -> 4 -> 1 -> 5 -> null

D. 4 -> 3 -> 1 -> 5 -> null

Solution

1. Step 1: InsertRear(1), InsertRear(2)

   Deque: 1 -> 2

2. Step 2: InsertFront(3), InsertFront(4)

   Deque: 4 -> 3 -> 1 -> 2 (deque full)

3. Step 3: DeleteRear()

   Removes 2, Deque: 4 -> 3 -> 1

4. Step 4: InsertRear(5)

   Deque: 4 -> 3 -> 1 -> 5 (full again)

5. Final Answer:

   4 -> 3 -> 1 -> 5 -> null -> Option D

6. Quick Check:

   Circular deque final state matches 4 -> 3 -> 1 -> 5 -> null [OK]

Hint: Track circular wrap and full capacity carefully [OK]

Common Mistakes:

• Ignoring circular wrap-around
• Misordering front and rear elements
• Forgetting deleteRear removes last element