Mental Model

A dequeue lets you add or remove items from both ends, like a line where people can enter or leave from front or back.

Analogy: Imagine a double-ended queue as a hallway with doors at both ends. People can enter or exit from either door, not just one side.

front -> [1] -> [2] -> [3] ← rear
↑front pointer          ↑rear pointer

Dry Run Walkthrough

Input: dequeue with elements 1 -> 2 -> 3, perform dequeue from front and then from rear

Goal: Remove one element from the front and one from the rear, showing how the structure updates

Step 1: Remove element from front

front removed 1 -> 2 -> 3 ← rear
front now points to 2

Why: We remove the first element to simulate dequeue from front

Step 2: Remove element from rear

2 -> 3 removed from rear
front -> 2 ← rear now points to 2

Why: We remove the last element to simulate dequeue from rear

Result:

2 ← front and rear point to the same single element
final dequeue state: 2 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

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

void init(Dequeue* dq) {
    dq->front = -1;
    dq->rear = -1;
}

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

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

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

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

int dequeueFront(Dequeue* dq) {
    if (isEmpty(dq)) {
        printf("Dequeue is empty\n");
        return -1;
    }
    int data = dq->arr[dq->front];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->front == MAX - 1) {
        dq->front = 0;
    } else {
        dq->front++;
    }
    return data;
}

int dequeueRear(Dequeue* dq) {
    if (isEmpty(dq)) {
        printf("Dequeue is empty\n");
        return -1;
    }
    int data = dq->arr[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else if (dq->rear == 0) {
        dq->rear = MAX - 1;
    } else {
        dq->rear--;
    }
    return data;
}

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

int main() {
    Dequeue dq;
    init(&dq);
    enqueueRear(&dq, 1);
    enqueueRear(&dq, 2);
    enqueueRear(&dq, 3);
    printDequeue(&dq);

    int frontVal = dequeueFront(&dq);
    printf("Dequeued from front: %d\n", frontVal);
    printDequeue(&dq);

    int rearVal = dequeueRear(&dq);
    printf("Dequeued from rear: %d\n", rearVal);
    printDequeue(&dq);

    return 0;
}

if (isEmpty(dq)) { dq->front = dq->rear = 0; } else if (dq->rear == MAX - 1) { dq->rear = 0; } else { dq->rear++; } dq->arr[dq->rear] = value;

advance rear pointer circularly and insert value at rear

if (isEmpty(dq)) { dq->front = dq->rear = 0; } else if (dq->front == 0) { dq->front = MAX - 1; } else { dq->front--; } dq->arr[dq->front] = value;

move front pointer backward circularly and insert value at front

int data = dq->arr[dq->front]; if (dq->front == dq->rear) { dq->front = dq->rear = -1; } else if (dq->front == MAX - 1) { dq->front = 0; } else { dq->front++; } return data;

remove element at front and update front pointer circularly

int data = dq->arr[dq->rear]; if (dq->front == dq->rear) { dq->front = dq->rear = -1; } else if (dq->rear == 0) { dq->rear = MAX - 1; } else { dq->rear--; } return data;

remove element at rear and update rear pointer circularly

OutputSuccess

Dequeue elements: 1 2 3 Dequeued from front: 1 Dequeue elements: 2 3 Dequeued from rear: 3 Dequeue elements: 2

Complexity Analysis

Time: O(1) because dequeue operations just move pointers without traversing

Space: O(MAX) fixed size array used for storage

vs Alternative: Compared to linked list dequeue, array-based dequeue uses fixed space but faster index access; linked list uses dynamic space but more pointer overhead

Edge Cases

empty dequeue

dequeue operations print 'Dequeue is empty' and return -1

DSA C

if (isEmpty(dq)) { printf("Dequeue is empty\n"); return -1; }

single element dequeue

removing that element resets front and rear to -1 indicating empty

DSA C

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

front or rear pointer wrap around

pointers wrap circularly to start or end of array

DSA C

else if (dq->front == MAX - 1) { dq->front = 0; } and else if (dq->rear == 0) { dq->rear = MAX - 1; }

When to Use This Pattern

When you need to add or remove items from both ends efficiently, look for dequeue operations because they allow double-ended access with constant time updates.

Common Mistakes

Mistake: Not handling the circular wrap-around of front and rear pointers
Fix: Use modulo or conditional checks to wrap pointers to start/end of array

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

Summary

It removes elements from either the front or rear end of a dequeue.

Use it when you want to efficiently remove items from both ends of a collection.

Remember to update pointers circularly and reset when dequeue becomes empty.