Queue di C#: Enqueue, Dequeue, Peek dan TryDequeue

Queue<T> bekerja seperti antrean di loket: item yang pertama ditambahkan adalah yang pertama diambil (FIFO, first in, first out). Kamu menambahkan di belakang dengan Enqueue dan mengambil dari depan dengan Dequeue, keduanya dalam waktu konstan.

Enqueue, Dequeue, dan 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);
    }
}

Output:

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

Peek dipakai untuk memutuskan apa yang akan dilakukan dengan item berikutnya sebelum benar-benar mengambilnya; Dequeue benar-benar mengambilnya. Perulangan while (queue.Count > 0) yang terus melakukan dequeue sampai kosong adalah cara standar memproses queue, dan cara ini tetap berjalan jika isi perulangan menambahkan item baru ke queue, sesuatu yang tidak diizinkan oleh foreach.

Exception saat queue kosong dan TryDequeue

Dequeue dan Peek pada queue kosong melempar InvalidOperationException. Tidak ada perilaku "null jika kosong", bahkan untuk reference type.

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
    }
}

Output:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue dan TryPeek mengembalikan true dan mengisi variabel out jika ada item, dan mengembalikan false jika queue kosong. Keduanya hadir di .NET Core 2.0; di kode .NET Framework yang lebih lama, periksa Count > 0 sebelum memanggil Dequeue.

Melihat isi queue

Kamu bisa melakukan enumerasi pada queue tanpa menghapus apa pun. foreach, ToArray, dan Contains semuanya melihat item dari depan ke belakang.

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
    }
}

Output:

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

Queue tidak punya indeks: line[1] tidak bisa dikompilasi, dan kamu tidak bisa menghapus item dari tengah. Jika kamu butuh salah satunya, datamu sebenarnya bukan queue; pakai List<T> atau LinkedList<T>. Sama seperti collection lain, melakukan enqueue atau dequeue di dalam foreach pada queue yang sama akan melempar InvalidOperationException.

Breadth first search dengan queue

Urutan queue persis seperti yang dibutuhkan breadth first search: kunjungi semua yang berjarak satu langkah, lalu semua yang berjarak dua langkah, dan seterusnya. Di sini BFS mencari berapa koneksi yang memisahkan Ana dari semua orang lain di sebuah jaringan kecil:

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");
        }
    }
}

Output:

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

Setiap orang dimasukkan ke queue sekali saja, yaitu saat pertama kali dicapai, dan karena queue mengembalikan mereka sesuai urutan ditemukannya, pertama kali itu selalu lewat jalur terpendek. Ganti queue dengan Stack dan perulangan yang sama menjadi depth first search, yang tidak lagi menemukan jalur terpendek.

Bentuk yang sama bisa dipakai untuk traversal level order pada tree, flood fill pada grid, dan menjelajahi link: mulai dengan satu item di queue, lalu selama queue tidak kosong, ambil satu dan masukkan tetangganya yang belum dikunjungi.

Queue vs List untuk pekerjaan FIFO

Kamu bisa memakai List<T> sebagai queue dengan Add dan RemoveAt(0), tetapi RemoveAt(0) menggeser setiap elemen yang tersisa satu posisi ke bawah. Mengosongkan list berisi 100.000 item dengan cara itu butuh sekitar lima miliar perpindahan elemen; Queue<T> hanya butuh 100.000 langkah berwaktu konstan. Di balik layar, queue adalah circular buffer: ia mencatat indeks head dan tail ke dalam sebuah array dan hanya mengalokasikan ulang saat penuh.

ConcurrentQueue untuk banyak thread

Queue<T> tidak thread safe. Jika beberapa thread menambah atau mengambil item, pakai ConcurrentQueue<T> dari System.Collections.Concurrent. Class ini punya Enqueue, TryDequeue, dan TryPeek, tetapi tidak punya Dequeue, karena saat ada thread lain, langkah "periksa Count lalu Dequeue" bisa gagal di antara kedua panggilan itu.

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");
    }
}

Output:

4000
4000 processed

Jika ConcurrentQueue<T> diganti dengan Queue<T> biasa, hitungannya bisa salah atau program melempar exception, tergantung waktunya. Untuk thread producer dan consumer yang seharusnya menunggu pekerjaan alih-alih terus berputar, BlockingCollection<T> (yang secara default membungkus ConcurrentQueue<T>) atau System.Threading.Channels menambahkan fitur blocking dan penyelesaian. Lihat lock untuk melindungi collection biasa secara manual.

PriorityQueue

Jika item harus keluar berdasarkan prioritas, bukan urutan kedatangan (tiket paling mendesak lebih dulu, jalur terpendek sejauh ini di algoritma Dijkstra), .NET 6 dan sesudahnya menyediakan PriorityQueue<TElement, TPriority>. Nilai prioritas terendah keluar lebih dulu:

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

Item dengan prioritas yang sama bisa keluar dalam urutan apa pun; tambahkan nomor urut ke prioritasnya jika urutan kedatangan harus menjadi penentu saat nilainya sama.

Kesalahan umum

• Melakukan dequeue tanpa memeriksa. Queue kosong melempar InvalidOperationException; pakai perulangan dengan Count > 0 atau pakai TryDequeue.
• Memanggil Peek dan mengira itemnya sudah hilang. Hanya Dequeue yang menghapus.
• Melakukan enqueue di dalam foreach pada queue itu. Ini melempar exception; proses dengan perulangan while.
• Memakai satu Queue<T> bersama di beberapa thread. Pakai ConcurrentQueue<T> atau lock.
• Memakai List.RemoveAt(0) sebagai queue untuk data besar. Setiap panggilan butuh waktu O(n).