Deque in Java — Sliding Window O(n) and Monotonic Patterns

Every program that manages ordered data eventually hits an awkward wall: a plain Queue is too rigid (insert at back, remove from front — period), and a Stack is the opposite extreme (everything through one end only). But real problems rarely fit neatly into either box. Your browser's back-and-forward history needs insertions and removals at both ends. A sliding-window algorithm needs to add to the back while evicting old entries from the front. A task scheduler needs to push urgent work to the front without rebuilding the entire structure. That's the gap the Deque was born to fill.

A Deque — pronounced 'deck,' short for Double-Ended Queue — is a linear data structure that lets you add and remove elements from both its front and its back in O(1) time. It's not a hack on top of a Queue; it's a first-class citizen in every serious language's standard library. Java has ArrayDeque. Python has collections.deque. C++ has std::deque. The reason they all ship one is that too many critical algorithms need this exact shape.

By the end of this article you'll understand precisely why a Deque exists, when to reach for it over a Stack or Queue, how to implement core operations from scratch, and how to use Java's ArrayDeque to solve a real sliding-window problem that shows up constantly in technical interviews. No hand-waving, no abstract diagrams divorced from code — just concrete understanding you can use tomorrow.

Deque: The Double-Ended Queue That Unlocks O(n) Sliding Window Algorithms

A deque (double-ended queue) is a linear data structure that supports insertion and deletion at both ends in O(1) amortized time. Unlike a regular queue (FIFO) or stack (LIFO), a deque combines both capabilities: you can push/pop from the front or back. In Java, the Deque interface is implemented by ArrayDeque and LinkedList, with ArrayDeque being the faster, non-thread-safe choice for most use cases.

The core mechanic is simple: elements are stored in a circular buffer (ArrayDeque) or doubly linked list (LinkedList). This gives you constant-time access to both ends. The real power emerges when you combine deque operations with a monotonic ordering constraint — for example, maintaining elements in decreasing order while sliding a window. This pattern lets you discard irrelevant elements (those that can never be the maximum in a future window) in O(1) per element, reducing a naive O(n*k) sliding window problem to O(n).

Use a deque when you need to efficiently track a subset of elements that are "candidates" for some property (like max/min) as a window moves over a sequence. Real systems use this for real-time analytics (rolling statistics), network packet buffering (where old packets expire), and UI event streams (debouncing recent clicks). The key insight: a deque is not just a double-ended queue — it's a data structure for maintaining a sliding view of relevant elements with O(1) eviction of stale or dominated entries.

How a Deque Works — Plain English and Patterns

A deque (double-ended queue) supports O(1) insertions and deletions from both ends. It is more general than both a stack (one end) and a queue (FIFO). Python's collections.deque implements this efficiently.

Core operations (all O(1)): 1. append(x): add to right end. 2. appendleft(x): add to left end. 3. pop(): remove from right end. 4. popleft(): remove from left end.

Key pattern — sliding window maximum (monotonic deque): Maintain a deque of indices in decreasing order of value. For each new element: 1. Remove indices from the back that have values <= current (they can never be max). 2. Remove indices from the front that are outside the current window. 3. Append current index to back. 4. Front of deque = index of maximum in current window.

Worked example — sliding max, window k=3, arr=[1,3,-1,-3,5,3,6,7]: i=0(1): deque=[0]. i=1(3): 3>arr[0]=1 → pop 0. deque=[1]. i=2(-1): -1<3. deque=[1,2]. Window full. max=arr[1]=3. i=3(-3): -3<-1. deque=[1,2,3]. Front 1 still in window [1,3]. max=arr[1]=3. i=4(5): pop 3(-3),2(-1),1(3). deque=[4]. max=arr[4]=5. i=5(3): 3<5. deque=[4,5]. max=arr[4]=5. i=6(6): pop 5(3),4(5). deque=[6]. max=arr[6]=6. i=7(7): pop 6(6). deque=[7]. max=arr[7]=7. Sliding maxima: [3,3,5,5,6,7].

How a Deque Works Internally — The Four Core Operations

A Deque supports exactly four directional operations: addFirst, addLast, removeFirst, and removeLast. Everything else (peekFirst, peekLast, size, isEmpty) is just a convenience wrapper on top of these four. Understanding that simplicity is important — a Deque is not complicated, it's just unrestricted.

Under the hood, most implementations use either a doubly-linked list or a circular resizable array. Java's ArrayDeque uses the circular array approach, which gives better cache locality than a linked list because elements are stored contiguously in memory. When the array fills up, it doubles in capacity — the same growth strategy as ArrayList.

The doubly-linked list approach (like LinkedList in Java, which also implements Deque) has O(1) worst-case for all four operations but pays a memory overhead for the prev and next pointers on every node, plus it thrashes the CPU cache because nodes are scattered in the heap.

For 99% of use cases, ArrayDeque is the right pick. The Java docs themselves say: 'This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.' That's a direct endorsement from the authors. Use ArrayDeque unless you specifically need null elements (ArrayDeque forbids them) or guaranteed O(1) worst-case at the cost of memory.

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeCoreBehavior {

    public static void main(String[] args) {

        // ArrayDeque is the go-to Deque implementation in Java.
        // It's backed by a resizable circular array — fast and cache-friendly.
        Deque<String> taskQueue = new ArrayDeque<>();

        // --- addLast: normal enqueue, like a regular queue ---
        taskQueue.addLast("render-homepage");   // rear -> [render-homepage]
        taskQueue.addLast("send-email");         // rear -> [render-homepage, send-email]
        taskQueue.addLast("resize-image");       // rear -> [render-homepage, send-email, resize-image]

        System.out.println("Initial task queue: " + taskQueue);
        // Output: [render-homepage, send-email, resize-image]

        // --- addFirst: urgent task jumps to the FRONT ---
        // This is the operation no plain Queue can do without rebuilding itself.
        taskQueue.addFirst("URGENT-payment-gateway");
        System.out.println("After urgent task injected at front: " + taskQueue);
        // Output: [URGENT-payment-gateway, render-homepage, send-email, resize-image]

        // --- peekFirst / peekLast: look without removing ---
        System.out.println("Next task to process: " + taskQueue.peekFirst());  // URGENT-payment-gateway
        System.out.println("Last task in line:    " + taskQueue.peekLast());   // resize-image

        // --- removeFirst: process tasks from the front ---
        String processed = taskQueue.removeFirst();
        System.out.println("Processed: " + processed);
        System.out.println("Remaining tasks: " + taskQueue);
        // Output: [render-homepage, send-email, resize-image]

        // --- removeLast: cancel the last-added task (like an undo) ---
        String cancelled = taskQueue.removeLast();
        System.out.println("Cancelled (last task removed): " + cancelled);
        System.out.println("Final queue: " + taskQueue);
        // Output: [render-homepage, send-email]
    }
}

Deque as a Stack AND a Queue — One Structure, Two Personalities

Here's the insight that makes a Deque so valuable: it's a strict superset of both Stack and Queue. You can use it as a pure stack by only calling addFirst and removeFirst. You can use it as a pure queue by calling addLast and removeFirst. Or you can mix both modes in the same algorithm.

Java's old Stack class extends Vector, which is synchronized (thread-locking every call even in single-threaded code) and carries decades of legacy baggage. The official Java recommendation since Java 6 has been: use a Deque instead of Stack. Specifically, ArrayDeque when you don't need thread safety.

This matters beyond style. When you push and pop using a Deque-as-stack, you're getting a leaner, faster structure with no synchronization overhead and no broken inheritance chain (Stack inheriting from Vector means you can call .get(3) on a 'stack,' which violates the entire abstraction).

A Queue interface in Java also doesn't give you addFirst. So when you're building a BFS that needs to occasionally push a node back to the front of the queue (priority re-insertion), a plain Queue forces you to use a PriorityQueue or rebuild the collection. A Deque handles it in one method call.

Think of Deque as the Swiss Army knife that ships with your runtime — it costs you nothing extra to use the more capable tool.

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsStackAndQueue {

    // ── Using Deque as a STACK (LIFO) ────────────────────────────────────────
    // Real use case: parsing nested brackets in a code editor
    static boolean isBracketsBalanced(String sourceCode) {
        Deque<Character> bracketStack = new ArrayDeque<>();

        for (char ch : sourceCode.toCharArray()) {
            // Opening bracket: push onto the top of our stack
            if (ch == '(' || ch == '{' || ch == '[') {
                bracketStack.addFirst(ch);  // addFirst = push
            }
            // Closing bracket: check if it matches the last opened bracket
            else if (ch == ')' || ch == '}' || ch == ']') {
                if (bracketStack.isEmpty()) {
                    return false; // Closed something that was never opened
                }
                char lastOpened = bracketStack.removeFirst(); // removeFirst = pop
                if (!isMatchingPair(lastOpened, ch)) {
                    return false; // Mismatch: { closed by ) for example
                }
            }
        }
        // If stack is empty, every opened bracket was closed correctly
        return bracketStack.isEmpty();
    }

    static boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')')
            || (open == '{' && close == '}')
            || (open == '[' && close == ']');
    }

    // ── Using Deque as a QUEUE (FIFO) ────────────────────────────────────────
    // Real use case: print job spooler — jobs processed in arrival order,
    // but a SYSTEM job can jump to the front.
    static void simulatePrintSpooler() {
        Deque<String> printQueue = new ArrayDeque<>();

        // Normal jobs arrive at the back
        printQueue.addLast("user-invoice.pdf");     // addLast = enqueue
        printQueue.addLast("user-report.pdf");
        printQueue.addLast("user-photo.png");

        // System diagnostic needs to print NOW — inject at the front
        printQueue.addFirst("SYSTEM-diagnostic.pdf");

        System.out.println("Print spooler order:");
        while (!printQueue.isEmpty()) {
            System.out.println("  Printing: " + printQueue.removeFirst()); // removeFirst = dequeue
        }
    }

    public static void main(String[] args) {
        // ── Stack mode: bracket validation ──
        System.out.println("Bracket check '{[()]}':   " + isBracketsBalanced("{[()]}"));  // true
        System.out.println("Bracket check '({[})':    " + isBracketsBalanced("({[})"));    // false
        System.out.println("Bracket check '((()))':   " + isBracketsBalanced("((()))"));  // true
        System.out.println();

        // ── Queue mode: print spooler ──
        simulatePrintSpooler();
    }
}

Real-World Algorithm: Sliding Window Maximum Using a Deque

The sliding window maximum problem is THE canonical Deque interview question, and it perfectly illustrates why no other structure can do this elegantly.

The problem: given an array of numbers and a window of size k, find the maximum value in each window as it slides from left to right. Brute force is O(n*k) — for each window position, scan all k elements. With a Deque, you can do it in O(n).

The trick is to use the Deque as a monotonic decreasing queue of indices. You maintain the invariant that the front of the Deque always holds the index of the largest element in the current window. When you slide the window: 1. Remove from the back any elements smaller than the incoming element (they can never be the max while the new element exists in the window). 2. Remove from the front any index that's fallen outside the window boundary. 3. The front is always your current window maximum.

This is not intuitive at first. But notice what makes a Deque mandatory here: you need to remove stale indices from the FRONT (out-of-window), and you need to remove useless candidates from the BACK (smaller values). No other single structure gives you O(1) on both ends. A heap would give O(log k) per operation. A queue gives you nothing for the back. A stack gives you nothing for the front.

This pattern generalises to sliding window minimum, next greater element, and monotonic stack problems with a window constraint.

package io.thecodeforge.deque;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class SlidingWindowMaximum {

    /**
     * Finds the maximum value in every sliding window of size windowSize.
     *
     * The Deque stores INDICES (not values) of candidate maximum elements.
     * Invariant: elements in the Deque are always in decreasing order of their
     * corresponding values in the input array.
     *
     * @param temperatures  The input array (e.g., daily temperature readings)
     * @param windowSize    Number of days in each sliding window
     * @return              Array of maximum temperatures per window
     */
    static int[] slidingWindowMax(int[] temperatures, int windowSize) {
        if (temperatures == null || temperatures.length == 0 || windowSize <= 0) {
            return new int[0];
        }

        int totalDays = temperatures.length;
        int[] windowMaxima = new int[totalDays - windowSize + 1]; // one max per window
        int resultIndex = 0;

        // The Deque holds indices into the temperatures array.
        // Front = index of current window's maximum.
        // Back  = index of the smallest 'candidate' we haven't discarded yet.
        Deque<Integer> candidateIndices = new ArrayDeque<>();

        for (int currentDay = 0; currentDay < totalDays; currentDay++) {

            // STEP 1: Evict from the BACK — remove any past candidates whose
            // temperature is <= today's. They can NEVER be a future window max
            // while today's value is still inside the window.
            while (!candidateIndices.isEmpty()
                    && temperatures[candidateIndices.peekLast()] <= temperatures[currentDay]) {
                candidateIndices.removeLast(); // this candidate is useless now
            }

            // STEP 2: Add today's index as the newest candidate at the BACK
            candidateIndices.addLast(currentDay);

            // STEP 3: Evict from the FRONT — if the front index is outside
            // the current window's left boundary, it's no longer valid.
            int windowLeftBoundary = currentDay - windowSize + 1;
            if (candidateIndices.peekFirst() < windowLeftBoundary) {
                candidateIndices.removeFirst(); // slid out of the window
            }

            // STEP 4: Once we've filled the first window, record the max.
            // The front of the Deque is always the index of the window's max.
            if (currentDay >= windowSize - 1) {
                windowMaxima[resultIndex++] = temperatures[candidateIndices.peekFirst()];
            }
        }

        return windowMaxima;
    }

    public static void main(String[] args) {
        // Scenario: 10 days of temperature readings, window = 3 days
        int[] dailyTemperatures = {31, 27, 34, 22, 19, 35, 28, 30, 24, 33};
        int windowSize = 3;

        System.out.println("Daily temperatures: " + Arrays.toString(dailyTemperatures));
        System.out.println("Window size: " + windowSize + " days\n");

        int[] maxPerWindow = slidingWindowMax(dailyTemperatures, windowSize);

        System.out.println("Max temperature in each 3-day window:");
        for (int i = 0; i < maxPerWindow.length; i++) {
            int windowStart = i;
            int windowEnd   = i + windowSize - 1;
            System.out.printf("  Days %d-%d %s  →  Max: %d°C%n",
                windowStart + 1,
                windowEnd   + 1,
                Arrays.toString(Arrays.copyOfRange(dailyTemperatures, windowStart, windowEnd + 1)),
                maxPerWindow[i]);
        }

        // Edge case: window size = 1 (each element is its own max)
        System.out.println();
        int[] singleDayWindow = slidingWindowMax(dailyTemperatures, 1);
        System.out.println("Window size 1 (sanity check): " + Arrays.toString(singleDayWindow));

        // Edge case: window = full array (single max of entire array)
        int[] fullWindow = slidingWindowMax(dailyTemperatures, dailyTemperatures.length);
        System.out.println("Window = full array:           " + Arrays.toString(fullWindow));
    }
}

Deque Performance: Memory, Cache Locality & Choosing the Right Implementation

Not all Deques are created equal. The implementation you choose has a direct impact on throughput, memory footprint, and GC pressure. Here's what actually matters in production.

ArrayDeque's circular array gives sequential memory access patterns. When you iterate or poll from the front, the CPU prefetcher pulls in adjacent cache lines. That means ArrayDeque can process elements at L1 cache speed (~1ns per element) when the deque fits in cache. LinkedList, by contrast, scatters nodes across the heap — every removeFirst() is a cache miss, and every node traversal chases a pointer through memory.

But ArrayDeque has a hidden cost: resizing. When the internal array fills up, it doubles and copies all elements. For a deque that grows to 1 million elements, that's a 4MB copy operation that stalls your thread. If you're running latency-sensitive code (sub-millisecond SLAs), that copy can blow your budget.

LinkedList avoids the resize stall entirely — every addFirst/addLast is just a pointer swap. But you pay for it with memory: each element in LinkedList requires a Node object with two references (prev, next) plus the element itself. That's roughly 24 bytes of overhead per element on a 64-bit JVM with compressed OOPs. For a deque holding 10 million elements, that's 240MB of overhead that ArrayDeque doesn't need.

The decision rule: use ArrayDeque by default. Switch to LinkedList only when you need null elements or when the resize cost is unacceptable for your latency budget. And if you're really in a tight spot, build your own ring buffer with a fixed-size int[] array — no boxing, no resizing, no GC pressure.

Input-Restricted vs Output-Restricted: Why You Should Care About the Variants

Most tutorials treat deque as one unified thing. That's fine for leetcode. In production, the hardware interface you're coding to might only support insertion on one end. That's where the variants live.

Input-Restricted Deque: Insertions only at the rear. Deletions from both ends. Sounds dumb until you're writing a scheduler that processes priority requests arriving on a single channel but allows cancellation from either end. The input restriction maps to a physical constraint — one DMA channel for writes.

Output-Restricted Deque: Deletions only from the front. Insertions at both ends. You see this in buffer pools where consumers pull from one side but producers can push high-priority data to the front and normal data to the back. Think network packet processing: urgent control frames jump the queue, bulk data goes to the tail.

Both variants trade flexibility for simpler locking and better cache behavior. If you only need access on one side of the queue, don't pay for the other side's overhead.

// io.thecodeforge — dsa tutorial

import java.util.ArrayDeque;
// Input-restricted: only addLast, but removeFirst or removeLast
public class InputRestrictedDequeDemo {
    public static void main(String[] args) {
        var deque = new ArrayDeque<Integer>();
        deque.addLast(1);
        deque.addLast(2);
        deque.addLast(3);

        System.out.println("Deque: " + deque);
        // Output-restricted logic: remove from both ends
        int frontRemoved = deque.removeFirst();
        int rearRemoved  = deque.removeLast();
        System.out.println("Front: " + frontRemoved + ", Rear: " + rearRemoved);
        System.out.println("After removal: " + deque);
    }
}

Easy Problems That Will Expose Your Deque Blind Spots

Competitor pages just dump a problem list. I'll tell you which ones actually teach you something. The 'easy' label is a lie — these problems punish you like a senior code review.

Level Order Traversal in Spiral Form: You're given a binary tree. Print it zigzag. Most people use two stacks. The deque solution is cleaner: push root, then alternate between addFirst and addLast depending on direction. If you can't do that in 10 lines, you don't understand double-ended movement.

String After Processing Backspace Characters: Typed 'ab#c' becomes 'ac'. Obvious stack solution, but the twist: you can also traverse from right to left with a deque. Skip characters after a backspace. It's a trick interviewers use to see if you can reverse the problem — worth knowing.

Lexicographically Largest Permutation: Given a string, modify it by moving characters to front or back to get the lexicographically largest result. This is a deque problem in disguise. If you don't see that, you're treating it as a sorting problem, which is wrong and O(n log n) instead of O(n).

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SpiralOrderZigzag {
    public static void zigzagLevelOrder(TreeNode root) {
        if (root == null) return;
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.addLast(root);
        boolean leftToRight = true;
        while (!dq.isEmpty()) {
            int size = dq.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = leftToRight ? dq.removeFirst() : dq.removeLast();
                System.out.print(node.val + " ");
                if (leftToRight) {
                    if (node.left != null) dq.addLast(node.left);
                    if (node.right != null) dq.addLast(node.right);
                } else {
                    if (node.right != null) dq.addFirst(node.right);
                    if (node.left != null) dq.addFirst(node.left);
                }
            }
            leftToRight = !leftToRight;
            System.out.println();
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2); root.right = new TreeNode(3);
        root.left.left = new TreeNode(4); root.right.right = new TreeNode(5);
        zigzagLevelOrder(root);
    }
    static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }
}

Deque Implementations: Circular Array vs Doubly Linked List — The Real Tradeoffs

Competitors show you both implementations as if they're equivalent. They're not. One will get you fired if you pick wrong.

Circular Array: You get O(1) amortized access to any index. Cache-friendly because elements are contiguous in memory. But when it resizes, it copies the whole array — O(n) time, and if you're on a latency-sensitive path, that copy will wake up your ops team. Java's ArrayDeque uses this. It's your default.

Doubly Linked List: Every insertion and deletion is O(1) actual, no resize. But each node is a separate allocation — heap fragmentation, pointer chasing, cache misses on traversal. You pay 16 bytes per node for the two pointers alone (on 64-bit JVM). The only reason to use this is if you need persistent references to nodes (like a LRU cache where you remove from middle) or if you can't tolerate any resize pauses.

If you're doing sliding window problems — use ArrayDeque. If you're building a concurrent queue where resizing would cause contention — use a linked-list based ConcurrentLinkedDeque. Know your workload.

Java's ArrayDeque vs LinkedList: ArrayDeque is almost always faster. It's not even close. Respect the data.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class ArrayDequeVsLinkedList {
    public static void main(String[] args) {
        int size = 1000000;
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        Deque<Integer> linkedDeque = new LinkedList<>();

        // Add
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) arrayDeque.addLast(i);
        long arrayTime = System.nanoTime() - start;

        start = System.nanoTime();
        for (int i = 0; i < size; i++) linkedDeque.addLast(i);
        long linkedTime = System.nanoTime() - start;

        System.out.println("ArrayDeque add: " + arrayTime / 1e6 + " ms");
        System.out.println("LinkedList add: " + linkedTime / 1e6 + " ms");
        System.out.println("Ratio: LinkedList is " + (linkedTime / (double) arrayTime) + "x slower");
    }
}

Deque in Production: Why Your Codebase Already Has One (And You're Ignoring It)

Every senior dev has seen this: someone imports a Stack or a LinkedList for a FIFO queue. Wrong tool. The JDK ships with ArrayDeque — a circular-array deque that beats both hands down. No synchronization overhead like Vector-based Stack. No node allocation like LinkedList. Just a contiguous chunk of memory with head and tail pointers spinning around it.

ArrayDeque does everything. Push front, push back, pop either end, peek without removing. That's your stack and your queue in one class. The Java Collections Framework literally recommends it over Stack. But most devs never open the Javadoc. They default to what they learned in CS 101.

Here's the production reality: LinkedList is for when you need mid-list insertion or guaranteed O(1) removal at an iterator position. ArrayDeque is for everything else — sliding windows, work-stealing queues, undo stacks. If you're using LinkedList for a simple queue in 2024, your code is leaving performance on the table. End of story.

// io.thecodeforge — dsa tutorial

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeInProduction {
    public static void main(String[] args) {
        Deque<String> taskQueue = new ArrayDeque<>();
        
        // Work-stealing pattern: producers push back, workers pop front
        taskQueue.addLast("task-1");
        taskQueue.addLast("task-2");
        taskQueue.addFirst("urgent-0");  // high-priority gets front
        
        System.out.println("Next: " + taskQueue.removeFirst());
        System.out.println("Size: " + taskQueue.size());
    }
}

Deque in C++: What std::deque Actually Does to Your Memory

C++ devs love std::deque. They should. It's the only standard container that grows from both ends without invalidating pointers to existing elements — unlike vector's reallocation. But here's what the tutorials won't tell you: std::deque isn't a single contiguous array. It's a sequence of fixed-size chunks (blocks) managed by a central map. Each chunk is a slab of memory. Push front? If the current front chunk is full, it allocates a new chunk and updates the map.

This means random access is O(1) amortized, but it's slower than vector because there's an extra layer of indirection through the chunk map. Iterator invalidation rules are weird: inserting at the middle invalidates everything. Deque shrinks? It won't release memory back to the OS, even after clear(). The chunks stay allocated for reuse.

Use std::deque when you need fast push/pop at both ends and occasional random access. Use std::vector for tight loops iterating over everything. Use std::list only when you need stable iterators after insertions. Know your allocator. Know your access patterns. The standard library gives you tools, not excuses.

// io.thecodeforge — dsa tutorial

// C++ std::deque example in Java to match language requirement
// Concept: std::deque<int> dq = {1,2,3};
import java.util.ArrayDeque;

public class CppDeque {
    public static void main(String[] args) {
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        dq.addLast(1);
        dq.addLast(2);
        dq.addLast(3);
        dq.addFirst(0);  // equivalent to push_front
        
        System.out.println("Front: " + dq.getFirst());
        System.out.println("Back: " + dq.getLast());
    }
}

Basics of Deque

A deque, short for double-ended queue, is a linear data structure that allows insertion and deletion of elements from both ends—front and rear. Think of it as a more flexible queue: you can add to the back and remove from the front (like a regular queue), or add to the front and remove from the back (like a stack). But what makes deques powerful is that you can do all four operations efficiently in O(1) average time. Why use a deque instead of a stack or queue alone? Real-world scenarios often need both behaviors at once—for example, processing a browser's history where you go back (pop from front) and forward (pop from back). The key takeaway: deques unify stack and queue operations into one structure, simplifying code when you need two-way access. They also serve as building blocks for algorithms like sliding window maximum, palindrome checking, and undo/redo systems. Understanding deque basics is the first step to writing cleaner, more efficient code.

// io.thecodeforge — dsa tutorial
import java.util.*;

public class DequeBasics {
    public static void main(String[] args) {
        Deque<Integer> dq = new ArrayDeque<>();
        
        // Add from both ends
        dq.addLast(10);
        dq.addFirst(20);
        dq.addLast(30);
        
        // Remove from both ends
        int first = dq.removeFirst(); // 20
        int last = dq.removeLast();   // 30
        
        System.out.println("Remaining: " + dq); // [10]
        System.out.println("Peek first: " + dq.peekFirst()); // 10
    }
}

Deque in Different Languages

Deque implementations vary across languages, but the core concept remains: efficient insertion and deletion at both ends. In Java, the Deque interface (java.util.Deque) is implemented by ArrayDeque (fast, array-backed) and LinkedList (node-based). ArrayDeque is the go-to for single-threaded use because of cache-friendly memory and no nulls. In Python, collections.deque is the standard—implemented as a doubly linked list of fixed-size blocks, offering O(1) operations and thread-safe appends/pops. C++'s std::deque is a sequence container with a more complex block-based design, giving fast random access but sometimes slower iterators. JavaScript lacks a native deque; use an array with shift()/unshift() (O(n)) or implement a custom linked list for O(1). Why learn these differences? Because picking the wrong language-specific deque can tank performance: Python's deque is ideal for queues, C++'s for balanced access, and Java's ArrayDeque for speed. Always check your language's standard library before rolling your own.

// io.thecodeforge — dsa tutorial
import java.util.*;

public class DequeLanguages {
    public static void main(String[] args) {
        // Java — ArrayDeque (preferred)
        Deque<String> javaDq = new ArrayDeque<>();
        javaDq.addFirst("front");
        javaDq.addLast("back");
        System.out.println("Java deque: " + javaDq);
        
        // Python equivalent (conceptually)
        // from collections import deque
        // py_dq = deque(['front', 'back'])
        // py_dq.append('new_back')
        // py_dq.appendleft('new_front')
        
        // C++ equivalent (conceptually)
        // std::deque<int> cpp_dq = {1, 2, 3};
        // cpp_dq.push_front(0);
        // cpp_dq.push_back(4);
    }
}