C# Queue: תור עם 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 ואותה לולאה הופכת לחיפוש לעומק, שכבר לא מוצא מסלולים קצרים ביותר.

אותה צורה מתאימה למעבר על עץ לפי רמות, למילוי שטח ברשת (flood fill) ולסריקת קישורים: מתחילים עם איבר אחד בתור, וכל עוד הוא לא ריק, מוציאים איבר אחד ומכניסים את השכנים שלו שעוד לא ביקרנו בהם.

Queue מול List לעבודת FIFO

אפשר להשתמש ב-List<T> כתור עם Add ו-RemoveAt(0), אבל RemoveAt(0) מזיז כל איבר שנשאר מקום אחד אחורה. ריקון של רשימה עם 100,000 איברים בדרך הזו מבצע בערך חמישה מיליארד הזזות של איברים; Queue<T> מבצע 100,000 צעדים בזמן קבוע. בפנים, תור הוא חוצץ מעגלי: הוא עוקב אחרי אינדקס ראש ואינדקס זנב בתוך מערך ומקצה מחדש רק כשהוא מתמלא.

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).