Стек и очередь как структуры данных
💻 Информатика · 9 класс
Структуры данных стек и очередь
Структура данных — это способ организации данных в памяти, который определяет, как к ним обращаться. Стек и очередь — две простейшие и важнейшие структуры. Они отличаются лишь порядком, в котором элементы добавляются и извлекаются, но именно этот порядок делает их незаменимыми во множестве алгоритмов.
Стек: принцип LIFO
Стек работает по принципу LIFO (last in — first out, «последним пришёл — первым ушёл»). Представьте стопку тарелок: новую тарелку кладут наверх, и берут тоже сверху. Чтобы достать нижнюю, придётся снять все, что лежит над ней.
Основные операции стека:
- push — положить элемент на вершину;
- pop — снять элемент с вершины;
- peek — посмотреть верхний элемент, не снимая его.
Очередь: принцип FIFO
Очередь работает по принципу FIFO (first in — first out, «первым пришёл — первым ушёл»). Это обычная очередь в магазине: кто встал раньше, того и обслужат раньше. Новые элементы добавляются в конец, а извлекаются из начала.
Основные операции очереди:
- enqueue — добавить элемент в конец;
- dequeue — извлечь элемент из начала.
| Свойство | Стек | Очередь |
|---|---|---|
| Принцип | LIFO | FIFO |
| Добавление | на вершину | в конец |
| Извлечение | с вершины | из начала |
| Аналогия | стопка тарелок | очередь людей |
Пример работы стека
Проследим состояние стека при последовательности операций. Слева перечисляются действия, справа — содержимое стека (вершина справа):
push(5) -> [5]
push(8) -> [5, 8]
push(2) -> [5, 8, 2]
pop() -> [5, 8] (вернул 2)
push(9) -> [5, 8, 9]
pop() -> [5, 8] (вернул 9)Где применяются
Стек используется для хранения адресов возврата при вызове функций (стек вызовов), для проверки правильности расстановки скобок, для отмены действий (Ctrl+Z) и при обходе графов в глубину. Когда программа вызывает одну функцию из другой, адреса возврата складываются именно в стек, поэтому управление всегда возвращается туда, откуда ушло.
Очередь нужна для обработки задач в порядке поступления: печать документов, обработка запросов сервера, обход графа в ширину. Принтер печатает файлы в том порядке, в каком их отправили, а сервер отвечает на запросы по очереди — это естественные примеры структуры FIFO. Обе структуры можно хранить в массиве, отслеживая положение вершины или начала и конца.
Частые ошибки. Не путайте порядок: из стека выходит последний добавленный, из очереди — первый. Перед операцией pop или dequeue убедитесь, что структура не пуста, иначе возникнет ошибка. Помните, что в стеке доступна только вершина, а не произвольный элемент.
Кратко о главном
- Стек — структура LIFO, доступ только к вершине.
- Очередь — структура FIFO, добавление в конец, извлечение из начала.
- Операции стека: push, pop, peek.
- Операции очереди: enqueue, dequeue.
- Применяются в обходах графов, обработке задач, отмене действий.