Deque (Double-Ended Queue)

A deque lets you insert and remove at both front and rear. It generalizes both stack (one end) and queue (two ends, FIFO). A fixed-size implementation often uses a circular buffer like a circular queue, but with two movable ends.

On this page

Representation — array + front index + size (or front/rear)
Operations — push/pop at front and back
Restricted variants — input- vs output-restricted deque
Example in C — circular-array deque

1) Representation

Typical fields (circular array deque)
Field	Purpose	Notes
`buf[]`	Stores elements	Capacity `MAX`
`front`	Index of first element	Advance with `(front + 1) % MAX` on pop front
`size`	Count of elements	Empty: `0`; full: `MAX`

Rear is not always stored: logical rear = (front + size - 1) % MAX when size > 0.

2) Operations and restricted types

Deque API (double-ended)
Operation	Meaning	Typical time (array)
`push_front`	Insert at front	O(1)
`push_back`	Insert at rear	O(1)
`pop_front`	Remove from front	O(1)
`pop_back`	Remove from rear	O(1)

Restricted deque variants (names vary by textbook)
Variant	Restriction	Behaves like
Input-restricted	Insert at only one end	Queue or stack depending on which end
Output-restricted	Delete at only one end	Often still useful for scheduling

3) Example in C

#include <stdio.h>

#define MAX 8

static int buf[MAX];
static int front = 0;
static int size = 0;

static int is_empty(void) { return size == 0; }
static int is_full(void)  { return size == MAX; }

static int push_back(int v) {
    if (is_full()) return 0;
    int rear = (front + size) % MAX;
    buf[rear] = v;
    size++;
    return 1;
}

static int push_front(int v) {
    if (is_full()) return 0;
    front = (front - 1 + MAX) % MAX;
    buf[front] = v;
    size++;
    return 1;
}

static int pop_front(int *out) {
    if (is_empty()) return 0;
    *out = buf[front];
    front = (front + 1) % MAX;
    size--;
    return 1;
}

static int pop_back(int *out) {
    if (is_empty()) return 0;
    int rear = (front + size - 1 + MAX) % MAX;
    *out = buf[rear];
    size--;
    return 1;
}

int main(void) {
    int x;
    push_back(10);
    push_back(20);
    push_front(5);   /* 5, 10, 20 */
    pop_front(&x);   printf("pop_front: %d\n", x);
    pop_back(&x);    printf("pop_back: %d\n", x);
    return 0;
}

Execution summary

Sample trace
Step	Action	Logical order (front → rear)
1	`push_back(10)`, `push_back(20)`	`[10, 20]`
2	`push_front(5)`	`[5, 10, 20]`
3	`pop_front` → 5	`[10, 20]`
4	`pop_back` → 20	`[10]`

Visual (logical sequence)

push_back 10,20:     [10] [20]
push_front 5:        [5] [10] [20]
pop_front:           [10] [20]   (removed 5)
pop_back:            [10]        (removed 20)

4) Trade-offs

Pros — O(1) at both ends with a circular array; versatile (BFS variants, palindrome checks, sliding window).
Cons — Fixed capacity unless you add dynamic resizing; more index cases than a simple queue.

See circular queue for FIFO-only wrap-around, and linked list if you need unbounded growth without resizing.

Key takeaway

Treat front and size (or front/rear) carefully with modulo so push/pop on both ends stay O(1) and never cross.

Next up: Priority queue · Circular queue · All queue topics