Lesson 16 · Linear structures

Deques

A Deque (Double-Ended Queue, pronounced 'deck') is a versatile data structure that combines the capabilities of both a stack and a queue. It supports O(1) insertions and deletions at both ends.

A Hybrid Structure

While a stack strictly enforces LIFO (one end) and a queue enforces FIFO (two ends, one-way), a deque relaxes these rules. You have full access to both boundaries.

You can push_front, push_back, pop_front, and pop_back. This makes the deque a superset of stacks and queues; you can use a deque to implement either.

Four primary O(1) operations
More versatile than stacks or queues
Often implemented as a Doubly Linked List

Implementation Details

A deque is typically implemented in one of two ways. The first is a Doubly Linked List, which trivially supports O(1) operations at both the head and tail.

The second (often used in Python's collections.deque and C++ std::deque) is a block-allocated array. It allocates memory in chunks, providing the cache-friendliness of arrays with the flexibility of linked nodes.

Doubly linked lists provide strict O(1)
Block arrays provide better cache locality
Python's deque is highly optimized in C

Key reference

Terms, operations, and practical uses

Core capabilities

Double-EndedPermits insertions and deletions at both the front and the rear boundaries.
Superset StructureA deque can act purely as a stack (using one end) or purely as a queue (using opposite ends).
SymmetryAlgorithms that require processing data from both ends simultaneously, like palindrome checking, fit deques perfectly.

Implementation strategies

Doubly Linked ListThe simplest way to build a deque, providing strict O(1) operations by tracking head and tail nodes.
Block ArraysThe standard C++ and Python approach. Allocates memory in chunks (blocks) and links the blocks together for cache efficiency.
Circular DequeImplementing a deque within a single fixed-size array using modulo arithmetic for both front and rear pointers.

Algorithmic uses

Sliding Window MaximumUsing a deque to store indices of useful elements in a moving window, solving the problem in O(N) time.
Undo/Redo HistoryUsing a deque to store actions. If the history limit is reached, the oldest action is popped from the front.
Stealing SchedulerWork-stealing thread pools use deques. A thread pops tasks from the rear of its own deque, but steals from the front of others.

Code example

Checking for a Palindrome

from collections import deque

def is_palindrome(word):
    d = deque(word)
    while len(d) > 1:
        if d.popleft() != d.pop():
            return False
    return True

print('It is a palindrome' if is_palindrome("racecar") else 'Not a palindrome')

#include <iostream>
#include <deque>
using namespace std;

bool isPalindrome(string word) {
    deque<char> d;
    for (char c : word) d.push_back(c);
    while (d.size() > 1) {
        if (d.front() != d.back()) return false;
        d.pop_front();
        d.pop_back();
    }
    return true;
}

int main() {
    cout << (isPalindrome("racecar") ? "True" : "False") << endl;
    return 0;
}

import java.util.*;

class Main {
    public static boolean isPalindrome(String word) {
        Deque<Character> d = new ArrayDeque<>();
        for (char c : word.toCharArray()) d.addLast(c);
        while (d.size() > 1) {
            if (d.removeFirst() != d.removeLast()) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        System.out.println(isPalindrome("racecar"));
    }
}

InputWord: 'r a c e c a r'

OutputIt is a palindrome

Example

Run the example step by step

Output

Sliding Window Maximum

Deques are the secret weapon for the famous Sliding Window Maximum algorithmic problem. As a window moves across an array, you need to know the maximum value inside it in O(1) time.

By storing indices in a deque and strictly maintaining a monotonically decreasing order (popping smaller elements from the back), the maximum for the current window is always at the front of the deque.

Classic hard algorithmic pattern
Maintains useful candidates only
Achieves O(N) time overall

Palindrome Checking

Because you can access both ends simultaneously, deques are perfect for symmetrical problems. To check if a word is a palindrome, load the characters into a deque.

Then, repeatedly pop_front and pop_back and compare them. If they match until the deque has 1 or 0 characters left, it is a palindrome.

Natural fit for two-pointer problems
Simplifies symmetric logic
Useful for undo/redo with length limits