CHow-ToBeginner · 4 min read

How to Implement Deque in C: Simple Guide with Example

To implement a deque in C, create a structure with an array and two indices to track front and rear positions. Use functions to add or remove elements from both ends, updating indices circularly to manage the queue efficiently.

📐

Syntax

A deque can be implemented using a struct containing an array, front and rear indices, and the maximum size. Functions include initDeque to initialize, pushFront and pushRear to add elements, and popFront and popRear to remove elements.

The indices wrap around the array using modulo arithmetic to use space efficiently.

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

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

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

int isFull(Deque *dq) {
    return ((dq->rear + 1) % dq->size) == dq->front;
}

void pushFront(Deque *dq, int val);
void pushRear(Deque *dq, int val);
int popFront(Deque *dq);
int popRear(Deque *dq);

💻

Example

This example shows a complete deque implementation with functions to add and remove elements from both ends, and prints the deque contents after operations.

#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->rear + 1) % MAX) == dq->front;
}

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

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

int popFront(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int val = dq->arr[dq->front];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->front = (dq->front + 1) % MAX;
    }
    return val;
}

int popRear(Deque *dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    int val = dq->arr[dq->rear];
    if (dq->front == dq->rear) {
        dq->front = dq->rear = -1;
    } else {
        dq->rear = (dq->rear - 1 + MAX) % MAX;
    }
    return val;
}

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

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

    pushRear(&dq, 10);
    pushRear(&dq, 20);
    pushFront(&dq, 5);
    printDeque(&dq);

    printf("Popped from front: %d\n", popFront(&dq));
    printDeque(&dq);

    pushRear(&dq, 30);
    pushFront(&dq, 2);
    printDeque(&dq);

    printf("Popped from rear: %d\n", popRear(&dq));
    printDeque(&dq);

    return 0;
}

Output

Deque elements: 5 10 20 Popped from front: 5 Deque elements: 10 20 Deque elements: 2 10 20 30 Popped from rear: 30 Deque elements: 2 10 20

⚠️

Common Pitfalls

Not handling the circular wrap-around correctly causes index errors or overwriting data.
Forgetting to check if the deque is full before adding elements leads to overflow.
Incorrectly updating front and rear indices when deque becomes empty can cause invalid states.

Always use modulo arithmetic for index updates and check empty/full conditions before operations.

/* Wrong: Not using modulo causes out-of-bound errors */
// dq->rear = dq->rear + 1; // WRONG

/* Right: Use modulo to wrap around */
// dq->rear = (dq->rear + 1) % MAX; // CORRECT

📊

Quick Reference

isEmpty: front == -1
isFull: (rear + 1) % size == front
pushFront: front = (front - 1 + size) % size
pushRear: rear = (rear + 1) % size
popFront: front = (front + 1) % size
popRear: rear = (rear - 1 + size) % size

✅

Key Takeaways

Use a circular array with front and rear indices to implement deque efficiently in C.

Always check for full and empty conditions before adding or removing elements.

Update indices using modulo arithmetic to wrap around the array correctly.

Handle the empty deque state carefully by resetting front and rear to -1.

Test your deque with both front and rear operations to ensure correctness.