Что вы знаете о структуре данных 'очередь'?

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

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

• enqueue (помещение в очередь): добавление элемента в конец очереди.
• dequeue (извлечение из очереди): удаление элемента из начала очереди.
• peek (или front): получение значения элемента в начале очереди без его удаления.
• is_empty: проверка, пуста ли очередь.
• size: получение текущего количества элементов в очереди.

Реализации:

• Список (List): Неэффективно для больших очередей из-за O(n) при удалении с начала (смещении элементов).

  # Добавление
  queue = []
  queue.append(item)
  
  # Удаление
  if queue:
      item = queue.pop(0) # O(n) операция
  

• collections.deque: Двусвязный список, оптимизированный для быстрого добавления/удаления с обоих концов. O(1) для enqueue и dequeue.

  import collections
  
  # Создание
  queue = collections.deque()
  
  # Добавление
  queue.append(item) # O(1)
  
  # Удаление
  if queue:
      item = queue.popleft() # O(1)
  

• queue.Queue: Потокобезопасная реализация для многопоточных приложений. Использует collections.deque внутри. Методы put() и get() потокобезопасны.

  import queue
  
  # Создание
  q = queue.Queue()
  
  # Помещение (можно использовать таймаут)
  q.put(item)
  
  # Получение (можно использовать таймаут или блокировку)
  try:
      item = q.get(block=False) # не блокирующий вызов
  except queue.Empty:
      pass # Очередь пуста
      
  # Сообщить об успешной обработке элемента
  q.task_done() 
  

Применение:

• Обработка запросов сервером.
• Буферизация данных.
• Реализация алгоритмов (например, поиск в ширину - BFS).
• Потокобезопасное взаимодействие между потоками (с помощью queue.Queue).