Deque (Double-Ended Queue)

Push/pop from both ends in O(1) — the backbone of BFS and sliding window max

A deque lets you efficiently add/remove from both front and back. In interviews it appears in two contexts: BFS (queue behaviour) and sliding window maximum (monotonic deque).

Language:

Python

All languages — Basic operations

JavaScript

// JS arrays support both ends, but shift/unshift are O(n).
// For true O(1) deque in interviews, arrays are usually fine.

const dq = [];
dq.push(1);        // push right
dq.push(2);
dq.unshift(0);     // push left  ← O(n)

dq.pop();          // pop right → 2
dq.shift();        // pop left  → 0   ← O(n)

dq[0];             // peek left
dq[dq.length-1];   // peek right

TypeScript

const dq: number[] = [];
dq.push(1);
dq.push(2);
dq.unshift(0);
dq.pop();
dq.shift();

Java

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

Deque<Integer> dq = new ArrayDeque<>();
dq.addLast(1);     // push right
dq.addLast(2);
dq.addFirst(0);    // push left

dq.pollLast();     // pop right → 2
dq.pollFirst();    // pop left  → 0

dq.peekFirst();    // peek left
dq.peekLast();     // peek right

// Go has no built-in deque — use a slice:
dq := []int{}
dq = append(dq, 1)          // push right
dq = append([]int{0}, dq...)  // push left (O(n) copy)

// Pop right:
right := dq[len(dq)-1]; dq = dq[:len(dq)-1]

// Pop left:
left := dq[0]; dq = dq[1:]

fmt.Println(right, left)

C++

#include <deque>

deque<int> dq;
dq.push_back(1);   // push right
dq.push_back(2);
dq.push_front(0);  // push left

dq.pop_back();     // pop right
dq.pop_front();    // pop left

dq.front();        // peek left
dq.back();         // peek right