Стек, очередь и дек

Линейные структуры данных

Стек, очередь и дек — это линейные структуры данных, которые отличаются правилами добавления и извлечения элементов. Они хранят набор значений, но дают доступ только к концам последовательности, а не к произвольному элементу.

Стек

Стек работает по принципу LIFO — «последним пришёл, первым ушёл». Элементы добавляют и удаляют только с одного конца, который называют вершиной. Аналогия — стопка тарелок: берут верхнюю. Основные операции:

• push — положить элемент на вершину;
• pop — снять элемент с вершины;
• top — посмотреть верхний элемент, не снимая.

Стек применяют для вызова функций, проверки скобок, перевода выражений в обратную польскую запись и обхода в глубину.

Очередь

Очередь работает по принципу FIFO — «первым пришёл, первым ушёл». Элементы добавляют в конец, а извлекают из начала, как живая очередь в магазине. Операции enqueue (добавить в конец) и dequeue (взять из начала). Очередь используют при обходе в ширину и в буферах данных.

Дек

Дек (двусторонняя очередь) — структура, в которую можно добавлять и из которой можно извлекать элементы с обоих концов. Дек обобщает и стек, и очередь.

Структура	Принцип	Где доступ
Стек	LIFO	один конец
Очередь	FIFO	оба конца, по одному
Дек	смешанный	оба конца

Разбор примера

Проследим работу стека для проверки скобок в выражении (a+b):

встретили '(' -> push, стек: [ ( ] встретили ')' -> pop, стек: [ ] стек пуст -> скобки сбалансированы

Если в конце стек не пуст или встретилась закрывающая скобка при пустом стеке — баланс нарушен.

Как хранят эти структуры

Стек, очередь и дек можно реализовать на основе массива или связного списка. В массиве хранят данные и индексы концов; при выходе за границу массив увеличивают. В связном списке каждый элемент хранит значение и ссылку на следующий, поэтому добавление и удаление с конца выполняются быстро и без перевыделения памяти. Важно, что у всех этих структур операции добавления и извлечения выполняются за постоянное время, не зависящее от числа элементов.

Кольцевая очередь

Чтобы массив под очередь не «уезжал» вправо при многократном добавлении и удалении, применяют кольцевую очередь: индексы начала и конца, дойдя до края массива, переходят обратно в его начало. Так массив используется по кругу и память расходуется экономно. Это типичное решение для буфера, в который данные поступают и из которого считываются непрерывно, например при передаче по сети.

Частые ошибки. Пытаются извлечь элемент из пустого стека или очереди — это ошибка переполнения снизу. Путают концы добавления и удаления в очереди. Думают, что в стеке можно обратиться к нижнему элементу напрямую — нельзя, только к вершине.

Кратко о главном

• Стек работает по правилу LIFO: доступ только к вершине.
• Очередь работает по правилу FIFO: вход в конец, выход из начала.
• Дек допускает операции с обоих концов.
• Стек нужен для рекурсии и проверки скобок, очередь — для обхода в ширину.
• Извлечение из пустой структуры — типичная ошибка.