المكدّس Stack في C#: 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

السحب أو النظر في مكدّس فارغ يرمي InvalidOperationException. يظهر هذا غالبًا في المحلّلات والخوارزميات التي تتغذى بمدخلات فيها عناصر إغلاق أكثر من عناصر الفتح.

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.

مثال: سجل التراجع

تحفظ المحرّرات كل تغيير في مكدّس. يسحب التراجع أحدث تغيير ويعكسه؛ ويحفظ الإعادة مكدّسًا ثانيًا للتغييرات المتراجع عنها.

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

تخزين لقطات كاملة هو النسخة الأبسط. أما المحرّرات الحقيقية فتدفع كائنات أوامر صغيرة بدلًا من ذلك (ما أُدرج، وأين)، لكل منها دالة تعكس نفسها، لكن المكدّسين يعملان بالطريقة نفسها.

مثال: الأقواس المتوازنة

التحقق من إغلاق ( و[ و{ بالترتيب الصحيح هو التمرين القياسي على المكدّس، والمنطق نفسه موجود داخل كل مترجم ومحلّل 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، الذي لا يمكن التقاطه.
• تقييم التعابير. يُقيَّم الترميز اللاحق (3 4 + 2 *) بدفع الأرقام وسحب اثنين لكل معامل.
• التراجع (backtracking). سجل التصفح وحل المتاهات وحالات المحلّل تدفع موضعًا وتعود إليه بالسحب عند طريق مسدود.

راجع 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).