Overview

std::deque is a double-ended queue. It supports efficient push and pop from both ends while still providing O(1) indexed access.

Use it when both ends matter. Use std::vector when only the back grows and contiguous memory is important.

Common Includes

#include <cstddef>
#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

Basic Operations

std::deque<int> dq;

dq.push_back(10);
dq.push_front(5);
dq.push_back(20);

int front = dq.front();                   // 5
int back = dq.back();                     // 20
int middle = dq[1];                       // 10

dq.pop_front();
dq.pop_back();

push_front(value) and push_back(value) add an element at the corresponding end. pop_front() and pop_back() remove an element but return no value. Read the element first when it is needed.

front(), back(), pop_front(), and pop_back() require a non-empty deque. operator[] requires a valid index and does not check bounds; at(index) throws std::out_of_range for an invalid index.

Iteration:

for (int x : dq) {
  // read x
}

for (auto it = dq.begin(); it != dq.end(); ++it) {
  // random-access iterator
}

Memory Model

A vector stores its elements contiguously. A typical deque implementation uses multiple allocated blocks plus an internal structure that locates those blocks. The exact block layout is an implementation detail; the portable guarantee is random-access iteration without contiguous storage.

Consequences:

• deque[i] is still O(1).
• deque[i] usually has one more level of indirection than vector[i].
• push_front and push_back do not shift all existing elements.
• deque is not stored in one contiguous memory block.

This is why deque is useful when front growth matters but indexed access is still needed.

Invalidation Rules

Deque invalidation depends on where mutation occurs:

• Insertion at either end invalidates all iterators, including a saved end(), but preserves references and pointers to existing elements.
• Insertion in the middle invalidates all iterators, references, and pointers.
• Erasing only at an end invalidates iterators and references to erased elements; erasing the last element also invalidates the past-the-end iterator.
• Erasing from the middle invalidates all iterators and references.

Stable references at the ends do not imply stable iterators. Keep the distinction explicit in APIs that retain handles into a deque.

Sliding Window Maximum

The standard monotonic deque pattern stores indices, not values.

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
  std::vector<int> ans;
  std::deque<int> dq;                     // stores indices

  if (k <= 0 || static_cast<std::size_t>(k) > nums.size()) {
    return ans;
  }

  for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
    while (!dq.empty() && dq.front() <= i - k) {
      dq.pop_front();
    }

    while (!dq.empty() && nums[dq.back()] <= nums[i]) {
      dq.pop_back();
    }

    dq.push_back(i);

    if (i >= k - 1) {
      ans.push_back(nums[dq.front()]);
    }
  }

  return ans;
}

Why it works:

• The front is always the best candidate for the current window.
• Expired indices are removed from the front.
• Worse candidates are removed from the back.
• Each index enters and leaves the deque at most once, so the algorithm is O(n).
• The function explicitly rejects non-positive windows and windows larger than the input.

queue and stack Defaults

std::queue and std::stack are adapters. By default, both use std::deque internally.

std::queue<int> q;                        // backed by deque by default
std::stack<int> st;                       // backed by deque by default

This is because deque supports efficient operations at both ends without requiring one contiguous buffer.

Complexity

Checklist

• Use deque for monotonic queue patterns.
• Use deque when both front and back operations are needed.
• Use vector when contiguous memory and cache locality matter more.
• Do not assume deque storage is contiguous.
• Distinguish stable references from invalidated iterators after end insertion.
• For sliding windows, usually store indices so expiry is easy.

Further Reading

• C++ working draft: deque
• C++ working draft: deque modifiers and invalidation