Что такое стек и очередь? Чем они различаются?

Стек (LIFO — Last In First Out): элементы добавляются и удаляются с одного конца — «вершины». Как стопка тарелок: последняя положенная — первая снятая.

Очередь (FIFO — First In First Out): добавление в конец, удаление из начала. Как очередь в магазине.

На Python:

# Стек на основе списка
stack = []
stack.append(1)   # push
stack.append(2)
stack.append(3)
print(stack.pop())  # 3 — последний
print(stack.pop())  # 2

# Очередь — лучше через deque (для O(1))
from collections import deque
queue = deque()
queue.append(1)        # enqueue
queue.append(2)
queue.append(3)
print(queue.popleft())  # 1 — первый
print(queue.popleft())  # 2

Применения:

• Стек: проверка скобок, отмена действий (Ctrl+Z), вызовы функций (call stack), обход графа в глубину.
• Очередь: задачи на печать в принтере, обработка событий, BFS, межпроцессное взаимодействие.

list.pop(0) для очереди работает за $O(n)$ — нужно deque.