C# Queue, Stack, LinkedList ve PriorityQueue: Sırayla Çalışan Collection'lar

Sürüm notu: Bu yazıdaki kodlar C# 10 ve .NET 6 API'leriyle yazılmıştır; .NET 10 SDK ile derlenip denenmiştir.

Önce Tahmin Et

Kargo servisine siparişleri önceliğe göre vermek istiyoruz: aynı gün teslimat 0, ekspres 1, standart 3. Küçük sayı önce gider. .NET 6 ile gelen PriorityQueue'ya beş sipariş ekledik ve içindekileri foreach ile listeledik. Ekranda hangi sıra görünür?

PriorityQueue<string, int> shipping = new();
shipping.Enqueue("Order 1001 (standard)", 3);
shipping.Enqueue("Order 1002 (express)", 1);
shipping.Enqueue("Order 1003 (standard)", 3);
shipping.Enqueue("Order 1004 (same day)", 0);
shipping.Enqueue("Order 1005 (express)", 1);

foreach ((string order, int priority) in shipping.UnorderedItems)
{
    Console.WriteLine($"{priority} {order}");
}

UnorderedItems Neden Sırasız

0 Order 1004 (same day)
3 Order 1001 (standard)
3 Order 1003 (standard)
1 Order 1002 (express)
1 Order 1005 (express)

İlk satır doğru, gerisi karışık. Property'nin adı zaten uyarıyor: UnorderedItems. PriorityQueue içeride element'leri sıralı tutmaz; bir array üzerinde duran bir min-heap tutar. Heap'in tek sözü şudur: en küçük öncelik her zaman en üstte. Geri kalanı yalnızca "her ebeveyn çocuklarından küçük" kuralına uyar, tam bir sıralama değildir. UnorderedItems sana o array'i olduğu gibi gösterir.

Bir hastanenin acil servisini düşün. Triyaj hemşiresi bekleme salonundaki herkesi sıraya dizmez; sadece "şu an en acil kim?" sorusuna her an cevap verebilir. Sırayla işlemek istiyorsan Dequeue ile en üsttekini alırsın:

// shipping: yukarıdaki beş siparişlik queue
while (shipping.TryDequeue(out string? order, out int priority))
{
    Console.WriteLine($"{priority} {order}");
}

0 Order 1004 (same day)
1 Order 1005 (express)
1 Order 1002 (express)
3 Order 1003 (standard)
3 Order 1001 (standard)

Öncelikler artık doğru sırada. Ama eşit öncelikli siparişlere bak: 1005, ondan önce verilen 1002'nin önüne geçti, 1003 de 1001'in. PriorityQueue stable değildir; aynı önceliğe sahip element'lerin ekleme sırasını korumaz. Bunu nasıl düzelteceğimizi yazının sonunda göreceğiz. Önce bu ailenin daha basit iki üyesine bakalım.

Queue<T>: İlk Gelen İlk Çıkar

Queue<string> orders = new();
orders.Enqueue("Order 1001");
orders.Enqueue("Order 1002");
orders.Enqueue("Order 1003");

Console.WriteLine($"Next: {orders.Peek()}, waiting: {orders.Count}");

while (orders.TryDequeue(out string? order))
{
    Console.WriteLine($"Processing {order}");
}

orders.Dequeue(); // boş queue: InvalidOperationException

Next: Order 1001, waiting: 3
Processing Order 1001
Processing Order 1002
Processing Order 1003
Unhandled exception. System.InvalidOperationException: Queue empty.

Market kasasındaki sıra: ilk gelen ilk hizmet alır (FIFO, first in first out). Enqueue sona ekler, Dequeue baştan alır, Peek almadan bakar. Boş bir queue'da Dequeue ve Peek exception fırlatır; boş olabileceği her yerde TryDequeue ve TryPeek kullan.

Baştan almak List<T>'de RemoveAt(0) demek ve her seferinde bütün listeyi kaydırır. Queue<T> ise içerideki array'i dairesel kullanır: baş ve son için iki index tutar, element'leri yerinden oynatmaz. Hem Enqueue hem Dequeue O(1)'dir. Sipariş işleme, e-posta gönderme ya da bir web crawler'ın ziyaret edeceği adresler gibi "geldiği sırayla işle" ihtiyacının doğal cevabı budur.

Stack<T>: Son Gelen İlk Çıkar

Üst üste dizilmiş tabakları düşün; en son koyduğun tabağı ilk alırsın (LIFO, last in first out). Bu, geri alma (undo) özelliğinin ta kendisi:

List<string> cart = new();
Stack<string> history = new();

AddToCart("Dune");
AddToCart("Foundation");
AddToCart("1984");
Console.WriteLine($"Cart: {string.Join(", ", cart)}");

UndoLast();
UndoLast();
Console.WriteLine($"After two undos: {string.Join(", ", cart)}");

Stack<int> original = new(new[] { 1, 2, 3 });
Stack<int> copy = new(original);
Console.WriteLine($"Original: {string.Join(", ", original)} | copy: {string.Join(", ", copy)}");

void AddToCart(string title)
{
    cart.Add(title);
    history.Push(title);
}

void UndoLast()
{
    if (history.TryPop(out string? title))
    {
        cart.Remove(title);
        Console.WriteLine($"Undo: {title}");
    }
}

Cart: Dune, Foundation, 1984
Undo: 1984
Undo: Foundation
After two undos: Dune
Original: 3, 2, 1 | copy: 1, 2, 3

Push üste koyar, Pop üsttekini alır, Peek bakar. Hepsi O(1). Geri alma, tarayıcıdaki "geri" tuşu, expression parsing ve recursive bir algoritmayı döngüye çevirmek tipik kullanım alanları.

Son satır bir tuzak. Bir Stack<T>'i foreach ile dolaştığında element'ler üstten alta, yani Pop sırasıyla gelir: 3, 2, 1. new Stack<int>(original) ise original'i bu sırayla dolaşıp her birini Push eder; sonuçta kopya ters döner. Bir stack'i aynı sırayla kopyalamak istiyorsan iki kez ters çevirmen gerekir: new Stack<int>(original.Reverse()).

LinkedList<T>: Node'larla Çalışmak

LinkedList<string> readingList = new(new[] { "Dune", "Foundation", "1984" });

LinkedListNode<string> foundation = readingList.Find("Foundation")!;
readingList.AddAfter(foundation, "Hyperion");
readingList.AddFirst("The Hobbit");
readingList.Remove(foundation);

Console.WriteLine(string.Join(" -> ", readingList));
Console.WriteLine($"First: {readingList.First!.Value}, Last: {readingList.Last!.Value}, Count: {readingList.Count}");

The Hobbit -> Dune -> Hyperion -> 1984
First: The Hobbit, Last: 1984, Count: 4

LinkedList<T> çift yönlü bağlı bir liste. Her element bir LinkedListNode<T> içinde durur ve node bir öncekini (Previous) ve bir sonrakini (Next) bilir. Bir trenin vagonları gibi: araya vagon eklemek için diğer vagonları yerinden oynatmazsın, sadece iki bağlantıyı değiştirirsin. Elinde node varsa AddAfter, AddBefore ve Remove(node) O(1)'dir; listenin başı ve sonu da her zaman O(1).

Ama bedeli büyük. Index yok; readingList[2] yazamazsın. Bir değeri bulmak için Find baştan yürür: O(n). Her node heap'te ayrı bir object olduğu için bellekte dağınık durur ve modern işlemcilerin önbelleği bundan hoşlanmaz; pratikte List<T> üzerinde baştan sona dolaşmak, aynı sayıda element'li bir LinkedList<T>'yi dolaşmaktan genellikle hızlıdır. LinkedList<T>'yi ancak node'ları elinde tutup ortadan sık ekleme ve silme yaptığında seç.

LinkedList ve Dictionary: Son Bakılan Kitaplar

O "node'u elinde tutmak" şartını sağlamanın klasik yolu, node'ları bir dictionary'de saklamak. Kitap sayfasında "son baktığın üç kitap" kutusu tam olarak bu, yani küçük bir LRU (least recently used) cache:

RecentlyViewed recent = new(capacity: 3);
recent.Visit("Dune");
recent.Visit("Foundation");
recent.Visit("1984");
recent.Visit("Dune");
recent.Visit("The Hobbit");

Console.WriteLine(string.Join(" > ", recent.Items));

class RecentlyViewed
{
    private readonly int _capacity;
    private readonly LinkedList<string> _order = new();
    private readonly Dictionary<string, LinkedListNode<string>> _nodes = new();

    public RecentlyViewed(int capacity) => _capacity = capacity;

    public IEnumerable<string> Items => _order;

    public void Visit(string title)
    {
        if (_nodes.TryGetValue(title, out LinkedListNode<string>? node))
        {
            _order.Remove(node); // node elimizde: O(1)
            _order.AddFirst(node);
            return;
        }

        if (_order.Count == _capacity)
        {
            LinkedListNode<string> oldest = _order.Last!;
            _order.RemoveLast(); // en eski: listenin sonu
            _nodes.Remove(oldest.Value);
        }

        _nodes[title] = _order.AddFirst(title);
    }
}

The Hobbit > Dune > 1984

Dune'a ikinci kez bakıldığında listenin başına taşındı. The Hobbit geldiğinde kapasite dolu olduğu için en uzun süredir bakılmayan Foundation çıkarıldı. Dictionary "bu kitap listede nerede?" sorusuna O(1)'de cevap veriyor, linked list de o node'u O(1)'de yerinden alıp başa koyuyor. İki collection tek başına bunu yapamaz; birlikte her işlem sabit zamanda biter.

PriorityQueue<TElement, TPriority> Derinlemesine

Başa dönelim. PriorityQueue iki tip parametresi alır: queue'ya giren element ve onun önceliği. Öncelik, element'in kendi parçası değildir; aynı element farklı önceliklerle eklenebilir. Enqueue ve Dequeue O(log n), Peek O(1)'dir. Eşit önceliklerdeki karışıklığı çözmenin yolu, önceliğe bir sıra numarası eklemek:

PriorityQueue<string, (int Priority, long Sequence)> shipping = new();
long sequence = 0;

Enqueue("Order 1001 (standard)", 3);
Enqueue("Order 1002 (express)", 1);
Enqueue("Order 1003 (standard)", 3);
Enqueue("Order 1004 (same day)", 0);
Enqueue("Order 1005 (express)", 1);

while (shipping.TryDequeue(out string? order, out (int Priority, long Sequence) key))
{
    Console.WriteLine($"{key.Priority} {order}");
}

void Enqueue(string order, int priority) => shipping.Enqueue(order, (priority, sequence++));

0 Order 1004 (same day)
1 Order 1002 (express)
1 Order 1005 (express)
3 Order 1001 (standard)
3 Order 1003 (standard)

Tuple'lar önce ilk field'a, eşitse ikinci field'a bakarak karşılaştırılır. Öncelik aynıysa sıra numarası küçük olan, yani önce gelen kazanır. Queue artık "öncelikli ama adil".

Varsayılan davranış küçük olanın önce çıkması. Büyük olanı önce istiyorsan bir comparer verirsin. "En pahalı N kitap" gibi sorularda ise min-heap'in kendisi işine yarar:

using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

List<Book> books = new()
{
    new("Dune", 12.99m),
    new("Foundation", 9.50m),
    new("The Hobbit", 10.99m),
    new("1984", 8.99m),
    new("Brave New World", 11.49m),
    new("Hyperion", 14.25m),
};

PriorityQueue<Book, decimal> topThree = new();
foreach (Book book in books)
{
    if (topThree.Count < 3)
    {
        topThree.Enqueue(book, book.Price);
    }
    else
    {
        topThree.EnqueueDequeue(book, book.Price); // ekle, sonra en ucuzu at
    }
}

while (topThree.TryDequeue(out Book? book, out decimal price))
{
    Console.WriteLine($"{book.Title} {price}");
}

PriorityQueue<string, decimal> largestFirst = new(Comparer<decimal>.Create((x, y) => y.CompareTo(x)));
largestFirst.Enqueue("Order 2001", 25.00m);
largestFirst.Enqueue("Order 2002", 140.50m);
largestFirst.Enqueue("Order 2003", 61.75m);
Console.WriteLine($"Largest order first: {largestFirst.Dequeue()}");

record Book(string Title, decimal Price);

Brave New World 11.49
Dune 12.99
Hyperion 14.25
Largest order first: Order 2002

Üç kişilik bir min-heap, o ana kadar görülen en pahalı üç kitabı tutar; en tepede de üçün en ucuzu durur. Yeni gelen kitap EnqueueDequeue ile eklenir ve en ucuz olan atılır. Bütün listeyi sıralamak O(n log n) iken bu yöntem O(n log k)'dır ve bellekte sadece k element tutar. Milyonlarca satırlık bir log'dan "en yavaş 10 isteği" bulmak gibi işlerde fark büyüktür.

Bir eksik var: queue'daki bir element'in önceliğini değiştiremezsin. .NET 6'daki çözüm, yeni öncelikle bir kez daha eklemek ve çıkarırken eskimiş kayıtları atlamaktır. .NET 9'da bu iş için bir Remove method'u geldi; serinin sürüm yazılarında ona döneceğiz.

Sık Düşülen Tuzaklar

UnorderedItems'ı sıralı sanmak. Adı ne diyorsa o: heap'in iç düzeni. Sıra istiyorsan Dequeue ile çıkar.

PriorityQueue'nun eşit önceliklerde FIFO çalıştığını varsaymak. Yukarıdaki çıktı tersini gösterdi. Adaleti önceliğe bir sıra numarası ekleyerek sen sağlarsın.

Queue ihtiyacı için List<T> ve RemoveAt(0) kullanmak. Her çıkarma bütün listeyi kaydırır. Queue<T> aynı işi O(1)'de yapar.

Stack'i kopyalarken sıranın ters döndüğünü unutmak. new Stack<T>(stack) ters bir kopya üretir.

"Ortadan ekleme yapacağım" diye düşünmeden LinkedList<T> seçmek. Node'u elinde tutmuyorsan önce Find ile O(n) arama yaparsın ve kazancın kalmaz; üstelik dağınık bellek yüzünden dolaşması da yavaştır.

Boş bir collection'da Dequeue, Pop ya da Peek çağırmak. Üçü de InvalidOperationException fırlatır. Try ile başlayan karşılıklarını kullan.

Küçük Bir Deneme

★☆☆ Sepet örneğine bir "yinele" (redo) özelliği ekle: geri alınan kitapları ikinci bir Stack<string>'te tut ve tekrar sepete koy.

★★☆ RecentlyViewed'a kitap adlarını büyük-küçük harfe duyarsız eşleştiren bir dictionary ver (bir önceki yazıdaki StringComparer.OrdinalIgnoreCase) ve "dune" ziyaretinin "Dune"u başa taşıdığını göster.

★★★ Önceliği değiştirilebilen bir kargo queue'su yaz: her sipariş için güncel önceliği bir Dictionary<string, int>'te tut, önceliği değişen siparişi yeniden Enqueue et ve Dequeue sırasında önceliği dictionary'dekiyle eşleşmeyen eski kayıtları atla.

Bu yazıdaki collection'lar element'leri ekleme sırasına ya da önceliğe göre tutuyordu. Bir sonraki yazıda içeriği her zaman sıralı tutan collection'lara geçiyoruz: SortedList, SortedDictionary, SortedSet ve sıralamanın kuralını belirleyen IComparer<T>.