C# Stack: Push, Pop, Peek, Geri Alma ve Parantez Eşleştirme

Bir Stack<T> bir yığındır: öğeleri Push ile en üste koyar ve Pop ile en üstten alırsınız, böylece son giren ilk çıkar (LIFO). Yalnızca en üst erişilebilirdir ve üzerindeki her işlem sabit zaman alır.

Push, Pop ve 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);
    }
}

Çıktı:

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

green en son push edildi, bu yüzden ilk o çıkar. Peek stack'i değiştirmeden en üstü döndürür; Pop'un size ne vereceğini almaya karar vermeden önce böyle incelersiniz.

Boş stack istisnası ve TryPop

Boş bir stack'te pop ya da peek yapmak InvalidOperationException fırlatır. Bu en çok, kapanış öğeleri açılışlardan fazla olan girdiyle beslenen parser'larda ve algoritmalarda ortaya çıkar.

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

Çıktı:

Caught InvalidOperationException
True 10
False 0

TryPop ve TryPeek (.NET Core 2.0 ve sonrası) boş bir stack'te false döndürür ve out değişkenini varsayılan değere, burada 0'a ayarlar. .NET Framework'te önce Count > 0 kontrol edin.

Dolaşma sırası: önce en üst

Bir stack'i dolaşmak hiçbir şeyi çıkarmaz ve Pop'un öğeleri döndüreceği sırayla, yukarıdan aşağıya gider:

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

Çıktı:

checkout products home 
checkout > products > home
True
home
checkout

Ters çevrilmiş kopya insanları yakalar: constructor herhangi bir IEnumerable<T> alır ve öğelerini sırayla push eder, stack de önce en üstten dolaşılır, bu yüzden eski en üst kopyanın en altına düşer. Önce diziyi ters çevirmek (LINQ'in Reverse()'ü öğeleri alttan başlayarak döndürür) aynı üste sahip bir kopya verir.

Bir öğe listesini yeni bir stack'e push etmek de onları ters çevirir; bu, bir diziyi ters çevirmenin hızlı bir yoludur: new Stack<char>("hello") geriye o, l, l, e, h olarak pop edilir.

Örnek: bir geri alma geçmişi

Editörler her değişikliği bir stack'te tutar. Geri alma en son değişikliği pop edip geri çevirir; yineleme ise geri alınan değişikliklerden oluşan ikinci bir stack tutar.

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

Çıktı:

Hello, world!
Hello, world
Hello
Hello, world

Tüm anlık görüntüleri saklamak en basit sürümdür. Gerçek editörler bunun yerine, her biri kendini geri çevirecek bir metoda sahip küçük komut nesneleri (ne eklendi ve nereye) push eder, ama iki stack aynı şekilde çalışır.

Örnek: dengeli parantezler

(, [ ve {'nin doğru sırayla kapatıldığını kontrol etmek standart stack alıştırmasıdır ve aynı mantık her derleyicinin ve JSON parser'ının içinde bulunur.

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

Çıktı:

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

Üç başarısızlık kontrolü, parantezlerin bozulabileceği üç yola karşılık gelir: açık hiçbir şey yokken bir kapanış (a)b(, Pop'tan gelen bir istisna yerine Count == 0 ile yakalanır), yanlış türde bir kapanış ((]) ve hiç kapatılmamış açılışlar (((a), son kontrolle yakalanır).

Diğer kullanımlar

• Derinlik öncelikli arama. Genişlik öncelikli bir aramadaki kuyruğu bir stack ile değiştirin, dolaşma genişlemeden önce derine gider. Açık bir stack, girdi yakalanamayan bir StackOverflowException riskine yetecek kadar derin olduğunda özyinelemenin yerini de alır.
• İfadeleri değerlendirmek. Sonek gösterim (3 4 + 2 *), sayıları push edip her operatör için iki tane pop ederek değerlendirilir.
• Geri izleme. Gezinme geçmişi, labirent çözme ve parser durumları bir konumu push eder ve çıkmaza girildiğinde ona geri pop eder.

İlk giren ilk çıkar karşılığı için Queue sayfasına bakın.

Stack, Queue ve List

Birkaç thread için System.Collections.Concurrent içindeki ConcurrentStack<T> lock olmadan Push, TryPop ve TryPeek sunar.

Yaygın hatalar

• Kontrol etmeden Pop yapmak. Boş bir stack InvalidOperationException fırlatır; Count'u kontrol edin ya da TryPop kullanın.
• foreach'in ilk push edilen öğeden başlamasını beklemek. En üstten başlar.
• new Stack<T>(stack) ile kopyalamak. Kopya ters çevrilmiştir.
• Aynı stack üzerindeki foreach içinde Push yapmak. İstisna fırlatır; bir while (stack.Count > 0) döngüsü kullanın.