Дек: Двусторонняя суперсила

Цели урока

• Понять дек как обобщение стека и очереди
• Освоить 6 операций дека - все O(1)
• Решить Sliding Window Maximum за O(n)
• Применить дек для проверки палиндрома

Предварительные знания

• Стеки (LIFO) и очереди (FIFO)

• Стеки: LIFO и трюк со скобками
• Очереди: FIFO и честный порядок

Как найти максимум в скользящем окне за O(n), а не O(n×k)? Монотонный дек - секретное оружие!

• **Sliding Window** алгоритмы в стриминге
• **Планировщики задач**: work stealing
• **Обработка текста**: палиндромы, анаграммы
• **Python deque**: универсальная структура

От формального определения у Кнута до work-stealing планировщиков

Идея структуры с доступом к обоим концам появилась естественно из обобщения стека и очереди, но строгое формальное изложение дал Дональд Кнут в первом томе The Art of Computer Programming (1968). Там дек (double-ended queue) описан как массив с двумя указателями и операциями добавления и удаления на каждом конце. Кнут же ввёл удобную классификацию: вырожденные деки, где один конец доступен только для вставки или только для удаления, дают input-restricted и output-restricted очереди. По-настоящему массовое применение дек получил в параллельных вычислениях. В 1994 году Роберт Блумофе и Чарльз Лейзерсон описали алгоритм work stealing для планировщика задач: каждый поток держит собственный дек готовых задач, берёт работу со своего конца, а простаивающие потоки крадут задачи с противоположного конца чужих деков. Этот подход лёг в основу системы Cilk и позже разошёлся по пулам потоков в Java, Go и .NET.

Дек - лучшее от стека и очереди

**Дек (Deque)** = Double-Ended Queue. Операции с **обоих концов** за O(1)!

**Дек может работать как:**

• **Стек**: push_back + pop_back (LIFO)
• **Очередь**: push_back + pop_front (FIFO)
• **Стек с другого конца**: push_front + pop_front

В Python: `collections.deque` - готовая реализация с O(1) для всех операций на концах.

6 операций - все O(1)

Дек предоставляет симметричный набор операций:

**list в Python** - плохой дек! `insert(0, x)` и `pop(0)` - O(n). Используй `deque`!

Реализация: двусвязный список

Идеальная реализация дека - **двусвязный список** с указателями head и tail.

**Альтернатива**: блочный массив (как в Python deque) - несколько массивов фиксированного размера. Хороший компромисс между памятью и скоростью.

Sliding Window Maximum - сила дека

Классическая задача: найти максимум в каждом окне размера k за **O(n)**.

**Наивное решение**: для каждого окна ищем max → O(n × k). Можно лучше!

**Монотонный дек**: элементы в деке всегда убывают. Максимум - всегда в начале!

Проверка палиндрома с деком

Дек идеален для сравнения с обоих концов - например, проверка **палиндрома**.

**Другие применения дека:**

• **Undo/Redo с ограничением**: храним последние N действий
• **Кража работы (work stealing)**: параллельные алгоритмы
• **A-Steal алгоритм**: планирование задач

Реализуй стек и очередь через один deque: ```python from collections import deque class StackAndQueue: def __init__(self): self.d = deque() # Стек операции def stack_push(self, x): pass def stack_pop(self): pass # Очередь операции def queue_push(self, x): pass def queue_pop(self): pass ```

from collections import deque class StackAndQueue: def __init__(self): self.d = deque() # Стек: работаем с правым концом (LIFO) def stack_push(self, x): self.d.append(x) def stack_pop(self): return self.d.pop() # Очередь: добавляем справа, берём слева (FIFO) def queue_push(self, x): self.d.append(x) def queue_pop(self): return self.d.popleft()

Реализуй дек с методом get_max() за O(1) (аналог MinStack): ```python class MaxDeque: def __init__(self): pass def push_back(self, x): pass def pop_front(self): pass def get_max(self): pass # O(1)! ```

from collections import deque class MaxDeque: def __init__(self): self.data = deque() self.maxes = deque() # Монотонно убывающий дек def push_back(self, x): self.data.append(x) # Удаляем меньшие элементы из конца maxes while self.maxes and self.maxes[-1] < x: self.maxes.pop() self.maxes.append(x) def pop_front(self): val = self.data.popleft() if val == self.maxes[0]: self.maxes.popleft() return val def get_max(self): return self.maxes[0]

Найди длину самого длинного подмассива, где max - min ≤ limit: ```python def longest_subarray(nums, limit): # nums = [8, 2, 4, 7], limit = 4 # Ответ: 2 ([2, 4] или [4, 7]) pass ``` Используй два монотонных дека для отслеживания min и max.

from collections import deque def longest_subarray(nums, limit): max_dq = deque() # Убывающий (максимум в начале) min_dq = deque() # Возрастающий (минимум в начале) left = 0 result = 0 for right, num in enumerate(nums): # Поддерживаем монотонность while max_dq and nums[max_dq[-1]] < num: max_dq.pop() while min_dq and nums[min_dq[-1]] > num: min_dq.pop() max_dq.append(right) min_dq.append(right) # Сужаем окно пока условие нарушено while nums[max_dq[0]] - nums[min_dq[0]] > limit: left += 1 if max_dq[0] < left: max_dq.popleft() if min_dq[0] < left: min_dq.popleft() result = max(result, right - left + 1) return result

Связанные темы

Дек открывает путь к продвинутым алгоритмам:

• Монотонный стек — Похожая техника для задач типа Next Greater Element
• Sliding Window — Дек - ключ к оптимальным решениям
• Приоритетная очередь — Когда нужен не max окна, а k-й элемент

Ключевые идеи

• **Дек** = Double-Ended Queue - операции с обоих концов
• **6 операций** - все O(1): push/pop с front и back
• **Реализация**: двусвязный список или блочный массив
• **Монотонный дек**: элементы отсортированы, экстремум в начале
• **Sliding Window Maximum**: O(n) вместо O(n×k)

Вопросы для размышления

• Почему collections.deque в Python быстрее list для операций с началом?
• Как бы ты решил Sliding Window Minimum?
• В каких задачах монотонный дек эффективнее кучи (heap)?

Связанные уроки

• ds-03-stacks — Stack is a restricted deque (one open end)
• ds-04-queues — Queue is a restricted deque (FIFO)
• ds-02-linked-lists — Doubly-linked list is the natural deque backing structure
• ds-20-lru-cache — LRU cache uses a deque (doubly-linked list) as its core
• alg-01-big-o