Визуализация
Сценарий: Работа с двух концов
Легенда цветов
Как работает дек
Идея структуры: Дек (Deque, читается как "дэк", сокращение от Double-Ended Queue) представляет собой гибридную структуру данных. В отличие от стандартной очереди, где элементы добавляются строго в конец и удаляются строго из начала, дек позволяет совершать и вставку, и удаление на обоих концах списка.
Обобщение стека и очереди:
Дек - универсальная структура. Изменяя набор используемых операций, вы получаете либо стек, либо очередь:
- Стек (Stack): Если использовать только один конец (например,
pushFrontдля добавления иpopFrontдля извлечения), дек работает по принципу LIFO (последним пришел - первым ушел). - Очередь (Queue): Если вставлять элементы в один конец, а извлекать с другого (например,
pushBackиpopFront), структура ведет себя как FIFO (первым пришел - первым ушел).
Сфера применения: Деки используются во многих алгоритмических задачах. Наиболее известные примеры:
- Поддержание скользящего окна максимума/минимума в массиве.
- Ведение истории переходов (вперед/назад) в браузере.
- Планировщики задач, где новые задачи помещаются в конец, но прерванные или срочные задачи могут быть возвращены в начало (алгоритмы work-stealing).
Почему на сцене массив, а в примерах кода список. Дек - это набор
операций, а не конкретное устройство памяти, и собрать его можно двумя способами.
В визуализации выше взят массив: у него видны индексы, и хорошо заметно, что два
указателя расходятся от середины в разные стороны. В примерах кода ниже взят
двусвязный список: он не упирается в границы выделенного куска памяти и растет
с обоих концов сколько угодно. Оценки O(1) одинаковы в обоих случаях - и там,
и там работа идет только с концами. Промышленные реализации (std::deque
в C++, collections.deque в Python) устроены как компромисс: цепочка
небольших массивов-блоков.
Синонимы названия: Двусторонняя очередь, Дэк, Deque, Double-Ended Queue.
Сложность
Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
Если дек реализован эффективно (на базе связного списка с указателями на голову и хвост или на базе кольцевого буфера), все его операции выполняются за константное время.
По времени
| Операция | Время | Комментарий |
|---|---|---|
| Добавление в начало (pushFront) | O(1) | Обновление указателя начала и запись значения. |
| Добавление в конец (pushBack) | O(1) | Обновление указателя конца и запись значения. |
| Удаление из начала (popFront) | O(1) | Чтение значения и сдвиг указателя начала. |
| Удаление с конца (popBack) | O(1) | Чтение значения и сдвиг указателя конца. |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Затраты памяти | O(n) | Требуется память для хранения самих элементов (в узлах списка или массиве). |
Свойства
| Свойство | Значение | Комментарий |
|---|---|---|
| Доступ к концам | O(1) | Мгновенный доступ как к первому, так и к последнему элементу. |
| Доступ в середину | O(n) | Стандартный дек не предоставляет быстрого доступа к произвольному индексу по O(1) (кроме реализаций на массивах). |
| Универсальность | Стек/Очередь | Дек способен заменить любую из этих базовых структур, в зависимости от того, какие методы вы вызываете. |
Примеры реализации: Дек (Deque)
Код на C
#include <stdio.h>
#include <stdlib.h> // malloc, free, NULL
// Узел двусвязного списка
typedef struct Node {
int data; // Хранимое значение
struct Node* prev; // Указатель на предыдущий узел
struct Node* next; // Указатель на следующий узел
} Node;
// Структура самого дека
typedef struct {
Node* head; // Указатель на первый элемент
Node* tail; // Указатель на последний элемент
int count; // Текущее количество элементов
} Deque;
// Инициализация пустого дека
void init(Deque* dq) {
dq->head = NULL;
dq->tail = NULL;
dq->count = 0;
}
// Вспомогательная функция: создание нового узла
Node* createNode(int val) {
Node* n = (Node*)malloc(sizeof(Node));
n->data = val;
n->prev = n->next = NULL;
return n;
}
// Вставка элемента в начало дека (pushFront)
void pushFront(Deque* dq, int val) {
Node* n = createNode(val); // Создаем узел
if (dq->count == 0) {
// Если дек пуст, новый узел становится и головой, и хвостом
dq->head = dq->tail = n;
} else {
// Связываем новый узел с текущей головой
n->next = dq->head;
dq->head->prev = n;
dq->head = n; // Сдвигаем указатель головы на новый узел
}
dq->count++;
}
// Вставка элемента в конец дека (pushBack)
void pushBack(Deque* dq, int val) {
Node* n = createNode(val); // Создаем узел
if (dq->count == 0) {
// Если дек пуст, новый узел становится и головой, и хвостом
dq->head = dq->tail = n;
} else {
// Связываем новый узел с текущим хвостом
n->prev = dq->tail;
dq->tail->next = n;
dq->tail = n; // Сдвигаем указатель хвоста на новый узел
}
dq->count++;
}
// Удаление элемента из начала дека (popFront)
int popFront(Deque* dq) {
if (dq->count == 0) return -1; // Защита от извлечения из пустого дека
Node* temp = dq->head; // Запоминаем текущую голову
int val = temp->data; // Сохраняем значение
dq->head = temp->next; // Сдвигаем голову на следующий элемент
if (dq->head != NULL) {
dq->head->prev = NULL; // Отвязываем новую голову от удаленного узла
} else {
dq->tail = NULL; // Если дек опустел, обнуляем и хвост
}
free(temp); // Освобождаем память
dq->count--;
return val;
}
// Удаление элемента с конца дека (popBack)
int popBack(Deque* dq) {
if (dq->count == 0) return -1; // Защита от извлечения из пустого дека
Node* temp = dq->tail; // Запоминаем текущий хвост
int val = temp->data; // Сохраняем значение
dq->tail = temp->prev; // Сдвигаем хвост на предыдущий элемент
if (dq->tail != NULL) {
dq->tail->next = NULL; // Отвязываем новый хвост от удаленного узла
} else {
dq->head = NULL; // Если дек опустел, обнуляем и голову
}
free(temp); // Освобождаем память
dq->count--;
return val;
}Код на Python
# В Python уже есть встроенный оптимизированный дек, реализованный на C.
# Он работает намного быстрее списков, когда нужны операции с двух концов.
from collections import deque
# Инициализация пустого дека
dq = deque()
# --- ДОБАВЛЕНИЕ ЭЛЕМЕНТОВ ---
dq.append(10) # Вставка в конец (pushBack). Результат: [10]
dq.appendleft(20) # Вставка в начало (pushFront). Результат: [20, 10]
# --- УДАЛЕНИЕ ЭЛЕМЕНТОВ ---
val1 = dq.pop() # Удаление с конца (popBack). Возвращает 10.
val2 = dq.popleft() # Удаление из начала (popFront). Возвращает 20.
# -------------------------------------------------------------
# Реализация "с нуля" на базе двусвязного списка (для понимания)
# -------------------------------------------------------------
class Node:
def __init__(self, val):
self.data = val
self.prev = None # Ссылка на предыдущий узел
self.next = None # Ссылка на следующий узел
class Deque:
def __init__(self):
self.head = None # Указатель на начало
self.tail = None # Указатель на конец
self.count = 0 # Количество элементов
def push_front(self, val):
n = Node(val)
if self.count == 0:
self.head = self.tail = n
else:
n.next = self.head
self.head.prev = n
self.head = n
self.count += 1
def push_back(self, val):
n = Node(val)
if self.count == 0:
self.head = self.tail = n
else:
n.prev = self.tail
self.tail.next = n
self.tail = n
self.count += 1
def pop_front(self):
if self.count == 0: return None
val = self.head.data
self.head = self.head.next
if self.head:
self.head.prev = None
else:
self.tail = None # Дек полностью опустел
self.count -= 1
return val
def pop_back(self):
if self.count == 0: return None
val = self.tail.data
self.tail = self.tail.prev
if self.tail:
self.tail.next = None
else:
self.head = None # Дек полностью опустел
self.count -= 1
return valКод на JavaScript
// Узел двусвязного списка
class Node {
constructor(val) {
this.data = val; // Значение элемента
this.prev = null; // Ссылка на предыдущий узел
this.next = null; // Ссылка на следующий узел
}
}
// Реализация дека на основе двусвязного списка (чтобы операции были O(1))
class Deque {
constructor() {
this.head = null; // Начало дека
this.tail = null; // Конец дека
this.count = 0; // Количество элементов
}
// Вставка элемента в начало
pushFront(val) {
const n = new Node(val);
if (this.count === 0) {
// Если дек пуст, элемент становится единственным
this.head = this.tail = n;
} else {
n.next = this.head;
this.head.prev = n;
this.head = n; // Смещаем голову
}
this.count++;
}
// Вставка элемента в конец
pushBack(val) {
const n = new Node(val);
if (this.count === 0) {
// Если дек пуст, элемент становится единственным
this.head = this.tail = n;
} else {
n.prev = this.tail;
this.tail.next = n;
this.tail = n; // Смещаем хвост
}
this.count++;
}
// Удаление элемента из начала
popFront() {
if (this.count === 0) return null; // Защита от пустого дека
const val = this.head.data;
this.head = this.head.next; // Смещаем голову вперед
if (this.head) {
this.head.prev = null; // Отвязываем удаленный элемент
} else {
this.tail = null; // Если элементов больше нет, зануляем и хвост
}
this.count--;
return val;
}
// Удаление элемента с конца
popBack() {
if (this.count === 0) return null; // Защита от пустого дека
const val = this.tail.data;
this.tail = this.tail.prev; // Смещаем хвост назад
if (this.tail) {
this.tail.next = null; // Отвязываем удаленный элемент
} else {
this.head = null; // Если элементов больше нет, зануляем и голову
}
this.count--;
return val;
}
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про дек и его применение - с подробной теорией, задачами и проверочными вопросами.