Çalıştırılabilir C# Dokümanları: Queue

Q: C#'ta Queue nedir?

System.Collections.Generic içindeki Queue , ilk giren ilk çıkar (FIFO) bir koleksiyondur. Enqueue arkaya bir öğe ekler, Dequeue öndeki öğeyi çıkarıp döndürür ve Peek öndeki öğeyi çıkarmadan döndürür. Üçü de sabit zaman alır.

Q: C#'ta boş bir kuyrukta Dequeue yapınca ne olur?

Boş bir kuyrukta Dequeue ve Peek InvalidOperationException fırlatır. Önce queue.Count > 0 kontrol edin ya da istisna fırlatmak yerine false döndüren TryDequeue(out var item) ve TryPeek(out var item)'i kullanın (.NET Core 2.0'dan beri vardır).

Q: Peek ile Dequeue arasındaki fark nedir?

Peek öndeki öğeyi döndürür ve kuyrukta bırakır, bu yüzden iki kez çağırmak aynı öğeyi döndürür. Dequeue öndeki öğeyi döndürür ve çıkarır, bu yüzden sonraki çağrı onun arkasındaki öğeyi döndürür.

Q: C#'ta Queue thread-safe mi?

Hayır. Aynı Queue üzerinde aynı anda Enqueue ya da Dequeue çağıran iki thread onu bozabilir. Enqueue ve TryDequeue metotları birçok thread'den çağrılmaya güvenli olan System.Collections.Concurrent içindeki ConcurrentQueue 'yu kullanın ya da normal bir kuyruğa her erişimi bir lock içine alın.

Q: List yerine neden Queue kullanılmalı?

Bir List 'nin ilk öğesini RemoveAt(0) ile silmek diğer her öğeyi kaydırır, bu yüzden liste büyüdükçe yavaşlar. Bir Queue önden sabit zamanda siler ve API'si niyeti belirtir: öğeler geliş sırasıyla işlenir.

Bir Queue<T> bir gişedeki sıra gibi çalışır: eklenen ilk öğe ilk çıkarılandır (FIFO, first in, first out). Arkaya Enqueue ile ekler, önden Dequeue ile alırsınız; ikisi de sabit zamanlıdır.

Enqueue, Dequeue ve Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var printJobs = new Queue<string>();
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("photo.png");
        printJobs.Enqueue("report.docx");

        Console.WriteLine("Waiting: " + printJobs.Count);
        Console.WriteLine("Next up: " + printJobs.Peek()); // look, do not remove

        string job = printJobs.Dequeue();                   // remove the front
        Console.WriteLine("Printing " + job);
        Console.WriteLine("Next up: " + printJobs.Peek());

        while (printJobs.Count > 0)
        {
            Console.WriteLine("Printing " + printJobs.Dequeue());
        }
        Console.WriteLine("Waiting: " + printJobs.Count);
    }
}

Çıktı:

Waiting: 3
Next up: invoice.pdf
Printing invoice.pdf
Next up: photo.png
Printing photo.png
Printing report.docx
Waiting: 0

Peek, sonraki öğeyle ne yapacağınıza ona bağlanmadan önce karar vermek içindir; Dequeue bağlanır. Boşalana kadar çıkaran while (queue.Count > 0) döngüsü bir kuyruğu işlemenin standart yoludur ve döngü gövdesi yeni öğeler eklerse de çalışmaya devam eder; bir foreach buna izin vermez.

Boş kuyruk istisnası ve TryDequeue

Boş bir kuyrukta Dequeue ve Peek InvalidOperationException fırlatır. Referans tipleri için bile "boşken null" davranışı yoktur.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tickets = new Queue<int>();

        try
        {
            tickets.Dequeue();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        tickets.Enqueue(41);
        tickets.Enqueue(42);

        int ticket;
        while (tickets.TryDequeue(out ticket))
        {
            Console.WriteLine("Serving ticket " + ticket);
        }

        Console.WriteLine(tickets.TryPeek(out ticket)); // false: empty
    }
}

Çıktı:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue ve TryPeek bir öğe olduğunda true döndürüp out değişkenini ayarlar, kuyruk boşken false döndürür. .NET Core 2.0 ile geldiler; eski .NET Framework kodunda Dequeue çağırmadan önce Count > 0 kontrol edin.

Bir kuyruğun içine bakmak

Bir kuyruk hiçbir şey çıkarmadan dolaşılabilir. foreach, ToArray ve Contains öğeleri önden arkaya görür.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = new Queue<string>(new[] { "Ana", "Ben", "Chloe" });

        foreach (string name in line)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        Console.WriteLine(line.Contains("Ben"));
        string[] snapshot = line.ToArray();
        Console.WriteLine(snapshot[0] + " is first, " + snapshot.Length + " in line");
        Console.WriteLine(line.Count); // nothing was removed
    }
}

Çıktı:

Ana Ben Chloe 
True
Ana is first, 3 in line
3

İndeks yoktur: line[1] derlenmez ve ortadan bir öğe çıkaramazsınız. İkisinden birine ihtiyacınız varsa veri aslında bir kuyruk değildir; bir List<T> ya da bir LinkedList<T> kullanın. Diğer koleksiyonlarda olduğu gibi aynı kuyruk üzerindeki bir foreach içinde ekleme ya da çıkarma yapmak InvalidOperationException fırlatır.

Bir kuyrukla genişlik öncelikli arama

Kuyruğun sıralaması tam olarak genişlik öncelikli aramanın ihtiyaç duyduğu şeydir: önce bir adım uzaktaki her şeyi, sonra iki adım uzaktaki her şeyi ziyaret etmek ve böyle devam etmek. Burada küçük bir ağda Ana'yı diğer herkesten kaç bağlantının ayırdığını bulur:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var friends = new Dictionary<string, string[]>
        {
            ["Ana"] = new[] { "Ben", "Chloe" },
            ["Ben"] = new[] { "Ana", "Dev" },
            ["Chloe"] = new[] { "Ana", "Dev", "Eli" },
            ["Dev"] = new[] { "Ben", "Chloe", "Fay" },
            ["Eli"] = new[] { "Chloe" },
            ["Fay"] = new[] { "Dev" },
        };

        var distance = new Dictionary<string, int> { ["Ana"] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue("Ana");

        while (queue.Count > 0)
        {
            string person = queue.Dequeue();
            foreach (string next in friends[person])
            {
                if (!distance.ContainsKey(next))
                {
                    distance[next] = distance[person] + 1;
                    queue.Enqueue(next);
                }
            }
        }

        foreach (var pair in distance)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value + " step(s) from Ana");
        }
    }
}

Çıktı:

Ana: 0 step(s) from Ana
Ben: 1 step(s) from Ana
Chloe: 1 step(s) from Ana
Dev: 2 step(s) from Ana
Eli: 2 step(s) from Ana
Fay: 3 step(s) from Ana

Her kişi, ilk ulaşıldığında bir kez kuyruğa eklenir ve kuyruk onları bulundukları sırayla geri verdiği için ilk ulaşma her zaman en kısa yol üzerindendir. Kuyruğu bir Stack ile değiştirin, aynı döngü artık en kısa yolları bulmayan derinlik öncelikli aramaya dönüşür.

Aynı şekil bir ağacın seviye sıralı dolaşmasını, bir ızgarada flood fill'i ve bağlantı taramayı halleder: kuyrukta tek bir öğeyle başlayın ve kuyruk boş olmadığı sürece birini çıkarıp ziyaret edilmemiş komşularını ekleyin.

FIFO işler için Queue ve List

Add ve RemoveAt(0) ile bir List<T>'yi kuyruk olarak kullanabilirsiniz, ama RemoveAt(0) kalan her elemanı bir yuva aşağı kaydırır. 100.000 öğelik bir listeyi böyle boşaltmak yaklaşık beş milyar eleman taşıması yapar; bir Queue<T> ise 100.000 sabit zamanlı adım yapar. İçeride bir kuyruk dairesel bir tampondur: bir dizideki baş ve kuyruk indekslerini izler ve yalnızca dolduğunda yeniden ayırır.

İşlem	`Queue<T>`	Kuyruk olarak kullanılan `List<T>`
Arkaya eklemek	`Enqueue`, O(1)	`Add`, O(1)
Önden çıkarmak	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
Öne bakmak	`Peek`	`list[0]`
İndeks erişimi	Yok	`list[i]`

Birden fazla thread için ConcurrentQueue

Queue<T> thread-safe değildir. Birkaç thread öğe ekleyip aldığında System.Collections.Concurrent içindeki ConcurrentQueue<T>'yu kullanın. Enqueue, TryDequeue ve TryPeek'i vardır ama Dequeue'su yoktur, çünkü etrafta başka thread'ler varken "Count'u kontrol et sonra Dequeue yap" iki çağrı arasında başarısız olabilir.

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        var events = new ConcurrentQueue<int>();

        // 4 parallel iterations each add 1,000 items.
        Parallel.For(0, 4, worker =>
        {
            for (int i = 0; i < 1000; i++) events.Enqueue(i);
        });
        Console.WriteLine(events.Count);

        int total = 0;
        int item;
        while (events.TryDequeue(out item)) total++;
        Console.WriteLine(total + " processed");
    }
}

Çıktı:

4000
4000 processed

ConcurrentQueue<T> yerine düz bir Queue<T> ile sayı zamanlamaya bağlı olarak yanlış çıkardı ya da program istisna fırlatırdı. Boşa dönmek yerine iş beklemesi gereken üretici ve tüketici thread'ler için BlockingCollection<T> (varsayılan olarak bir ConcurrentQueue<T>'yu sarar) ya da System.Threading.Channels bekleme ve tamamlanma ekler. Normal bir koleksiyonu elle korumak için lock sayfasına bakın.

PriorityQueue

Öğelerin geliş sırasına göre değil önceliğe göre çıkması gerektiğinde (önce en acil destek talebi, Dijkstra algoritmasında o ana kadarki en kısa yol), .NET 6 ve sonrası PriorityQueue<TElement, TPriority> sağlar. En düşük öncelik değeri önce çıkar:

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("chest pain", 1);
triage.Enqueue("headache", 5);

while (triage.TryDequeue(out string patient, out int priority))
{
    Console.WriteLine($"{priority}: {patient}");
}
// 1: chest pain
// 3: sprained ankle
// 5: headache

Eşit öncelikli öğeler herhangi bir sırayla çıkabilir; eşitliği geliş sırası bozmalıysa önceliğe bir sıra numarası ekleyin.

Yaygın hatalar

Kontrol etmeden Dequeue yapmak. Boş bir kuyruk InvalidOperationException fırlatır; Count > 0 üzerinde döngü kurun ya da TryDequeue kullanın.
Peek çağırıp öğenin gitmesini beklemek. Yalnızca Dequeue çıkarır.
Kuyruk üzerindeki foreach içinde Enqueue yapmak. İstisna fırlatır; bunun yerine bir while döngüsüyle işleyin.
Bir Queue<T>'yu thread'ler arasında paylaşmak. ConcurrentQueue<T> ya da bir lock kullanın.
Büyük veride kuyruk olarak List.RemoveAt(0) kullanmak. Her çağrı O(n)'dir.

Sıkça Sorulan Sorular

C#'ta Queue nedir?

System.Collections.Generic içindeki Queue<T>, ilk giren ilk çıkar (FIFO) bir koleksiyondur. Enqueue arkaya bir öğe ekler, Dequeue öndeki öğeyi çıkarıp döndürür ve Peek öndeki öğeyi çıkarmadan döndürür. Üçü de sabit zaman alır.

C#'ta boş bir kuyrukta Dequeue yapınca ne olur?

Boş bir kuyrukta Dequeue ve Peek InvalidOperationException fırlatır. Önce queue.Count > 0 kontrol edin ya da istisna fırlatmak yerine false döndüren TryDequeue(out var item) ve TryPeek(out var item)'i kullanın (.NET Core 2.0'dan beri vardır).

Peek ile Dequeue arasındaki fark nedir?

Peek öndeki öğeyi döndürür ve kuyrukta bırakır, bu yüzden iki kez çağırmak aynı öğeyi döndürür. Dequeue öndeki öğeyi döndürür ve çıkarır, bu yüzden sonraki çağrı onun arkasındaki öğeyi döndürür.

C#'ta Queue<T> thread-safe mi?

Hayır. Aynı Queue<T> üzerinde aynı anda Enqueue ya da Dequeue çağıran iki thread onu bozabilir. Enqueue ve TryDequeue metotları birçok thread'den çağrılmaya güvenli olan System.Collections.Concurrent içindeki ConcurrentQueue<T>'yu kullanın ya da normal bir kuyruğa her erişimi bir lock içine alın.

List yerine neden Queue kullanılmalı?

Bir List<T>'nin ilk öğesini RemoveAt(0) ile silmek diğer her öğeyi kaydırır, bu yüzden liste büyüdükçe yavaşlar. Bir Queue<T> önden sabit zamanda siler ve API'si niyeti belirtir: öğeler geliş sırasıyla işlenir.

İlgili kavramlar