Deque Data Structure: The Double-Ended Queue, Explained

A stack lets you touch one end. A queue gives you the other. Both are principled, constrained, and will not negotiate.

Then you hit a problem that needs both ends active at the same time. Your stack and queue both shrug.

The deque (pronounced "deck," short for double-ended queue) supports O(1) push and pop at both ends. It is strictly more general than either a stack or a queue. You can simulate both with one. The catch is that you have to know when to reach for it, which most candidates don't until the interview.

This guide covers how deques work, how they are built, where they appear in interviews, and what each language gives you out of the box.

---

Two Ends, Four Operations

A standard queue gives you two operations: add to the back, remove from the front. A deque adds two more:

Operation	What it does	Time
push_back(x)	Add to the back	O(1)
push_front(x)	Add to the front	O(1)
pop_back()	Remove from the back	O(1)
pop_front()	Remove from the front	O(1)
peek_front()	Read the front without removing	O(1)
peek_back()	Read the back without removing	O(1)

Space is O(n). Random access by index is O(n) for linked-list implementations, O(1) for array-backed ones. The four end operations stay constant time either way.

---

When Four Operations Beat Two

Think about a playlist you control from both ends. Songs play from the front. New songs go to the back. But you also want to jump a track to the front, or yank the last one you added because you immediately changed your mind. No standard queue handles all four. Neither does a stack.

The interview-relevant version: a sliding window of fixed size moving across an array. As the window advances, you expire elements from one end and add new ones to the other. You need to remove the expired element cheaply and track the maximum or minimum over the window. This is the setup for the monotonic deque pattern, which shows up constantly in interviews and trips up most people who see it for the first time.

---

How the Deque Data Structure Is Built

Two implementations dominate.

Doubly-linked list. Each node holds a value, a pointer to the previous node, and a pointer to the next. You keep references to the head and tail. Push or pop at either end is O(1). The cost: pointer overhead and poor cache behavior. Nodes scatter across the heap, so traversal triggers a lot of cache misses. You are essentially paying for the privilege of chasing pointers to memory addresses that want nothing to do with each other.

Circular array (ring buffer). A fixed-size array with front and back indices that wrap using modulo arithmetic. When the buffer fills, you resize it, the same way a dynamic array does. Push and pop at both ends stay O(1) amortized. No pointer chasing. Cache-friendly. This is the smarter implementation for most use cases.

The key insight of the ring buffer: instead of shifting elements, you move the indices. pop_front increments front by one. push_back writes to the current back slot and increments. When an index reaches the end of the array, it wraps to zero via % capacity. No element ever moves. The positions are all bookkeeping.

Python's collections.deque uses a doubly-linked list of fixed-size blocks, each holding about 64 pointers. Java's ArrayDeque uses a resizable circular array. C++'s std::deque uses a chunked scheme with non-contiguous memory segments, giving O(1) end operations but slightly worse cache behavior during iteration.

For interviews, you do not need to know the internals. You need to know which API to call.

---

Deque vs Stack vs Queue

A stack is LIFO: last in, first out. You only ever touch the top. Useful for DFS, function call simulation, parentheses matching, undo systems.

A queue is FIFO: first in, first out. You add to the back and remove from the front. Useful for BFS, job scheduling, anything where arrival order matters.

A deque is for problems where you need both ends active at the same time. The sliding window maximum is the canonical example. You also reach for a deque when pushing high-priority items to the front of a queue, implementing a stack and a queue with a single structure, or checking palindromes by comparing characters from both ends.

If your problem only touches one end, use a stack or queue. A deque where you only ever use one side is just a stack wearing a trench coat. See the queue vs deque tradeoff for a deeper comparison.

---

The Interview Pattern: Sliding Window Maximum

This is worth walking through because it shows exactly why the deque's two-ended behavior matters.

Problem: given an array and a window size k, return the maximum element in each window as it slides across the array.

Brute force is O(n x k): scan k elements per window. With n = 10^5 and k = 10^4, that is 10^9 operations. Write it if you need to think through the problem. Then throw it away.

The deque solution is O(n): each element enters and leaves the deque exactly once.

You maintain a deque storing array indices in decreasing order of their values. For each new element:

1. Pop from the front any index outside the current window.
2. Pop from the back any index whose value is smaller than the new element. Those elements can never be the window maximum: the new element is larger and will expire later.
3. Push the new index to the back.
4. The front of the deque holds the index of the current window's maximum.

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result = []
    window = deque()  # stores indices, back-to-front decreasing by value

    for i, num in enumerate(nums):
        while window and window[0] < i - k + 1:
            window.popleft()

        while window and nums[window[-1]] < num:
            window.pop()

        window.append(i)

        if i >= k - 1:
            result.append(nums[window[0]])

    return result

The deque acts as a queue (removing expired windows from the front via popleft) and a stack (removing dominated elements from the back via pop) at the same time. A pure queue cannot do the back removal. A pure stack cannot do the front expiration. This is why the deque is the right tool and not just a stylistic preference.

This pattern is called a monotonic deque. For a deeper treatment and more problems, see The Deque: Fast at Both Ends, and the Monotonic Deque Trick Worth Memorizing.

---

How Every Language Does It

from collections import deque

d = deque()
d.append(1)       # push_back
d.appendleft(2)   # push_front
d.pop()           # pop_back
d.popleft()       # pop_front
d[0]              # peek_front
d[-1]             # peek_back

import java.util.ArrayDeque;

Deque<Integer> d = new ArrayDeque<>();
d.addLast(1);     // push_back
d.addFirst(2);    // push_front
d.removeLast();   // pop_back
d.removeFirst();  // pop_front
d.peekFirst();    // peek_front
d.peekLast();     // peek_back

#include <deque>

std::deque<int> d;
d.push_back(1);
d.push_front(2);
d.pop_back();
d.pop_front();
d.front();   // peek_front
d.back();    // peek_back

// No native O(1) deque in JavaScript or TypeScript.
// push() and pop() at the back are O(1) amortized.
// unshift() and shift() at the front are O(n).
const d: number[] = [];
d.push(1);       // O(1) amortized, push_back
d.pop();         // O(1), pop_back
d.unshift(2);    // O(n), avoid in performance-sensitive code
d.shift();       // O(n), avoid in performance-sensitive code

Python and Java are the most ergonomic for interviews. C++ works fine if you enjoy prefixing everything with std::. JavaScript and TypeScript are the cautionary tale, which gets its own section.

---

The JavaScript Trap

JavaScript's array.shift() and array.unshift() are O(n). Every call shifts every element by one index. This is the kind of thing that works fine in your test cases and detonates at n = 10^5.

Here is how the conversation goes in an interview: you write a clean sliding window solution, it passes every test you trace through, and then the interviewer asks "what's the time complexity?" You say O(n). They nod. Then they ask about shift(). There is a pause. You do the math. You realize your O(n) solution is O(n^2).

If you use JavaScript for interviews and need O(1) pop_front, track a left index variable and increment it instead of calling shift(). This simulates front-of-queue behavior at O(1) cost, though it leaves stale elements at the front of the array until garbage collected.

function maxSlidingWindow(nums: number[], k: number): number[] {
  const result: number[] = [];
  const window: number[] = [];  // stores indices
  let left = 0;

  for (let i = 0; i < nums.length; i++) {
    while (window.length > 0 && window[left] < i - k + 1) left++;
    while (window.length > left && nums[window[window.length - 1]] < nums[i]) {
      window.pop();
    }
    window.push(i);
    if (i >= k - 1) result.push(nums[window[left]]);
  }

  return result;
}

The JavaScript community has been aware of this issue for years and has collectively decided not to fix it. Plan accordingly.

---

Where to Practice

The sliding window maximum (LeetCode 239) is the standard starting point. It is the problem that makes the deque's two-ended advantage obvious. From there, look at any sliding window problem where you need to maintain a minimum or maximum over the window rather than just a sum.

If you want feedback on whether you are explaining the deque pattern clearly under pressure, SpaceComplexity runs voice-based DSA interviews with rubric scoring on communication. A lot of candidates can write the code but cannot explain why the back-pop step is valid. That gap shows up in the debrief.

---

Further Reading

• Double-ended queue, Wikipedia
• collections.deque, Python documentation
• ArrayDeque, Java SE documentation
• std::deque, cppreference
• LeetCode 239: Sliding Window Maximum