Queue trong C#: Enqueue, Dequeue, Peek và TryDequeue

Queue<T> hoạt động như một hàng người xếp trước quầy: phần tử được thêm vào đầu tiên là phần tử được lấy ra đầu tiên (FIFO, first in, first out, vào trước ra trước). Bạn thêm vào cuối hàng bằng Enqueue và lấy ra từ đầu hàng bằng Dequeue, cả hai đều trong thời gian hằng số.

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

Đầu ra:

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

Peek dùng để quyết định làm gì với phần tử kế tiếp trước khi thật sự lấy nó; Dequeue thì lấy luôn. Vòng lặp while (queue.Count > 0) lấy ra cho đến khi rỗng là cách chuẩn để xử lý một queue, và nó vẫn chạy đúng nếu thân vòng lặp thêm phần tử mới vào, điều mà foreach không cho phép.

Ngoại lệ khi queue rỗng và TryDequeue

Dequeue và Peek trên một queue rỗng sẽ ném InvalidOperationException. Không có kiểu hành vi "trả về null khi rỗng", kể cả với kiểu tham chiếu.

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

Đầu ra:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue và TryPeek trả về true và gán biến out khi có phần tử, và trả về false khi queue rỗng. Chúng xuất hiện từ .NET Core 2.0; với code .NET Framework cũ hơn, hãy kiểm tra Count > 0 trước khi gọi Dequeue.

Xem bên trong một queue

Bạn có thể duyệt một queue mà không lấy phần tử nào ra. foreach, ToArray và Contains đều thấy các phần tử theo thứ tự từ đầu đến cuối hàng.

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

Đầu ra:

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

Queue không có chỉ số: line[1] không biên dịch được, và bạn không thể xóa một phần tử ở giữa. Nếu cần một trong hai điều đó, dữ liệu của bạn thật ra không phải là một hàng đợi; hãy dùng List<T> hoặc LinkedList<T>. Giống các collection khác, thêm hoặc lấy phần tử bên trong một foreach trên chính queue đó sẽ ném InvalidOperationException.

Tìm kiếm theo chiều rộng với queue

Thứ tự của queue chính là thứ mà tìm kiếm theo chiều rộng (BFS) cần: đi qua mọi thứ cách một bước, rồi mọi thứ cách hai bước, và cứ thế tiếp tục. Ở đây nó tìm xem Ana cách mọi người khác bao nhiêu mối quan hệ trong một mạng lưới nhỏ:

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

Đầu ra:

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

Mỗi người chỉ được đưa vào queue một lần, ở lần đầu tiên được chạm tới, và vì queue trả họ ra theo đúng thứ tự được tìm thấy, lần đầu tiên đó luôn nằm trên một đường đi ngắn nhất. Đổi queue thành Stack thì cùng vòng lặp đó trở thành tìm kiếm theo chiều sâu, và không còn tìm được đường đi ngắn nhất nữa.

Cùng cấu trúc này xử lý được việc duyệt cây theo từng tầng, tô loang (flood fill) trên lưới và thu thập liên kết: bắt đầu với một phần tử trong queue, và chừng nào queue chưa rỗng thì lấy ra một phần tử rồi đưa các hàng xóm chưa được thăm của nó vào.

Queue và List cho công việc FIFO

Bạn có thể dùng List<T> làm hàng đợi với Add và RemoveAt(0), nhưng RemoveAt(0) dịch mọi phần tử còn lại lùi xuống một vị trí. Làm rỗng một danh sách 100.000 phần tử theo cách đó cần khoảng năm tỷ lần di chuyển phần tử; Queue<T> chỉ cần 100.000 bước với thời gian hằng số. Bên trong, queue là một bộ đệm vòng (circular buffer): nó theo dõi chỉ số đầu và chỉ số cuối trong một mảng và chỉ cấp phát lại khi mảng đầy.

ConcurrentQueue cho nhiều luồng

Queue<T> không an toàn đa luồng. Khi nhiều luồng cùng thêm hoặc lấy phần tử, hãy dùng ConcurrentQueue<T> trong System.Collections.Concurrent. Nó có Enqueue, TryDequeue và TryPeek nhưng không có Dequeue, vì khi có các luồng khác, "kiểm tra Count rồi Dequeue" có thể thất bại ngay giữa hai lời gọi.

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

Đầu ra:

4000
4000 processed

Nếu dùng Queue<T> thông thường thay cho ConcurrentQueue<T>, số lượng sẽ ra sai hoặc chương trình sẽ ném ngoại lệ, tùy vào thời điểm chạy. Với các luồng producer và consumer cần chờ việc thay vì quay vòng liên tục, BlockingCollection<T> (mặc định bọc một ConcurrentQueue<T>) hoặc System.Threading.Channels bổ sung khả năng chờ và báo hoàn tất. Xem lock để biết cách tự bảo vệ một collection thông thường.

PriorityQueue

Khi phần tử cần rời hàng theo độ ưu tiên thay vì thứ tự đến (phiếu khẩn cấp nhất trước, đường đi ngắn nhất hiện tại trong thuật toán Dijkstra), .NET 6 trở lên cung cấp PriorityQueue<TElement, TPriority>. Giá trị ưu tiên thấp nhất được lấy ra trước:

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

Các phần tử có cùng độ ưu tiên có thể ra theo thứ tự bất kỳ; hãy thêm một số thứ tự vào độ ưu tiên nếu cần thứ tự đến để phân định.

Lỗi thường gặp

• Dequeue mà không kiểm tra. Một queue rỗng sẽ ném InvalidOperationException; hãy lặp theo Count > 0 hoặc dùng TryDequeue.
• Gọi Peek và nghĩ rằng phần tử đã bị lấy ra. Chỉ Dequeue mới lấy ra.
• Enqueue bên trong foreach trên chính queue đó. Sẽ ném ngoại lệ; hãy xử lý bằng vòng lặp while.
• Dùng chung một Queue<T> giữa nhiều luồng. Hãy dùng ConcurrentQueue<T> hoặc một lock.
• Dùng List.RemoveAt(0) làm hàng đợi với dữ liệu lớn. Mỗi lần gọi là O(n).