В мире структур данных очереди и связанные списки — это две фундаментальные концепции. Очереди следуют принципу «первым пришел — первым обслужен» (FIFO), а связанные списки представляют собой динамическую структуру данных, которая позволяет эффективно вставлять и удалять элементы. Объединив эти две концепции, мы можем реализовать очередь, используя связанный список. В этой статье мы рассмотрим упрощенную реализацию очереди с использованием связанного списка и обсудим различные методы, связанные с ним.

Реализация:
Чтобы реализовать очередь со связанным списком, нам нужно создать класс узла и класс очереди. Каждый узел будет содержать значение и ссылку на следующий узел. Класс очереди будет отслеживать первый и последний узел в связанном списке.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
class Queue:
    def __init__(self):
        self.first = None
        self.last = None

Постановка элемента в очередь:
Чтобы поставить элемент в очередь, мы создаем новый узел с заданным значением и обновляем следующую ссылку последнего узла, чтобы она указывала на новый узел. Если очередь пуста, мы обновляем как первую, так и последнюю ссылку на новый узел.

def enqueue(self, value):
    new_node = Node(value)
    if self.last is None:
        self.first = new_node
        self.last = new_node
    else:
        self.last.next = new_node
        self.last = new_node

Извлечение элемента из очереди.
Чтобы исключить элемент из очереди, мы удаляем первый узел из связанного списка и обновляем первую ссылку, чтобы она указывала на следующий узел. Если после удаления из очереди очередь становится пустой, мы также обновляем последнюю ссылку на None.

def dequeue(self):
    if self.first is None:
        raise Exception("Queue is empty!")
    dequeued_value = self.first.value
    self.first = self.first.next
    if self.first is None:
        self.last = None
    return dequeued_value

Другие методы.
Помимо постановки в очередь и удаления из нее, очередь, реализованная с помощью связанного списка, может иметь и другие полезные методы. Вот несколько примеров:

1. is_empty(): проверяет, пуста ли очередь, проверяя, является ли первый узел пустым.
2. peek(): возвращает значение первого узла, не удаляя его из очереди.
3. size(): возвращает количество элементов в очереди путем обхода связанного списка и подсчета узлов.