Что такое стек и очередь: LIFO, FIFO и операции

Что такое стек и очередь? Какие операции они поддерживают?

Стек работает по принципу LIFO: последним пришёл — первым вышел. Очередь работает по принципу FIFO: первым пришёл — первым вышел. Базовые операции добавления, просмотра и извлечения элемента обычно выполняются за O(1) при корректной реализации.

Подробный ответ

Что такое стек

Стек — структура данных с принципом LIFO, Last In, First Out. Последний добавленный элемент будет извлечён первым. Простой пример — стопка тарелок.

Операции стека

push — добавить элемент на вершину;
pop — извлечь верхний элемент;
peek или top — посмотреть верхний элемент без удаления;
is_empty — проверить, пуст ли стек.

stack = []
stack.append('first')
stack.append('second')

last = stack.pop()
print(last)

В Python список обычно используют как стек: append() соответствует push, а pop() без аргумента — pop.

Что такое очередь

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

Операции очереди

enqueue — добавить элемент в конец очереди;
dequeue — извлечь элемент из начала;
front или peek — посмотреть первый элемент;
is_empty — проверить, пуста ли очередь.

from collections import deque

queue = deque()
queue.append('first')
queue.append('second')

first = queue.popleft()
print(first)

Для очереди в Python лучше использовать collections.deque: операции append() и popleft() выполняются эффективно. Удаление первого элемента из обычного списка через pop(0) имеет сложность O(n).

Применение

стек — отмена действий, проверка скобок, обход графа в глубину, стек вызовов функций;
очередь — фоновые задачи, обработка сообщений, обход графа в ширину, очереди запросов.

Как ответить на собеседовании

Стек работает по LIFO: push, pop и peek обычно O(1). Очередь работает по FIFO: enqueue добавляет в конец, dequeue извлекает из начала. В Python для очереди использую deque, потому что popleft() работает за O(1).