В чем разница между структурой данных 'стек' и 'очередь'?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

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

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

Основные операции:

Операция	Стек (Stack)	Очередь (Queue)
Добавление	`push()` (обычно в конец)	`enqueue()` (обычно в конец)
Удаление	`pop()` (из конца)	`dequeue()` (из начала)
Просмотр	`peek()` или `top()` (элемент в конце)	`peek()` или `front()` (элемент в начале)

Применение:

Стек: вызовы функций (стек вызовов), синтаксический анализ, откат действий (undo).
Очередь: планирование задач, управление буфером (например, ввод-вывод), обход графа в ширину (BFS).

Реализация в Python:

Для стека можно использовать список, добавляя и удаляя элементы с конца:

# Стек с использованием списка
stack = []
stack.append('a') # push
stack.append('b') # push
item = stack.pop() # pop

Для очереди можно использовать collections.deque для эффективного добавления и удаления с обоих концов:

# Очередь с использованием collections.deque
from collections import deque
queue = deque()
queue.append('a') # enqueue
queue.append('b') # enqueue
item = queue.popleft() # dequeue