Что хотят услышать интервьюеры:

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

Определение:

Стек — структура данных, в которой добавление и удаление элементов происходят с одного конца, называемого вершиной стека.
Основной принцип: LIFO (Last In, First Out) — «последним пришёл, первым вышел».

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

Разница между ними в порядке обработки элементов и в том, с какой стороны выполняются операции вставки и удаления.

Пример использования:

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

from collections import deque

# Стек
stack = []
stack.append("A")
stack.append("B")
stack.append("C")
print(stack.pop())  # C
print(stack.pop())  # B

# Очередь
queue = deque()
queue.append("A")
queue.append("B")
queue.append("C")
print(queue.popleft())  # A
print(queue.popleft())  # B

Пояснение кода:

В примере стек реализован на обычном списке Python.
append() добавляет элемент в конец списка, а pop() удаляет его тоже с конца, поэтому получаем поведение LIFO.

Очередь реализована через deque из collections, потому что для очереди важно эффективно удалять элементы из начала.
append() добавляет элемент в конец, а popleft() забирает элемент из начала, поэтому получается FIFO.

Пошагово:

В стек добавляются "A", "B", "C".
При pop() первым извлекается "C", затем "B".
В очередь добавляются "A", "B", "C".
При popleft() первым извлекается "A", затем "B".

Ключевые моменты:

Стек — это LIFO, очередь — FIFO.
У стека и очередь различается порядок извлечения элементов.
Для стека обычно используют append() и pop() с одного конца.
Для очереди в Python удобно использовать collections.deque.
Стек часто применяют для рекурсии, отмены действий, парсинга выражений.
Очередь часто применяют для очередей задач, буферов, BFS-обхода графа.

Объясните различия между структурой данных стек и структурой данных очередь