Можете объяснить структуры стек (stack) и очередь (queue) и где они используются?

Где каждая структура может быть наиболее подходящим выбором?

Подсказки:

• Подумайте о природе стека LIFO (Last In, First Out) и о том, как это может применяться к вызовам функций или обработке задач в определенном порядке.
• Рассмотрите поведение очереди FIFO (First In, First Out) и как это может быть полезно для планирования задач или обработки сообщений.
• Примеры из реальной жизни могут включать управление историей браузера (стек) или системы планирования задач (очередь).

Выше ожиданий:

• Понимание фреймов стека в выполнении вызовов и рекурсии.
• Реализация функций отмены/повторной обработки с использованием стека.
• Системы брокеров сообщений, использующие очереди для коммуникаций между сервисами.
• Очереди с приоритетами для планирования задач с разными уровнями срочности.

Стек следует принципу LIFO (Last-In, First-Out), где последний добавленный элемент является первым удаленным. Можно представить как стопку тарелок — вы можете взять только верхнюю.

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

• push: Добавить элемент наверх
• pop: Удалить верхний элемент
• peek: Просмотреть верхний элемент без удаления

Где используется стек

1. Управление вызовами функций

   • Каждый вызов функции создаёт фрейм на стеке, содержащий локальные переменные и адрес возврата.
   • Когда функция завершается, её фрейм удаляется со стека.
   • Рекурсия сильно зависит от стека вызовов:

   Стек вызовов (снизу → вверх):
   main() → factorial(3) → factorial(2) → factorial(1)
   

2. Функциональность отмены/повтор (не очевидный пример)

   • Каждое действие пользователя добавляется в стек отмены.
   • Когда пользователь нажимает «отменить», действие извлекается и добавляется в стек повтора.

3. История браузера

   • Каждая посещённая страница добавляется в стек истории.
   • При нажатии «назад» текущая страница извлекается.

4. Вычисление выражений (тяжелый пример)

   • Используется в компиляторах и калькуляторах для вычисления выражений.

   Выражение: 2 + 3 * 4
   Операции со стеком: push 2, push 3, push 4, pop дважды для умножения, pop для сложения
   

Очереди - FIFO (First-In, First-Out)

Очереди следуют принципу FIFO (First-In, First-Out), где первый добавленный элемент является первым удалённым. Как люди, стоящие в очереди.

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

• enqueue: Добавить элемент в конец
• dequeue: Удалить элемент из начала
• peek: Просмотреть первый элемент без удаления

Приложения в реальном мире

1. Планирование задач

   • Задачи обрабатываются в порядке их поступления.
   • Это предотвращает длительное ожидание для более старых запросов.

   Очередь задач: [Задача1] → [Задача2] → [Задача3] → ...
   

2. Брокеры сообщений

   • Коммунникации между сервисами в архитектурах микросервисов.
   • Производители (producers) добавляет сообщения в очередь, потребитель (consumer) обрабатывает их асинхронно.
   • Примеры: RabbitMQ, Kafka, AWS SQS

3. Поиск в ширину

   • Исследование узлов по уровням в графах/деревьях.

       A
      / \
     B   C
    / \
   D   E
   
   Обработка очереди: A, B, C, D, E
   

4. Очереди с приоритетами

   • Расширение обычных очередей, где элементы имеют приоритет.
   • Используются в системах реального времени, где некоторые задачи более срочные.
   • Маршрутизация сетевых пакетов с QoS (Качество обслуживания).

Выбор между стеками и очередями

Выберите стек, когда:

• Нужно обработать элементы в обратном порядке
• Нужно отслеживать состояние для отката

Выберите очередь, когда:

• Порядок поступления важен
• Нужна справедливая обработка (предотвращение голодания)
• Вы реализуете алгоритмы поиска в ширину
• Вам нужно буферизовать или декомпозировать компоненты