Этот вопрос проверяет понимание базовых структур данных: стека и очереди, их свойств и отличий.
Стек — это структура данных, работающая по принципу LIFO (последним пришёл — первым ушёл), где элементы добавляются и удаляются с одного конца. Очередь работает по принципу FIFO (первым пришёл — первым ушёл), где элементы добавляются с одного конца, а удаляются с другого. Обе используются для управления порядком обработки элементов.
Стек и очередь являются фундаментальными структурами данных в программировании.
Стек (Stack):
Принцип: LIFO (Last In, First Out).
Операции:
push — добавление элемента на вершину стека.
pop — удаление и возврат верхнего элемента.
peek — просмотр верхнего элемента без удаления.
Использование:
Управление вызовами функций (call stack).
Отмена действий (undo functionality).
Парсинг выражений (например, обратная польская запись).
Пример на Python:
stack = []
stack.push(1) # [1]
stack.push(2) # [1, 2]
top = stack.pop() # возвращает 2, stack = [1]Очередь (Queue):
Принцип: FIFO (First In, First Out).
Операции:
enqueue — добавление элемента в конец очереди.
dequeue — удаление и возврат первого элемента.
peek — просмотр первого элемента без удаления.
Использование:
Обработка задач в порядке поступления (например, print queue).
Breadth-first search (BFS) в графах.
Буферизация данных в сетях.
Пример на Python:
from collections import deque
queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
first = queue.popleft() # возвращает 1, queue = [2]