Deque (Double-Ended Queue)

Concept

A Deque (pronounced “deck”, short for Double-Ended Queue) is a data structure that allows insertion and deletion from both the front and the back in $O(1)$ time.

It essentially combines the capabilities of a Stack (which only operates on the back/top) and a standard Queue (which inserts at the back and deletes at the front).

Core Operations

A Deque supports four core $O(1)$ operations:

1. addFront(item)
2. addBack(item)
3. removeFront()
4. removeBack()

Implementation

Under the hood, a Deque is usually implemented using a Doubly Linked List.
Because a Doubly Linked List has prev and next pointers, as well as a Head and Tail reference, adding or severing nodes from either the absolute front or the absolute back takes exactly $O(1)$ pointer rewiring time.

(Alternatively, it can be implemented using a dynamically resizing Circular Array).

Language Support

• Python: Python has a phenomenal built-in Deque: from collections import deque. It supports d.append(), d.appendleft(), d.pop(), and d.popleft().
• Java: Deque<Integer> deque = new ArrayDeque<>();
• C++: std::deque<int> d;
• JavaScript/TypeScript: WARNING: JavaScript does not have a built-in Deque. If an interview problem absolutely requires a Deque, you must either use an Array and accept the $O(N)$ .shift() penalty (explicitly telling the interviewer why), or quickly code up a basic Doubly Linked List from scratch.

When to use a Deque?

You rarely use a Deque just for the sake of it. You use a Deque when you specifically need to maintain a Monotonic Sliding Window.

The classic problem is “Sliding Window Maximum” (LeetCode 239).
Problem: Given an array and a sliding window of size K, return the maximum number in every window as it slides from left to right.

If you use a naive approach to scan the window for the max number every time it slides, it takes $O(N \times K)$ time.

By using a Deque to store the indices of the array, you can drop the time to $O(N)$:

1. The Deque must be Strictly Decreasing.
2. When a new number arrives, it goes to the Back of the Deque. BUT FIRST, it brutally kicks out (removeBack) any numbers smaller than itself. (Because if the new number is bigger, the older, smaller numbers can mathematically never be the maximum of this window or any future window!).
3. Then, you check the Front of the Deque. If the index at the front has physically fallen out of the sliding window, you removeFront().
4. The true maximum of the current window is always sitting exactly at the Front of the Deque!

Interview Questions

Q: Can a Deque be used to check if a word is a Palindrome?
A: Yes! While Two Pointers is the standard way to check a palindrome string in-place, if the string is coming in as a stream of characters, you can load them into a Deque. You then run a loop: removeFront() and removeBack(). If the two characters match, continue. If the Deque empties successfully (or 1 char remains), it’s a palindrome.

Q: A developer uses a Deque to build a standard LIFO Stack. Is this a bad idea?
A: It is a perfectly valid idea! In fact, in Java, using the Stack class is actually deprecated because it is bloated with legacy thread-synchronization locks. The official Java documentation explicitly recommends using Deque<Integer> stack = new ArrayDeque<>(); as the modern, fastest way to implement a Stack! You just restrict yourself to using addBack() and removeBack().