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

Проблема: стандартные массивы для очереди могут привести к необходимости дорогостоящих операций сдвига элементов при удалении.

Решение: в книге Algorithms and Data Structures for OOP With C# автор предлагает реализовать очередь на основе связного списка, что позволяет эффективно добавлять элементы в конец и удалять с начала за O(1).

Пример кода:

public class Node<T>
{
    public T Data;
    public Node<T> Next;

    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

public class QueueLinkedList<T>
{
    private Node<T> front, rear;

    public QueueLinkedList()
    {
        front = rear = null;
    }

    public void Enqueue(T item)
    {
        var newNode = new Node<T>(item);
        if (rear == null)
        {
            front = rear = newNode;
            return;
        }
        rear.Next = newNode;
        rear = newNode;
    }

    public T Dequeue()
    {
        if (front == null)
            throw new InvalidOperationException("Queue is empty.");

        var data = front.Data;
        front = front.Next;

        if (front == null)
            rear = null;

        return data;
    }
}

Преимущества:
— Нет затрат на сдвиг элементов
— Высокая производительность при операциях добавления и удаления
— Универсальная реализация для любых типов данных

➡️ Лучшее из мира IT-книг — у нас в @progbook