Deque in C: solved exercise

If you searched for a solved deque in C, here is the circular-array implementation that supports O(1) insertion and removal at both ends. A deque (double-ended queue) generalizes both the stack and the queue: it can be used as either.

With a circular array, the front and rear indices advance modulo CAPACITY, avoiding element shifting.

Problem statement

Implement a fixed-capacity deque of 8 elements supporting:

push_front(d, v): insert at the front.
push_back(d, v): insert at the back.
pop_front(d): remove and return the front element.
pop_back(d): remove and return the back element.
print(d): display contents from front to back.

Demonstrate all four operations with a sequence of insertions and removals.

C solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>

#define CAP 8

typedef struct {
    int data[CAP];
    int front;   /* index of the first element */
    int size;
} Deque;

static int is_full(const Deque *d)  { return d->size == CAP; }
static int is_empty(const Deque *d) { return d->size == 0; }

void push_back(Deque *d, int val) {
    if (is_full(d)) { fprintf(stderr, "Deque full\n"); return; }
    int pos = (d->front + d->size) % CAP;
    d->data[pos] = val;
    d->size++;
}

void push_front(Deque *d, int val) {
    if (is_full(d)) { fprintf(stderr, "Deque full\n"); return; }
    d->front = (d->front - 1 + CAP) % CAP;
    d->data[d->front] = val;
    d->size++;
}

int pop_front(Deque *d) {
    if (is_empty(d)) { fprintf(stderr, "Deque empty\n"); return -1; }
    int val = d->data[d->front];
    d->front = (d->front + 1) % CAP;
    d->size--;
    return val;
}

int pop_back(Deque *d) {
    if (is_empty(d)) { fprintf(stderr, "Deque empty\n"); return -1; }
    int pos = (d->front + d->size - 1) % CAP;
    d->size--;
    return d->data[pos];
}

void print_deque(const Deque *d) {
    printf("Deque [%d]: ", d->size);
    for (int i = 0; i < d->size; i++)
        printf("%d ", d->data[(d->front + i) % CAP]);
    printf("\n");
}

int main(void) {
    Deque d = {.front = 0, .size = 0};

    push_back(&d,  10); print_deque(&d);
    push_back(&d,  20); print_deque(&d);
    push_front(&d,  5); print_deque(&d);
    push_back(&d,  30); print_deque(&d);
    push_front(&d,  1); print_deque(&d);

    printf("\npop_front() = %d\n", pop_front(&d)); print_deque(&d);
    printf("pop_back()  = %d\n", pop_back(&d));   print_deque(&d);
    printf("pop_front() = %d\n", pop_front(&d));  print_deque(&d);

    return 0;
}

Expected output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Deque [1]: 10 
Deque [2]: 10 20 
Deque [3]: 5 10 20 
Deque [4]: 5 10 20 30 
Deque [5]: 1 5 10 20 30 

pop_front() = 1
Deque [4]: 5 10 20 30 
pop_back()  = 30
Deque [3]: 5 10 20 
pop_front() = 5
Deque [2]: 10 20 

Common mistakes

Not applying the CAP modulo when computing front - 1: in C, the % operator with negative numbers can give a negative result; use (front - 1 + CAP) % CAP.
Confusing the back index with front + size: the back is at (front + size - 1) % CAP, since front + size points to the first empty slot.
Not checking if the deque is full before push_front or push_back: inserting when size == CAP overwrites existing elements.
Initializing front to a non-zero value: for simplicity, front = 0 and size = 0 is the standard initialization.

Practical use

The deque is used in sliding window algorithms (maximum/minimum in a window of size k), task scheduling (insertion and removal at both ends), as the underlying structure of bidirectional BFS, and in simulators of priority queues at both ends.

Recommended next exercise

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

What is the difference between a deque and a regular queue?

A queue (FIFO) only allows insertion at the back and removal at the front. A deque allows insertion and removal at both ends. The deque is a superset: it can simulate both a queue (using only push_back and pop_front) and a stack (using only push_back and pop_back).

Why use a circular array instead of a linked list?

A circular array guarantees O(1) for all operations without dynamic memory allocation, making it faster and with better cache locality than a linked list. A linked list is preferable when the capacity is unknown or unlimited.

What is the time complexity of the four deque operations?

All four operations (push_front, push_back, pop_front, pop_back) are O(1) with the circular array. The print operation is O(n) as it traverses all elements.