الطابور Queue في C#: Enqueue وDequeue وPeek وTryDequeue

يعمل Queue<T> مثل طابور أمام شبّاك: أول عنصر يُضاف هو أول عنصر يُؤخذ (FIFO، الداخل أولًا يخرج أولًا). تضيف في المؤخرة بـ Enqueue وتأخذ من المقدمة بـ Dequeue، كلاهما في زمن ثابت.

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

المخرجات:

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

Peek لتقرير ما تفعله بالعنصر التالي قبل الالتزام به؛ وDequeue تلتزم. حلقة while (queue.Count > 0) التي تسحب حتى يفرغ الطابور هي الطريقة القياسية لمعالجة طابور، وتظل تعمل إن أضاف جسم الحلقة عناصر أخرى، وهو ما لا تسمح به foreach.

استثناء الطابور الفارغ وTryDequeue

ترمي Dequeue وPeek على طابور فارغ InvalidOperationException. لا يوجد سلوك "null عند الفراغ"، حتى للأنواع المرجعية.

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

المخرجات:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

تعيد TryDequeue وTryPeek القيمة true وتضبطان متغيّر out حين يوجد عنصر، وتعيدان false حين يكون الطابور فارغًا. وصلتا في .NET Core 2.0؛ وفي شيفرة .NET Framework الأقدم افحص Count > 0 قبل استدعاء Dequeue.

النظر داخل الطابور

يمكن تعداد الطابور دون حذف شيء. ترى foreach وToArray وContains كلها العناصر من المقدمة إلى المؤخرة.

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

المخرجات:

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

لا فهرس: لا تُترجم line[1]، ولا يمكنك حذف عنصر من المنتصف. إن احتجت إلى أي منهما فالبيانات ليست طابورًا حقًا؛ استخدم List<T> أو LinkedList<T>. وكما في المجموعات الأخرى، الإضافة أو السحب داخل foreach على الطابور نفسه يرمي InvalidOperationException.

البحث بالعرض أولًا بطابور

ترتيب الطابور هو بالضبط ما يحتاجه البحث بالعرض أولًا (BFS): زر كل ما يبعد خطوة واحدة، ثم كل ما يبعد خطوتين، وهكذا. هنا يجد عدد الوصلات التي تفصل Ana عن كل شخص آخر في شبكة صغيرة:

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

المخرجات:

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

يُضاف كل شخص إلى الطابور مرة واحدة، أول مرة يُبلغ فيها، ولأن الطابور يعيدهم بترتيب العثور عليهم تكون المرة الأولى دائمًا على مسار أقصر. استبدل الطابور بـ Stack فتصبح الحلقة نفسها بحثًا بالعمق أولًا، الذي لا يجد أقصر المسارات بعد ذلك.

والشكل نفسه يعالج المرور على شجرة مستوى بمستوى، والتعبئة بالفيضان على شبكة، وزحف الروابط: ابدأ بعنصر واحد في الطابور، وما دام غير فارغ اسحب واحدًا وأضف جيرانه غير المزورين.

Queue مقابل List لعمل FIFO

يمكنك استخدام List<T> كطابور بـ Add وRemoveAt(0)، لكن RemoveAt(0) تزيح كل عنصر متبقٍّ خانة واحدة للخلف. تفريغ قائمة من 100,000 عنصر بهذه الطريقة يجري نحو خمسة مليارات نقل عنصر؛ بينما يجري Queue<T> مئة ألف خطوة بزمن ثابت. داخليًا الطابور مخزن دائري: يتتبّع فهرسي رأس وذيل في مصفوفة ولا يعيد الحجز إلا حين يمتلئ.

ConcurrentQueue لعدة خيوط

Queue<T> غير آمن مع الخيوط. حين تضيف عدة خيوط عناصر أو تأخذها استخدم ConcurrentQueue<T> من System.Collections.Concurrent. فيه Enqueue وTryDequeue وTryPeek لكن لا Dequeue، لأنه مع وجود خيوط أخرى قد يفشل "افحص Count ثم Dequeue" بين الاستدعاءين.

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

المخرجات:

4000
4000 processed

مع Queue<T> عادي مكان ConcurrentQueue<T> كان العدد سيخرج خاطئًا أو كان البرنامج سيرمي استثناءً، بحسب التوقيت. ولخيوط المنتج والمستهلك التي يجب أن تنتظر العمل بدل الدوران، تضيف BlockingCollection<T> (التي تغلّف ConcurrentQueue<T> افتراضيًا) أو System.Threading.Channels الحجب والإكمال. راجع lock لحماية مجموعة عادية يدويًا.

PriorityQueue

حين يجب أن تغادر العناصر بحسب الأولوية لا بترتيب الوصول (التذكرة الأكثر إلحاحًا أولًا، أو أقصر مسار حتى الآن في خوارزمية Dijkstra)، توفّر .NET 6 وما بعدها PriorityQueue<TElement, TPriority>. تخرج أدنى قيمة أولوية أولًا:

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

العناصر ذات الأولوية المتساوية قد تخرج بأي ترتيب؛ أضف رقمًا تسلسليًا إلى الأولوية إن كان يجب أن يحسم ترتيب الوصول التعادل.

أخطاء شائعة

• السحب دون فحص. الطابور الفارغ يرمي InvalidOperationException؛ دُر على Count > 0 أو استخدم TryDequeue.
• استدعاء Peek وتوقّع أن يختفي العنصر. وحدها Dequeue تحذف.
• الإضافة داخل foreach على الطابور. يرمي استثناءً؛ عالج بحلقة while بدلًا من ذلك.
• مشاركة Queue<T> بين الخيوط. استخدم ConcurrentQueue<T> أو قفلًا.
• استخدام List.RemoveAt(0) كطابور على بيانات كبيرة. كل استدعاء O(n).