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

Что такое структура данных

Структура данных — это способ организовать данные так, чтобы с ними было удобно работать. СписокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. вы уже знаете. Но иногда нужны особые правила доступа: «брать только последнее добавленное» или «только самое первое». На таких правилах построены стек и очередь.

Стек — стопка тарелок (LIFO)

Представьте стопку тарелок: вы кладёте тарелку сверху и берёте тоже сверху. Последняя добавленная уходит первой. Это правило называется LIFO — Last In, First Out («последним пришёл — первым ушёл»). Две операции стека: push (положить наверх) и pop (снять с верха).

Обычный список Python — готовый стек: append() кладёт элемент в конец (вершину), а pop() без аргументаЗначение, которое передаётся функции при вызове. Внутри функции оно доступно как параметр. снимает последний. Обе операции очень быстрые.

Где применяется стек

Стек незаменим там, где нужно «откатываться назад»: кнопка Undo в редакторах, история браузера, проверка парных скобок, вызовы функций (тот самый стек вызовов из рекурсииПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились.). Когда нужно вернуться к последнему действию — это стек.

Очередь — очередь в магазине (FIFO)

Очередь работает иначе: кто встал первым, того и обслужат первым. Это FIFO — First In, First Out. Добавляем в конец (enqueue), берём из начала (dequeue).

Стек выдаст [3, 2, 1] (последний вошёл — первым вышел), а очередь — [1, 2, 3] (порядок сохранён). Это главное различие LIFO и FIFO.

⚠️ Частые ошибки новичков

Ошибка. Вызвать pop() у пустого стека — будет IndexError. Всегда проверяйте, что структура не пуста, перед извлечением. Запустите код и почините: оберните извлечение в проверку if stack:.