Deques (Double-Ended Queues)

November 19, 2025
#deque #double-ended-queue #data-structures #algorithms

Table of Contents

Introduction

A deque (pronounced “deck”) is short for “double-ended queue”—a linear data structure that allows insertion and deletion at both the front and the rear. Think of it as a hybrid between a stack and a queue, offering the flexibility to add or remove elements from either end.

This versatility makes deques powerful for problems requiring sliding windows, palindrome checking, and maintaining ordered sequences with efficient operations at both ends. By the end of this tutorial, you’ll understand when deques shine and how to implement them efficiently.

If you’re new to data structures, review Big-O Notation, Arrays, Linked Lists, Stacks, and Queues first.

What is a deque?

A deque is a generalized queue that supports four primary operations:

  1. addFront (or pushFront): Add an element to the front
  2. addRear (or pushRear): Add an element to the rear
  3. removeFront (or popFront): Remove and return the element from the front
  4. removeRear (or popRear): Remove and return the element from the rear

Additional operations include: 5. peekFront: View the front element without removing it 6. peekRear: View the rear element without removing it 7. isEmpty: Check if the deque is empty 8. size: Get the number of elements

The key feature: bidirectional access allows adding and removing from both ends efficiently.

Why use a deque?

Choose a deque when:

  1. You need efficient operations at both ends (unlike queues or stacks)
  2. You’re implementing sliding window algorithms
  3. You need a data structure that can act as both a stack and a queue
  4. You’re checking for palindromes or processing sequences bidirectionally
  5. You’re implementing work-stealing algorithms in concurrent systems
  6. You need to maintain a limited-size buffer with eviction from either end

Avoid a deque when:

  • You only need single-end access (use a stack or queue)
  • You need random access to elements (use an array)
  • You need priority-based ordering (use a priority queue)

Real-world applications

Deques are used in various scenarios:

  • Browser history: Navigate forward and backward through pages
  • Undo/Redo systems: Add to front for undo, remove from rear for old operations
  • Sliding window problems: Maintain maximum/minimum in a window
  • Work stealing: In multi-threaded schedulers, threads steal work from both ends
  • Palindrome checking: Compare characters from both ends moving inward
  • A pathfinding*: Efficiently manage the open set with bidirectional access
  • Text editors: Managing cursor position with efficient insertion/deletion

Deque vs Stack vs Queue

Feature Deque Stack Queue
Front insertion ✅ O(1) ✅ O(1) (top) ❌ Not typical
Rear insertion ✅ O(1) ❌ Not typical ✅ O(1)
Front removal ✅ O(1) ✅ O(1) (top) ✅ O(1)
Rear removal ✅ O(1) ❌ Not typical ❌ Not typical
Use as stack ✅ Yes ✅ Yes ❌ No
Use as queue ✅ Yes ❌ No ✅ Yes

Core operations and complexity

All primary deque operations are constant time:

  • addFront: O(1) — add element to front
  • addRear: O(1) — add element to rear
  • removeFront: O(1) — remove and return front element
  • removeRear: O(1) — remove and return rear element
  • peekFront: O(1) — view front element
  • peekRear: O(1) — view rear element
  • isEmpty: O(1) — check if empty
  • size: O(1) — get number of elements
  • Space: O(n) — where n is the number of elements

Deque implementation

Deques are best implemented using doubly linked lists for true O(1) operations at both ends. Some languages provide built-in deque implementations.

Doubly linked list-based deque

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  addFront(element) {
    const node = new Node(element);
    if (this.isEmpty()) {
      this.front = this.rear = node;
    } else {
      node.next = this.front;
      this.front.prev = node;
      this.front = node;
    }
    this.length++;
  }

  addRear(element) {
    const node = new Node(element);
    if (this.isEmpty()) {
      this.front = this.rear = node;
    } else {
      node.prev = this.rear;
      this.rear.next = node;
      this.rear = node;
    }
    this.length++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.front.value;
    this.front = this.front.next;
    if (this.front === null) {
      this.rear = null; // Deque is now empty
    } else {
      this.front.prev = null;
    }
    this.length--;
    return value;
  }

  removeRear() {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.rear.value;
    this.rear = this.rear.prev;
    if (this.rear === null) {
      this.front = null; // Deque is now empty
    } else {
      this.rear.next = null;
    }
    this.length--;
    return value;
  }

  peekFront() {
    return this.isEmpty() ? undefined : this.front.value;
  }

  peekRear() {
    return this.isEmpty() ? undefined : this.rear.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }

  toArray() {
    const result = [];
    let current = this.front;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

// Example usage
const deque = new Deque();
deque.addRear(10);
deque.addRear(20);
deque.addFront(5);
console.log(deque.toArray());     // [5, 10, 20]
console.log(deque.removeFront()); // 5
console.log(deque.removeRear());  // 20
console.log(deque.toArray());     // [10]

class Node:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.length = 0

    def add_front(self, element):
        node = Node(element)
        if self.is_empty():
            self.front = self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.length += 1

    def add_rear(self, element):
        node = Node(element)
        if self.is_empty():
            self.front = self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.length += 1

    def remove_front(self):
        if self.is_empty():
            return None
        value = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None  # Deque is now empty
        else:
            self.front.prev = None
        self.length -= 1
        return value

    def remove_rear(self):
        if self.is_empty():
            return None
        value = self.rear.value
        self.rear = self.rear.prev
        if self.rear is None:
            self.front = None  # Deque is now empty
        else:
            self.rear.next = None
        self.length -= 1
        return value

    def peek_front(self):
        return None if self.is_empty() else self.front.value

    def peek_rear(self):
        return None if self.is_empty() else self.rear.value

    def is_empty(self):
        return self.length == 0

    def size(self):
        return self.length

    def to_list(self):
        result = []
        current = self.front
        while current:
            result.append(current.value)
            current = current.next
        return result

# Example usage - Python also has collections.deque built-in
deque = Deque()
deque.add_rear(10)
deque.add_rear(20)
deque.add_front(5)
print(deque.to_list())       # [5, 10, 20]
print(deque.remove_front())  # 5
print(deque.remove_rear())   # 20
print(deque.to_list())       # [10]

class Node {
    int value;
    Node prev;
    Node next;

    Node(int value) {
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

public class Deque {
    private Node front;
    private Node rear;
    private int length;

    public Deque() {
        this.front = null;
        this.rear = null;
        this.length = 0;
    }

    public void addFront(int element) {
        Node node = new Node(element);
        if (isEmpty()) {
            front = rear = node;
        } else {
            node.next = front;
            front.prev = node;
            front = node;
        }
        length++;
    }

    public void addRear(int element) {
        Node node = new Node(element);
        if (isEmpty()) {
            front = rear = node;
        } else {
            node.prev = rear;
            rear.next = node;
            rear = node;
        }
        length++;
    }

    public Integer removeFront() {
        if (isEmpty()) {
            return null;
        }
        int value = front.value;
        front = front.next;
        if (front == null) {
            rear = null; // Deque is now empty
        } else {
            front.prev = null;
        }
        length--;
        return value;
    }

    public Integer removeRear() {
        if (isEmpty()) {
            return null;
        }
        int value = rear.value;
        rear = rear.prev;
        if (rear == null) {
            front = null; // Deque is now empty
        } else {
            rear.next = null;
        }
        length--;
        return value;
    }

    public Integer peekFront() {
        return isEmpty() ? null : front.value;
    }

    public Integer peekRear() {
        return isEmpty() ? null : rear.value;
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public int size() {
        return length;
    }

    public static void main(String[] args) {
        Deque deque = new Deque();
        deque.addRear(10);
        deque.addRear(20);
        deque.addFront(5);
        System.out.println(deque.removeFront()); // 5
        System.out.println(deque.removeRear());  // 20
        System.out.println(deque.size());        // 1
    }
}

Using built-in deques

Many languages provide optimized deque implementations:

// JavaScript doesn't have a built-in deque, but arrays work reasonably well
// for small deques (though shift/unshift are O(n))
const deque = [];

// Add operations
deque.push(10);      // Add rear
deque.unshift(5);    // Add front

// Remove operations
const front = deque.shift();  // Remove front
const rear = deque.pop();     // Remove rear

// Peek operations
const peekFront = deque[0];
const peekRear = deque[deque.length - 1];

console.log(deque);

from collections import deque

# Python's collections.deque is highly optimized
d = deque()

# Add operations
d.append(10)      # Add rear - O(1)
d.appendleft(5)   # Add front - O(1)

# Remove operations
front = d.popleft()  # Remove front - O(1)
rear = d.pop()       # Remove rear - O(1)

# Peek operations (use indexing)
d.append(20)
d.append(30)
peek_front = d[0]    # Front element
peek_rear = d[-1]    # Rear element

print(list(d))

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

// Java's ArrayDeque is the standard implementation
Deque<Integer> deque = new ArrayDeque<>();

// Add operations
deque.addLast(10);   // Add rear - O(1)
deque.addFirst(5);   // Add front - O(1)
// Alternative: offerFirst(), offerLast()

// Remove operations
int front = deque.removeFirst();  // Remove front - O(1)
int rear = deque.removeLast();    // Remove rear - O(1)
// Alternative: pollFirst(), pollLast()

// Peek operations
deque.addLast(20);
deque.addLast(30);
int peekFront = deque.peekFirst();  // Front element
int peekRear = deque.peekLast();    // Rear element

System.out.println(deque);

Common deque problems

1. Palindrome checker

Check if a string is a palindrome by comparing from both ends:

function isPalindrome(str) {
  const deque = str.toLowerCase().replace(/[^a-z0-9]/g, '').split('');

  while (deque.length > 1) {
    if (deque.shift() !== deque.pop()) {
      return false;
    }
  }

  return true;
}

console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

from collections import deque

def is_palindrome(s):
    # Clean and convert to deque
    cleaned = ''.join(c.lower() for c in s if c.isalnum())
    d = deque(cleaned)

    while len(d) > 1:
        if d.popleft() != d.pop():
            return False

    return True

print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))  # False

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

public class PalindromeChecker {
    public static boolean isPalindrome(String s) {
        // Clean and convert to deque
        Deque<Character> deque = new ArrayDeque<>();
        for (char c : s.toLowerCase().toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                deque.addLast(c);
            }
        }

        while (deque.size() > 1) {
            if (!deque.removeFirst().equals(deque.removeLast())) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
        // true
        System.out.println(isPalindrome("race a car")); // false
    }
}

2. Sliding window maximum

Find the maximum value in each sliding window of size k:

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // Stores indices

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the window
    if (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }

    // Remove smaller elements from rear (they won't be max)
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);

    // Add to result once we have a full window
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

console.log(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3));
// [3, 3, 5, 5, 6, 7]

from collections import deque

def max_sliding_window(nums, k):
    result = []
    dq = deque()  # Stores indices

    for i in range(len(nums)):
        # Remove indices outside the window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove smaller elements from rear
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # Add to result once we have a full window
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

import java.util.*;

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];

        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>(); // Stores indices

        for (int i = 0; i < nums.length; i++) {
            // Remove indices outside the window
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove smaller elements from rear
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i);

            // Add to result once we have a full window
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] result = maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3);
        System.out.println(Arrays.toString(result));
        // [3, 3, 5, 5, 6, 7]
    }
}

3. Implement a circular tour (gas stations problem)

Use a deque to find the starting point for a circular tour:

function canCompleteCircuit(gas, cost) {
  const n = gas.length;
  let totalGas = 0, totalCost = 0;
  let start = 0, tank = 0;

  for (let i = 0; i < n; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
    tank += gas[i] - cost[i];

    // If tank is negative, we can't reach next station
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }

  return totalGas >= totalCost ? start : -1;
}

console.log(canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2])); // 3

def can_complete_circuit(gas, cost):
    n = len(gas)
    total_gas, total_cost = 0, 0
    start, tank = 0, 0

    for i in range(n):
        total_gas += gas[i]
        total_cost += cost[i]
        tank += gas[i] - cost[i]

        # If tank is negative, we can't reach next station
        if tank < 0:
            start = i + 1
            tank = 0

    return start if total_gas >= total_cost else -1

print(can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]))  # 3

public class CircularTour {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int totalGas = 0, totalCost = 0;
        int start = 0, tank = 0;

        for (int i = 0; i < n; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];

            // If tank is negative, we can't reach next station
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return totalGas >= totalCost ? start : -1;
    }

    public static void main(String[] args) {
        System.out.println(canCompleteCircuit(
            new int[]{1,2,3,4,5},
            new int[]{3,4,5,1,2}
        )); // 3
    }
}

Common pitfalls

  • Array-based front operations are O(n): Using array unshift() or shift() is inefficient. Use doubly linked lists or built-in deques.
  • Forgetting to update both pointers: When removing the last element, ensure both front and rear are set to null
  • Not checking for empty deque: Always verify before removing or peeking
  • Confusing which end is which: Clearly document front vs rear in your implementation
  • Memory management: In manual-memory languages, free nodes properly

When to prefer other data structures

  • Need single-end access only → Use stack or queue
  • Need random access → Use array
  • Need priority ordering → Use priority queue (heap)
  • Need key-based lookup → Use hash table

Practice problems

  1. Implement a deque using a circular array with fixed capacity
  2. Reverse a deque in place
  3. Find the first negative integer in every window of size k
  4. Implement LRU cache using a deque and hash map
  5. Design a browser history system with forward/back buttons using a deque
  6. Solve the “Maximum of all subarrays of size k” using a deque
  7. Check if a given array can be divided into pairs of consecutive numbers
  8. Implement a deque-based solution for the “Trapping Rain Water” problem
  9. Design an age-based priority system using a deque
  10. Solve the “Jump Game” problem using a deque for optimization

Complexity summary

  • Time complexity:
    • addFront: O(1)
    • addRear: O(1)
    • removeFront: O(1)
    • removeRear: O(1)
    • peekFront: O(1)
    • peekRear: O(1)
    • isEmpty: O(1)
    • size: O(1)
  • Space complexity: O(n) where n is the number of elements

Deques combine the best of stacks and queues, providing constant-time operations at both ends and making them ideal for bidirectional data processing.

Thanks for visiting
We are actively updating content to this site. Thanks for visiting! Please bookmark this page and visit again soon.
Sponsor