Основы работы с очередями: от новичка до продвинутого

30 дней алгоритмов: от новичка до продвинутого, 10-й день: Очереди

В предыдущем уроке мы рассмотрели стеки, которые работают на основе принципа последним пришёл — первым вышел (LIFO). Сегодня мы узнаем об очередях, которые работают на основе принципа первым пришёл — первым вышел (FIFO).

Что такое очереди?

Очередь — это линейная структура данных, которая позволяет добавлять элементы в один конец (называемый тылом) и удалять их из другого конца (называемого фронтом).

Операции над очередями

Основными операциями, выполняемыми над очередями, являются:

• enqueue: Добавляет элемент в тыл очереди.
• dequeue: Удаляет элемент из фронта очереди.
• peek: Возвращает элемент из фронта очереди, не удаляя его.

Реализация очереди с помощью массива

Очереди можно реализовать с помощью массива следующим образом:

class Queue:
  def __init__(self):
    self.items = []

  def enqueue(self, item):
    self.items.append(item)

  def dequeue(self):
    return self.items.pop(0)

  def peek(self):
    return self.items[0]

Реализация очереди с помощью связанного списка

Очереди также можно реализовать с помощью связанного списка следующим образом:

class Queue:
  def __init__(self):
    self.front = None
    self.rear = None

  def enqueue(self, item):
    new_node = Node(item)
    if self.front is None:
      self.front = new_node
    else:
      self.rear.next = new_node
    self.rear = new_node

  def dequeue(self):
    if self.front is None:
      return None
    else:
      item = self.front.data
      self.front = self.front.next
      if self.front is None:
        self.rear = None
      return item

  def peek(self):
    if self.front is None:
      return None
    else:
      return self.front.data

Применение очередей

Очереди имеют множество применений, в том числе:

• Системы планирования задач
• Очереди сообщений
• Буферы ввода-вывода
• Моделирование симуляции

Вывод

Очереди — это важная структура данных, которая используется в различных приложениях. Понимание их работы и реализации необходимо для эффективного написания программ.