C# Stack: מחסנית עם Push, Pop, Peek, ביטול פעולות ואיזון סוגריים

Stack<T> הוא ערימה: שמים איברים בראש עם Push ולוקחים אותם מהראש עם Pop, כך שהאיבר האחרון שנכנס הוא הראשון שיוצא (LIFO). רק הראש נגיש, וכל פעולה עליו לוקחת זמן קבוע.

Push, Pop ו-Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var plates = new Stack<string>();
        plates.Push("blue");
        plates.Push("red");
        plates.Push("green");

        Console.WriteLine("On top: " + plates.Peek()); // look only
        Console.WriteLine("Count: " + plates.Count);

        Console.WriteLine("Took " + plates.Pop());       // remove the top
        Console.WriteLine("On top: " + plates.Peek());

        while (plates.Count > 0)
        {
            Console.WriteLine("Took " + plates.Pop());
        }
        Console.WriteLine("Count: " + plates.Count);
    }
}

פלט:

On top: green
Count: 3
Took green
On top: red
Took red
Took blue
Count: 0

green נדחף אחרון, ולכן הוא יוצא ראשון. Peek מחזיר את הראש בלי לשנות את המחסנית, וכך בודקים מה Pop ייתן לפני שמחליטים לקחת אותו.

החריגה של מחסנית ריקה ו-TryPop

Pop או Peek על מחסנית ריקה זורקים InvalidOperationException. זה קורה הכי הרבה ב-parsers ובאלגוריתמים שמקבלים קלט עם יותר פריטים סוגרים מפותחים.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var history = new Stack<int>();

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

        history.Push(10);

        int value;
        Console.WriteLine(history.TryPop(out value) + " " + value);
        Console.WriteLine(history.TryPop(out value) + " " + value); // empty now
    }
}

פלט:

Caught InvalidOperationException
True 10
False 0

TryPop ו-TryPeek (.NET Core 2.0 ואילך) מחזירים false על מחסנית ריקה ומציבים במשתנה ה-out את ערך ברירת המחדל, כאן 0. ב-.NET Framework, בדקו קודם Count > 0.

סדר המעבר: הראש קודם

מעבר על מחסנית לא מסיר כלום, והוא הולך מלמעלה למטה, בסדר ש-Pop היה מחזיר את האיברים:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var pages = new Stack<string>();
        pages.Push("home");
        pages.Push("products");
        pages.Push("checkout");

        foreach (string page in pages)
        {
            Console.Write(page + " ");
        }
        Console.WriteLine();

        Console.WriteLine(string.Join(" > ", pages.ToArray()));
        Console.WriteLine(pages.Contains("home"));

        var copy = new Stack<string>(pages);  // pushes in enumeration order...
        Console.WriteLine(copy.Peek());        // ...so the copy is reversed

        var sameOrder = new Stack<string>(pages.Reverse());
        Console.WriteLine(sameOrder.Peek());
    }
}

פלט:

checkout products home 
checkout > products > home
True
home
checkout

העותק ההפוך מפיל אנשים בפח: הבנאי מקבל כל IEnumerable<T> ודוחף את האיברים שלו לפי הסדר, ומחסנית עוברת על האיברים מהראש, כך שהראש הישן מגיע לתחתית העותק. היפוך הרצף קודם (Reverse() של LINQ מחזיר את האיברים מהתחתית) נותן עותק עם אותו ראש.

גם דחיפה של רשימת איברים למחסנית חדשה הופכת אותם, וזו דרך מהירה להפוך רצף: new Stack<char>("hello") מוציא בחזרה o, l, l, e, h.

דוגמה: היסטוריית ביטול

עורכי טקסט שומרים כל שינוי במחסנית. ביטול (undo) מוציא את השינוי האחרון ומחזיר אותו לאחור; ביצוע מחדש (redo) שומר מחסנית שנייה של שינויים שבוטלו.

using System;
using System.Collections.Generic;

class Editor
{
    private string text = "";
    private readonly Stack<string> undo = new Stack<string>();
    private readonly Stack<string> redo = new Stack<string>();

    public void Type(string s)
    {
        undo.Push(text);   // remember the state before the change
        redo.Clear();      // a new change invalidates the redo history
        text += s;
    }

    public void Undo()
    {
        if (undo.Count == 0) return;
        redo.Push(text);
        text = undo.Pop();
    }

    public void Redo()
    {
        if (redo.Count == 0) return;
        undo.Push(text);
        text = redo.Pop();
    }

    public string Text { get { return text; } }
}

class Program
{
    static void Main()
    {
        var ed = new Editor();
        ed.Type("Hello");
        ed.Type(", world");
        ed.Type("!");
        Console.WriteLine(ed.Text);

        ed.Undo();
        Console.WriteLine(ed.Text);
        ed.Undo();
        Console.WriteLine(ed.Text);

        ed.Redo();
        Console.WriteLine(ed.Text);
    }
}

פלט:

Hello, world!
Hello, world
Hello
Hello, world

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

דוגמה: איזון סוגריים

בדיקה ש-(, [ ו-{ נסגרים בסדר הנכון היא התרגיל הקלאסי על מחסניות, ואותה לוגיקה יושבת בתוך כל קומפיילר ו-parser של JSON.

using System;
using System.Collections.Generic;

class Program
{
    static bool IsBalanced(string s)
    {
        var open = new Stack<char>();
        foreach (char c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                open.Push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
                if (open.Count == 0) return false;          // closer with no opener
                char top = open.Pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false; // wrong kind
            }
        }
        return open.Count == 0;                             // leftovers are unclosed
    }

    static void Main()
    {
        string[] inputs = { "f(a[i], {x: 1})", "(]", "((a)", "a)b(", "" };
        foreach (string input in inputs)
        {
            Console.WriteLine("\"" + input + "\" -> " + IsBalanced(input));
        }
    }
}

פלט:

"f(a[i], {x: 1})" -> True
"(]" -> False
"((a)" -> False
"a)b(" -> False
"" -> True

שלוש בדיקות הכישלון מתאימות לשלוש הדרכים שבהן סוגריים משתבשים: סוגר בלי שום דבר פתוח (a)b(, שנתפס על ידי Count == 0 במקום חריגה מ-Pop), סוגר מהסוג הלא נכון ((]), ופותחים שאף פעם לא נסגרו (((a), שנתפסים בבדיקה הסופית).

שימושים נוספים

• חיפוש לעומק. החליפו את התור בחיפוש לרוחב במחסנית והמעבר ילך לעומק לפני שהוא הולך לרוחב. מחסנית מפורשת גם מחליפה רקורסיה כשהקלט עמוק מספיק כדי להסתכן ב-StackOverflowException, שאי אפשר לתפוס.
• חישוב ביטויים. כתיב postfix (3 4 + 2 *) מחושב על ידי דחיפת מספרים והוצאת שניים לכל אופרטור.
• חזרה לאחור (backtracking). היסטוריית ניווט, פתרון מבוכים ומצבי parser דוחפים מיקום וחוזרים אליו במבוי סתום.

ראו את Queue למקבילה מסוג "ראשון נכנס, ראשון יוצא".

Stack מול Queue מול List

לכמה תהליכונים, ConcurrentStack<T> ב-System.Collections.Concurrent מציע Push, TryPop ו-TryPeek בלי נעילות.

טעויות נפוצות

• הוצאה בלי בדיקה. מחסנית ריקה זורקת InvalidOperationException; בדקו את Count או השתמשו ב-TryPop.
• ציפייה ש-foreach יתחיל מהאיבר הראשון שנדחף. הוא מתחיל מהראש.
• העתקה עם new Stack<T>(stack). העותק הפוך.
• דחיפה בתוך foreach על אותה מחסנית. זורק חריגה; השתמשו בלולאת while (stack.Count > 0).