ā† Back to DevBytes
Developer Tutorial July 12, 2026 15 min read

Interview Guide: Double-Ended Queues Problems and Solutions

Understanding Double-Ended Queues (Deques)

A double-ended queue, commonly abbreviated as deque (pronounced "deck"), is a linear data structure that allows insertion and deletion at both ends ā€” the front and the back. It generalizes both stacks (LIFO) and queues (FIFO), combining their capabilities into one flexible structure. You can think of it as a hybrid of a stack and a queue, where elements can be added or removed from either end in O(1) time in a well-designed implementation.

Core Operations

A deque typically supports the following fundamental operations:

Additionally, many implementations provide random-access indexing (getAtIndex, setAtIndex) when backed by an array, though this is not a strict requirement of the abstract data type.

Why Deques Matter in Technical Interviews

šŸš€ Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

Interviewers favor deque problems for several compelling reasons:

Implementing a Deque from Scratch

Approach 1: Doubly Linked List Implementation

This is the most intuitive approach. Each node has a prev and next pointer. We maintain pointers to both the head (front) and tail (back) of the list. All operations are O(1) since we never need to traverse the list.

// Doubly Linked List Node
class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LinkedListDeque {
  constructor() {
    this.head = null;   // front pointer
    this.tail = null;   // back pointer
    this.length = 0;
  }

  // O(1) - Insert at front
  pushFront(value) {
    const node = new Node(value);
    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.length++;
  }

  // O(1) - Insert at back
  pushBack(value) {
    const node = new Node(value);
    if (this.isEmpty()) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.length++;
  }

  // O(1) - Remove from front
  popFront() {
    if (this.isEmpty()) throw new Error("Deque is empty");
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null; // list became empty
    }
    this.length--;
    return value;
  }

  // O(1) - Remove from back
  popBack() {
    if (this.isEmpty()) throw new Error("Deque is empty");
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null; // list became empty
    }
    this.length--;
    return value;
  }

  peekFront() {
    if (this.isEmpty()) return undefined;
    return this.head.value;
  }

  peekBack() {
    if (this.isEmpty()) return undefined;
    return this.tail.value;
  }

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

Approach 2: Circular Buffer (Array-Based) Implementation

This approach uses a fixed-size or dynamically resizing array along with two indices: front and back. The "circular" nature means when we increment an index past the array's end, we wrap around to 0 using modular arithmetic. This is memory-efficient and cache-friendly, making it the preferred approach in performance-critical systems and the basis for Python's collections.deque and C++'s std::deque.

class CircularDeque {
  constructor(capacity = 16) {
    this.data = new Array(capacity);
    this.front = 0;   // index of the front element
    this.back = 0;    // index AFTER the last element (next insertion point)
    this.count = 0;
    this.capacity = capacity;
  }

  // Helper: compute next index in circular fashion
  _nextIndex(i) { return (i + 1) % this.capacity; }
  _prevIndex(i) { return (i - 1 + this.capacity) % this.capacity; }

  _resize(newCapacity) {
    const newData = new Array(newCapacity);
    // Copy existing elements starting from 'front' in order
    for (let i = 0; i < this.count; i++) {
      newData[i] = this.data[(this.front + i) % this.capacity];
    }
    this.data = newData;
    this.front = 0;
    this.back = this.count;
    this.capacity = newCapacity;
  }

  pushBack(value) {
    if (this.count === this.capacity) {
      this._resize(this.capacity * 2);
    }
    this.data[this.back] = value;
    this.back = this._nextIndex(this.back);
    this.count++;
  }

  pushFront(value) {
    if (this.count === this.capacity) {
      this._resize(this.capacity * 2);
    }
    this.front = this._prevIndex(this.front);
    this.data[this.front] = value;
    this.count++;
  }

  popFront() {
    if (this.isEmpty()) throw new Error("Deque is empty");
    const value = this.data[this.front];
    this.front = this._nextIndex(this.front);
    this.count--;
    return value;
  }

  popBack() {
    if (this.isEmpty()) throw new Error("Deque is empty");
    this.back = this._prevIndex(this.back);
    const value = this.data[this.back];
    this.count--;
    return value;
  }

  peekFront() {
    if (this.isEmpty()) return undefined;
    return this.data[this.front];
  }

  peekBack() {
    if (this.isEmpty()) return undefined;
    return this.data[this._prevIndex(this.back)];
  }

  isEmpty() { return this.count === 0; }
  size()    { return this.count; }
}

Built-In Deque Support Across Languages

In interviews, you'll often use the language's built-in deque rather than building your own. Here's how the major languages provide it:

// Java
import java.util.ArrayDeque;
import java.util.Deque;
Deque deque = new ArrayDeque<>();
deque.addFirst(10);  // pushFront
deque.addLast(20);   // pushBack
deque.removeFirst(); // popFront
deque.removeLast();  // popBack
deque.peekFirst();   // peekFront
deque.peekLast();    // peekBack

// Python
from collections import deque
d = deque()
d.append(10)        # pushBack
d.appendleft(20)    # pushFront
d.pop()             # popBack
d.popleft()         # popFront
d[0]                # peekFront
d[-1]               # peekBack

// C++
#include <deque>
std::deque<int> d;
d.push_front(10);
d.push_back(20);
d.pop_front();
d.pop_back();
d.front();          // peekFront
d.back();           // peekBack

Classic Interview Problems Using Deques

Problem 1: Sliding Window Maximum

Statement: Given an array nums and an integer k (window size), return an array of the maximum values for each sliding window of size k as it moves from left to right across the array.

Why a deque? A naive approach recalculates the max for each window, yielding O(n*k) time. Using a monotonic decreasing deque, we can achieve O(n) by maintaining candidates for future maximums. The deque stores indices (not values) and ensures the values corresponding to those indices are in strictly decreasing order. Before adding a new element, we pop from the back any indices whose values are smaller than the incoming value ā€” they can never be the maximum for any window that includes the new element.

function slidingWindowMax(nums, k) {
  const result = [];
  const deque = []; // will store indices, maintaining decreasing values
  // In JavaScript, we simulate a deque with an array and use
  // push/pop for the back, shift/unshift for the front.
  // For O(1) front removals, use a proper Deque implementation.
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices that are outside the current window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift(); // popFront: remove expired index
    }
    
    // Maintain monotonic decreasing order:
    // Pop from back all indices whose values are <= current value
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop(); // popBack: remove smaller/equal candidates
    }
    
    // Add current index
    deque.push(i); // pushBack
    
    // Window is formed when we've processed at least k elements
    if (i >= k - 1) {
      result.push(nums[deque[0]]); // front holds the max index
    }
  }
  
  return result;
}

// Example
console.log(slidingWindowMax([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Output: [3, 3, 5, 5, 6, 7]

Time Complexity: O(n) ā€” each element is pushed and popped at most once. Space Complexity: O(k) for the deque storage.

Problem 2: Sliding Window Minimum

This is the mirror of the previous problem. Simply change the monotonic property to increasing instead of decreasing. Pop from the back all indices whose values are greater than or equal to the current value.

function slidingWindowMin(nums, k) {
  const result = [];
  const deque = []; // stores indices, maintaining increasing values
  
  for (let i = 0; i < nums.length; i++) {
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Pop back while values are >= current (we want the smallest at front)
    while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Problem 3: Design a Browser History with Back/Forward Navigation

Statement: Implement a browser history that supports visit(url), back(steps), and forward(steps). Visiting a new URL clears all forward history. This maps perfectly to a deque-like structure with a "current" pointer.

Deque Insight: You maintain a list of URLs with an index pointer. When visiting a new page, you truncate everything after the pointer (popBack repeatedly or slice) and pushBack the new URL. Back/forward just move the pointer within bounds.

class BrowserHistory {
  constructor(homepage) {
    this.history = [homepage]; // using array as deque-like storage
    this.current = 0;          // index of the current page
  }

  visit(url) {
    // Clear all forward history: truncate array after current
    this.history.length = this.current + 1;
    // Add new URL at the back
    this.history.push(url);
    this.current++;
  }

  back(steps) {
    // Move current pointer back, but not beyond 0
    this.current = Math.max(0, this.current - steps);
    return this.history[this.current];
  }

  forward(steps) {
    // Move current pointer forward, but not beyond the last entry
    this.current = Math.min(this.history.length - 1, this.current + steps);
    return this.history[this.current];
  }
}

Problem 4: First Negative Integer in Every Window of Size K

Statement: For each window of size k in an array, return the first negative integer. If no negative exists in a window, return 0.

Deque Approach: Maintain a deque of indices of negative numbers within the current window. The front of the deque always holds the first negative. When sliding, remove expired indices from the front and add the new element's index if negative.

function firstNegativeInWindow(arr, k) {
  const result = [];
  const deque = []; // stores indices of negative numbers
  
  for (let i = 0; i < arr.length; i++) {
    // Remove indices that are out of the current window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // If current element is negative, add its index
    if (arr[i] < 0) {
      deque.push(i);
    }
    
    // Window formed
    if (i >= k - 1) {
      if (deque.length > 0) {
        result.push(arr[deque[0]]);
      } else {
        result.push(0);
      }
    }
  }
  
  return result;
}

console.log(firstNegativeInWindow([12, -1, 7, 8, -15, 30, 16, 28], 3));
// Output: [-1, -1, 0, -15, -15, 0]

Problem 5: Check If an Array Is a Valid Sequence of Deque Operations

Statement: Given an array of distinct integers and a target array, determine if the target can be obtained by pushing elements onto a deque and popping from either end in some order. This tests your understanding of the "permutation via deque" problem.

The core insight: when popping, you always remove from one of the two ends. This means at any point, the remaining elements must be a contiguous subarray of the original sorted order (if we push in sorted order), and the popped sequence must respect the "outside-in" property.

function isValidDequeSequence(pushed, popped) {
  // Use an actual deque to simulate
  const deque = [];
  let pushIdx = 0;
  
  for (const target of popped) {
    // Keep pushing until we have the target at either end
    while (pushIdx < pushed.length && 
           (deque.length === 0 || 
            (deque[0] !== target && deque[deque.length - 1] !== target))) {
      deque.push(pushed[pushIdx]);
      pushIdx++;
    }
    
    if (deque.length > 0 && deque[0] === target) {
      deque.shift(); // popFront matches
    } else if (deque.length > 0 && deque[deque.length - 1] === target) {
      deque.pop();   // popBack matches
    } else {
      return false; // cannot obtain this sequence
    }
  }
  
  return true;
}

// Example: push [1,2,3,4,5], can we pop [1,2,3,4,5]? Yes (always pop front)
console.log(isValidDequeSequence([1,2,3,4,5], [1,2,3,4,5])); // true
// Can we pop [3,1,2,4,5]? Let's check
console.log(isValidDequeSequence([1,2,3,4,5], [3,1,2,4,5])); // true
// Can we pop [3,4,2,1,5]? 
console.log(isValidDequeSequence([1,2,3,4,5], [3,4,2,1,5])); // true

Advanced Deque Techniques

Monotonic Deques for Range Queries

A monotonic deque is arguably the most powerful pattern involving deques. The idea is to maintain elements in sorted order (ascending or descending) while preserving the ability to remove expired (out-of-window) elements from the front. This pattern solves a whole family of problems:

// Generic monotonic deque template (decreasing)
function monotonicDequeTemplate(arr, k) {
  const deque = []; // store indices
  const result = [];
  
  for (let i = 0; i < arr.length; i++) {
    // 1. Remove expired (out-of-window) from FRONT
    while (deque.length && deque[0] <= i - k) {
      deque.shift();
    }
    
    // 2. Maintain monotonic property by popping from BACK
    //    For DECREASING: pop while back value <= current
    //    For INCREASING: pop while back value >= current
    while (deque.length && arr[deque[deque.length - 1]] <= arr[i]) {
      deque.pop();
    }
    
    // 3. Add current element
    deque.push(i);
    
    // 4. Answer query if window is formed
    if (i >= k - 1) {
      result.push(arr[deque[0]]);
    }
  }
  
  return result;
}

Deque as a "Two-Ended" Cache

Deques naturally model LRU (Least Recently Used) cache eviction policies. When an item is accessed, move it to the front (remove from middle, push to front). When eviction is needed, pop from the back. While a pure deque can't do O(1) middle removal, combining a deque with a hash map (pointing to nodes) gives us the classic LRU cache implementation.

Palindrome Checking with Deques

A fun but practical use: to check if a string is a palindrome, push all characters into a deque, then repeatedly pop from both ends and compare. If they match all the way until the deque is empty (or has one element left), it's a palindrome.

function isPalindrome(str) {
  const deque = [];
  // pushBack all characters
  for (const ch of str) {
    deque.push(ch);
  }
  
  while (deque.length > 1) {
    const front = deque.shift(); // popFront
    const back = deque.pop();    // popBack
    if (front !== back) return false;
  }
  
  return true;
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

Best Practices for Interviews

Common Pitfalls

Practice Problems Roadmap

Here's a curated progression to build deque mastery for interviews:

Conclusion

The double-ended queue is deceptively simple in definition but extraordinarily powerful in application. Its ability to provide O(1) access at both ends unlocks efficient solutions for an entire class of problems that would otherwise require nested loops or complex tree structures. The monotonic deque pattern in particular ā€” combining sorted-order maintenance with sliding window expiration ā€” is one of the most elegant algorithmic techniques you can wield in a technical interview. Master the circular buffer implementation to demonstrate low-level fluency, memorize the sliding window maximum solution as a template, and practice recognizing when "both ends matter." With these tools, you'll approach any deque problem with confidence and precision.

šŸš€ Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started ā€” $23.99/mo
ā† Back to all articles