Deque

A deque (double-ended queue, pronounced “deck”) is a queue where you can add and remove elements from both ends — the head and the tail. It generalizes both stacks and queues: you can use it as a stack (push and pop from one end), as a queue (push from one end, pop from the other), or as something more flexible.

Operations:

• enqueueHead(item) — add at the front.
• enqueueTail(item) — add at the back.
• dequeueHead() — remove from the front.
• dequeueTail() — remove from the back.
• getHead() / getTail() — peek at either end.

Naturally implemented with a Doubly linked list (each node has both next and prev pointers), or with a circular array.

Implementation with doubly linked list

struct item {
    int value;
    struct item *next;
    struct item *prev;
};
struct item *head = NULL;
struct item *tail = NULL;
 
void enqueueHead(int n) {
    struct item *pnew = malloc(sizeof(struct item));
    pnew->value = n;
    pnew->next  = head;
    pnew->prev  = NULL;
    
    if (head != NULL) {
        head->prev = pnew;
    }
    head = pnew;
    
    if (tail == NULL) {       // empty deque → set tail too
        tail = pnew;
    }
}
 
void enqueueTail(int n) {
    struct item *pnew = malloc(sizeof(struct item));
    pnew->value = n;
    pnew->next  = NULL;
    pnew->prev  = tail;
    
    if (tail != NULL) {
        tail->next = pnew;
    }
    tail = pnew;
    
    if (head == NULL) {       // empty deque → set head too
        head = pnew;
    }
}

The prev pointers are essential — when you dequeueTail, you need to update the new tail’s next to NULL, and to find the new tail you need its predecessor.

bool dequeueHead(int *n) {
    if (head == NULL) return false;
    struct item *temp = head;
    *n = head->value;
    head = head->next;
    if (head != NULL) {
        head->prev = NULL;
    } else {
        tail = NULL;          // deque is now empty
    }
    free(temp);
    return true;
}
 
bool dequeueTail(int *n) {
    if (tail == NULL) return false;
    struct item *temp = tail;
    *n = tail->value;
    tail = tail->prev;
    if (tail != NULL) {
        tail->next = NULL;
    } else {
        head = NULL;
    }
    free(temp);
    return true;
}

All four operations are O(1) thanks to the doubly linked list’s prev pointers.

When deques are useful

• Sliding window algorithms. Maintain a window over a stream by enqueueing at one end and dequeueing from the other when the window slides.
• Work-stealing schedulers. Each thread has its own deque of tasks; it pushes/pops from one end, and other threads “steal” from the other end.
• Palindrome checking. Push characters at both ends; remove and compare from each end.
• Undo/redo. Undo from one end, redo from the other.

Implementation with circular array

A circular array deque uses two pointers (front and back) plus modular arithmetic, similar to a circular queue but with operations at both ends. The complication is that the array doesn’t naturally extend leftward — front - 1 underflows. Modular arithmetic handles this: (front - 1 + capacity) % capacity gives the cell just before front.

Pros of circular array: contiguous memory, cache-friendly.

Cons: fixed capacity (or expensive to resize).

C++ std::deque and Python’s collections.deque are the standard library implementations.