Building a Double-Ended Queue (Deque) in Java for Sliding Window Algorithms

Suppose you are building a real-time crypto trading bot.

Your bot analyzes a stream of stock price ticks arriving every millisecond. For every incoming tick, it must report the maximum price seen over the last 60 seconds (a sliding window of 60,000 data points).

If you scan all 60,000 prices every millisecond, your system executes $60,000 \times 1,000 = 60,000,000$ comparisons per second. The bot falls behind real-time market data.

To compute running maximums in $O(1)$ constant time per incoming tick, algorithms use a Double-Ended Queue (Deque).

---

Why You Need This in Real Life

A Deque provides symmetric $O(1)$ insertions and removals at both ends:

• Sliding Window Analytics: Tracking running maximums, minimums, or moving averages across streaming sensor or market data.
• Work-Stealing Scheduler Queues: Multi-core executors (like Java’s ForkJoinPool) push and pop tasks from their own thread queue tail, while idle worker threads “steal” tasks from the head.
• Browser Navigation History: Moving forward and backward through web pages.

---

The Deque API Contract

A Deque exposes operations at both ends:

       +-------------------------------------------------------+
       |                  MyArrayDeque Buffer                  |
       |                                                       |
  pushFirst() ---> [ HEAD ] <---> [ BODY ] <---> [ TAIL ] <--- pushLast()
  popFirst()  <---                                        <--- popLast()
       +-------------------------------------------------------+

Action	Head Operation	Tail Operation
Insert	addFirst(e) / offerFirst(e)	addLast(e) / offerLast(e)
Remove	removeFirst() / pollFirst()	removeLast() / pollLast()
Examine	getFirst() / peekFirst()	getLast() / peekLast()

---

Circular Head Decrement Math

In a standard Queue, head only moves forward (head = (head + 1) % capacity).

In a Deque, addFirst() moves head backward in memory. Decrementing index 0 must wrap around to capacity - 1:

$\text{head} = (\text{head} - 1 + \text{capacity}) \pmod{\text{capacity}}$

---

Complete MyArrayDeque<T> Implementation

import java.util.NoSuchElementException;

public class MyArrayDeque<T> {
    private Object[] elements;
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public MyArrayDeque() {
        this.elements = new Object[16];
    }

    public void addFirst(T item) {
        if (item == null) throw new NullPointerException();
        head = (head - 1 + elements.length) % elements.length;
        elements[head] = item;
        size++;
        if (head == tail && size > 1) {
            doubleCapacity();
        }
    }

    public void addLast(T item) {
        if (item == null) throw new NullPointerException();
        elements[tail] = item;
        tail = (tail + 1) % elements.length;
        size++;
        if (head == tail) {
            doubleCapacity();
        }
    }

    @SuppressWarnings("unchecked")
    public T pollFirst() {
        if (size == 0) return null;
        T result = (T) elements[head];
        elements[head] = null;
        head = (head + 1) % elements.length;
        size--;
        return result;
    }

    @SuppressWarnings("unchecked")
    public T pollLast() {
        if (size == 0) return null;
        tail = (tail - 1 + elements.length) % elements.length;
        T result = (T) elements[tail];
        elements[tail] = null;
        size--;
        return result;
    }

    @SuppressWarnings("unchecked")
    public T peekFirst() {
        return size == 0 ? null : (T) elements[head];
    }

    @SuppressWarnings("unchecked")
    public T peekLast() {
        if (size == 0) return null;
        int target = (tail - 1 + elements.length) % elements.length;
        return (T) elements[target];
    }

    public int size() {
        return size;
    }

    private void doubleCapacity() {
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new IllegalStateException("Deque buffer overflow");
        }
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }
}

---

Real-World Application: Sliding Window Maximum

Deques track running maximums across a sliding array window in $O(N)$ total time.

Given an array [1, 3, -1, -3, 5, 3, 6, 7] and window size $k = 3$, a monotonically decreasing deque stores array indices.

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums.length == 0 || k <= 0) return new int[0];
    int[] result = new int[nums.length - k + 1];
    MyArrayDeque<Integer> deque = new MyArrayDeque<>();

    for (int i = 0; i < nums.length; i++) {
        // 1. Remove indices out of current window bounds from head
        if (deque.size() > 0 && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 2. Remove smaller elements from tail
        while (deque.size() > 0 && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.addLast(i);

        // 3. Record window max from head
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

---

Quick Summary

• Deques provide double-ended push/pop/peek operations in constant $O(1)$ time.
• Circular ring buffers require wrapping index math on both head decrements and tail increments.
• ArrayDeque consumes significantly less memory than LinkedList because it avoids per-element node pointer objects.

References & Further Reading

1. OpenJDK Repository. OpenJDK 21 Source Code: java.util.LinkedHashMap. GitHub.
2. Bloch, J. (2018). Effective Java (3rd Edition) — Item 66: Access to Shared Data. Addison-Wesley.
3. Oracle Corporation. Java SE 21 API Documentation: LinkedHashMap#removeEldestEntry. Oracle Docs.

---