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

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

Стек

• Операции push и pop на вершине за O(1).
• Применения: стек вызовов, отмена операций, проверка скобок, итеративный DFS, разбор выражений.

Очередь

• enqueue в хвост, dequeue из головы — обе за O(1).
• Применения: BFS, буферы producer-consumer, планировщики задач.

Дека

Оба конца открыты: реализует и стек, и очередь; монотонная дека даёт минимум в скользящем окне за O(n) суммарно.

Варианты реализации

• На динамическом массиве: стек тривиален; очередь — кольцевой буфер, иначе dequeue станет O(n).
• На двусвязном списке: все операции O(1) без ресайзов, но с накладными расходами на узлы.
• Очередь на двух стеках: амортизированный O(1) на dequeue — популярная задача.

Коротко для собеседования

Стек отдаёт последний добавленный элемент, очередь — самый ранний, а дека умеет работать с обоими концами. На массиве очередь делают кольцевым буфером, иначе извлечение из головы станет O(n); если извлекать нужно по приоритету, а не по порядку прихода, берут кучу.