Конспект раздела: массивы, списки и абстракции

Карта раздела

Раздел отвечает на вопрос «как описать структуру данных, чтобы выбрать её с умом, и почему одна и та же очередь бывает дешёвой и дорогой». Три главы - три слоя.

абстрактный тип   ->  структура = операции + контракт + СТОИМОСТЬ (не как хранится)
     |
массив и список   ->  две зеркальные реализации: индекс дёшев ⇄ правка на месте дешева
     |
стек/очередь/дека ->  дисциплины LIFO/FIFO и как сделать очередь за O(1)

Абстрактный тип против реализации

Абстрактный тип (АТД) - набор операций и их контракт, без слова о хранении. Реализация - представление в памяти плюс код операций; одной абстракции отвечает много реализаций. Стоимость операции - часть контракта: ответы у реализаций одинаковые, цена разная, по ней и выбирают. Обещанную цену держит инвариант представления (условие, истинное между операциями); нарушишь извне - рухнут и цена, и корректность, поэтому внутренности прячут. Вид цены пишут честно: «O(1) амортизированно» ≠ «O(1) всегда».

Таблица: операция - массив - список - дека

Главный итог раздела. Строки - операции, столбцы - реализации последовательности.

операция	массив (динамич.)	связный список	дека
взять/поставить `i`-й	`O(1)`	`O(n)`	`O(n)`
добавить/снять в конце	`O(1)` аморт.	`O(1)`	`O(1)`
добавить/снять в начале	`O(n)`	`O(1)`	`O(1)`
вставить/удалить в середине (место известно)	`O(n)`	`O(1)`	`O(n)`
найти по значению	`O(n)`	`O(n)`	`O(n)`
принадлежит? (нужно множество)	`O(n)`	`O(n)`	-

Массив силён в индексации, связный список - в правках на месте, дека - на обоих концах. Проверка «принадлежит?» дёшева только у множества (O(1) в среднем, на хеш-таблице - её разберём дальше) - это отдельный АТД, не последовательность.

Дерево решений: что под какую задачу

Что нужно чаще всего	Бери	Почему
доступ по индексу, проход подряд, добавление в конец	массив (`list`)	`O(1)`-индекс + локальность памяти
частые правки не с края по известному месту	связный список	правка на месте `O(1)`, сдвига нет
добавлять/снимать с обоих концов	дека (`deque`)	`O(1)` слева и справа
порядок LIFO (последний-первым)	стек на `list`	`push`/`pop` с конца, `O(1)`
порядок FIFO (первый-первым)	очередь (`deque`/кольцо/2 стека)	`O(1)`, но НЕ `list.pop(0)`
частые проверки «есть ли элемент?»	множество (`set`)	`O(1)` вместо `O(n)` перебора

Как сделать очередь за O(1)

Наивно на массиве dequeue через pop(0) - O(n²) на серии (сдвиг головы). Беда не в FIFO, а в реализации головы. Два лечения:

реализация	цена dequeue	ёмкость
кольцевой буфер	`O(1)` в худшем случае	фиксирована (нужно удвоение)
два стека (`in`/`out`)	`O(1)` амортизированно	растёт сама

Кольцевой буфер двигает индексы head/tail (обёртывание % size), а не данные; count отличает пустую очередь от полной. Два стека переливают in в out только при пустом out - каждый элемент льётся раз за жизнь, O(1) амортизированно (потенциал Φ = размер in, та же амортизация, что у динамического массива).

Сквозная нить - «пользуйся сильной стороной»

Весь раздел про одно: у структуры есть дешёвые операции и дорогие, и алгоритм надо строить на дешёвых. Уникальные - через set (O(1)-принадлежность), а не перебор списка (O(n²)). Обратный порядок - append + reverse в конец (O(n)), а не insert(0) в начало (O(n²)). Очередь - без pop(0) (O(n²)), а два стека или кольцо (O(n)). Одна абстрактная операция в правильной и неправильной обёртке - и линия против квадрата.

Связи с остальным курсом

Амортизация (прошлый раздел) заработала здесь на практике: append, стек, очередь на двух стеках - все их O(1) доказаны потенциалом.

Сортировки (следующий раздел) живут на массивах: сортировка на месте, устойчивость, слияние - всё опирается на профиль операций массива.

Хеш-таблицы (дальше) стоят за множеством и словарём с их O(1)-принадлежностью, которую мы здесь только использовали как готовую.

Чек-лист: объясни своими словами

Чем абстрактный тип отличается от реализации и почему их разделяют.
Почему стоимость операции - часть контракта, а не деталь.
Что такое инвариант представления и на что он опирает цену.
Почему индексация массива O(1), а вставка в середину O(n).
Почему у связного списка всё наоборот и когда его выбирают.
Что такое локальность памяти и почему массив часто быстрее, чем обещает асимптотика.
Чем стек (LIFO) отличается от очереди (FIFO).
Почему наивная очередь через pop(0) - O(n²).
Как кольцевой буфер даёт O(1) (индексы, обёртывание, count).
Почему очередь на двух стеках - O(1) амортизированно и при чём «перелив при пустом out».

Что дальше

Ты умеешь описать структуру абстрактно (операции + стоимость), выбрать реализацию по профилю и построить дешёвую очередь и стек. Это фундамент под всё остальное: следующий раздел - сортировки, они живут на массивах и опираются ровно на этот профиль операций.