Deque

A deque (double‑ended queue) is a generalization of both stacks and queues:

  • You can push and pop from both the front and the back.
  • It can act as:
    • A queue (FIFO).
    • A stack (LIFO).
    • A sliding window buffer.

Most modern languages provide an efficient deque implementation.

Core Operations

Typical deque API:

  • pushFront(x), pushBack(x) – insert at front or back.
  • popFront(), popBack() – remove from front or back.
  • peekFront(), peekBack() – view front/back without removal.

All of these operations are O(1) amortized in a proper deque implementation (e.g. circular buffer or linked list with head/tail).

Deques in Algorithms

Deques power some key patterns:

  • Sliding window maximum / minimum:
    • Maintain a decreasing (or increasing) deque of candidates.
    • Push new elements at the back; pop from back while they break monotonicity.
    • Pop from front if they slide out of the window.
  • Bidirectional BFS:
    • When you run BFS from both ends, you may use deques to manage the frontier.
  • Implementing stacks/queues:
    • A deque can trivially implement both a stack and a queue API.

Because deques support both ends, they’re more flexible than plain queues or stacks.

Systems and Libraries

In many standard libraries:

  • Java: ArrayDeque<E> is a resizable array‑backed deque.
  • Python: collections.deque provides O(1) appends and pops from both ends.

Queues (Queue) and stacks (Stack) can often be replaced by Deque for better performance and flexibility.

When to Use a Deque

Use a deque when:

  • You need to push/pop at both ends.
  • You are implementing:
    • A sliding window algorithm.
    • A bounded buffer.
    • A structure that switches between stack‑like and queue‑like behavior.

When in doubt, starting with a deque instead of hand‑rolled arrays/lists for both ends usually makes the code safer and clearer.

Example: Sliding Window Maximum with Deque (Java)

Java
int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k == 0) return new int[0];
    int[] res = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>(); // store indices, values decreasing

    for (int i = 0; i < n; i++) {
        // Remove indices out of window
        if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
            dq.pollFirst();
        }
        // Maintain decreasing deque
        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
            dq.pollLast();
        }
        dq.offerLast(i);
        // Window formed
        if (i >= k - 1) {
            res[i - k + 1] = nums[dq.peekFirst()];
        }
    }
    return res;
}

Here the deque compactly maintains candidates for the maximum of the current window.