tgoop.com/csharpproglib/5890
Create:
Last Update:
Last Update:
Проблема: стандартные массивы для очереди могут привести к необходимости дорогостоящих операций сдвига элементов при удалении.
Решение: в книге 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;
}
}
Преимущества:
— Нет затрат на сдвиг элементов
— Высокая производительность при операциях добавления и удаления
— Универсальная реализация для любых типов данных