Deque (Двусторонняя очередь)

Дек (double-ended queue) — структура, позволяющая добавлять и удалять элементы с обоих концов за O(1). Обобщение стека и очереди одновременно.

Сложности операций

Операция	Сложность
Добавить в начало / конец	O(1)
Удалить из начала / конца	O(1)
Доступ по индексу	O(n)

Реализация (на объекте с указателями)

Наивный дек на массиве JS страдает от shift/unshift за O(n). Эффективная версия — на объекте с двумя указателями:

class Deque {
    constructor() { this.map = {}; this.head = 0; this.tail = 0; }
 
    pushBack(v)  { this.map[this.tail++] = v; }
    pushFront(v) { this.map[--this.head] = v; }
 
    popBack() {
        if (this.isEmpty()) return undefined;
        const v = this.map[--this.tail]; delete this.map[this.tail]; return v;
    }
    popFront() {
        if (this.isEmpty()) return undefined;
        const v = this.map[this.head]; delete this.map[this.head++]; return v;
    }
 
    get size() { return this.tail - this.head; }
    isEmpty()  { return this.size === 0; }
}

Монотонный дек (Monotonic Deque)

Дек, в котором элементы поддерживаются в отсортированном порядке — снимаем с конца всё, что «хуже» нового элемента. Ключевой приём для задач «максимум/минимум в скользящем окне» за O(n) (например, Sliding Window Maximum).

// Индексы, значения по убыванию; фронт — максимум текущего окна
const dq = []; // хранит индексы
for (let i = 0; i < nums.length; i++) {
    while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (dq[0] <= i - k) dq.shift(); // элемент вышел из окна
    // nums[dq[0]] — максимум окна
}

См. также

• queue — очередь FIFO
• sliding-window — монотонный дек для окна