Stack di C#: Push, Pop, Peek, Undo dan Pencocokan Kurung

Stack<T> adalah sebuah tumpukan: kamu menaruh item di atas dengan Push dan mengambilnya dari atas dengan Pop, jadi item yang terakhir masuk adalah yang pertama keluar (LIFO). Hanya bagian atas yang bisa dijangkau, dan setiap operasi padanya berjalan dalam waktu konstan.

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

Output:

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

green dimasukkan paling akhir, jadi ia keluar paling dulu. Peek mengembalikan item teratas tanpa mengubah stack, dan dengan cara itulah kamu melihat apa yang akan diberikan Pop sebelum memutuskan untuk mengambilnya.

Exception saat stack kosong dan TryPop

Melakukan pop atau peek pada stack kosong melempar InvalidOperationException. Ini paling sering muncul di parser dan algoritma yang menerima input dengan item penutup lebih banyak daripada item pembuka.

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

Output:

Caught InvalidOperationException
True 10
False 0

TryPop dan TryPeek (.NET Core 2.0 dan sesudahnya) mengembalikan false pada stack kosong dan mengisi variabel out dengan nilai default, di sini 0. Di .NET Framework, periksa Count > 0 lebih dulu.

Urutan iterasi: yang teratas lebih dulu

Melakukan enumerasi pada stack tidak menghapus apa pun, dan urutannya dari atas ke bawah, sesuai urutan item yang akan dikembalikan 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());
    }
}

Output:

checkout products home 
checkout > products > home
True
home
checkout

Salinan yang terbalik sering menjebak: constructor-nya menerima IEnumerable<T> apa pun dan melakukan push pada itemnya secara berurutan, sedangkan stack melakukan enumerasi dari atas, jadi item teratas yang lama berakhir di dasar salinannya. Membalik urutannya lebih dulu (Reverse() dari LINQ mengembalikan item mulai dari dasar) menghasilkan salinan dengan item teratas yang sama.

Melakukan push pada daftar item ke stack baru juga membalik urutannya, dan ini cara cepat untuk membalik sebuah urutan: new Stack<char>("hello") mengembalikan o, l, l, e, h saat diambil dengan pop.

Contoh: riwayat undo

Editor menyimpan setiap perubahan di sebuah stack. Undo melakukan pop pada perubahan terbaru lalu membatalkannya; redo menyimpan stack kedua berisi perubahan yang sudah dibatalkan.

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

Output:

Hello, world!
Hello, world
Hello
Hello, world

Menyimpan seluruh snapshot adalah versi yang paling sederhana. Editor sungguhan melakukan push pada object command kecil (apa yang disisipkan, dan di mana), masing-masing dengan method untuk membalikkan dirinya, tetapi kedua stack-nya bekerja dengan cara yang sama.

Contoh: kurung yang seimbang

Memeriksa bahwa (, [, dan { ditutup dengan urutan yang benar adalah latihan stack yang standar, dan logika yang sama ada di dalam setiap compiler dan 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));
        }
    }
}

Output:

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

Ketiga pengecekan kegagalan itu sesuai dengan tiga cara kurung bisa salah: kurung tutup tanpa ada kurung yang terbuka (a)b(, ditangkap oleh Count == 0 alih-alih exception dari Pop), kurung tutup dengan jenis yang salah ((]), dan kurung buka yang tidak pernah ditutup (((a), ditangkap oleh pengecekan terakhir).

Pemakaian lainnya

• Depth first search. Ganti queue di breadth first search dengan stack, maka penelusurannya masuk ke dalam lebih dulu sebelum melebar. Stack eksplisit juga bisa menggantikan rekursi saat input cukup dalam sehingga berisiko memicu StackOverflowException, yang tidak bisa ditangkap.
• Mengevaluasi ekspresi. Notasi postfix (3 4 + 2 *) dievaluasi dengan melakukan push pada angka dan pop dua angka untuk setiap operator.
• Backtracking. Riwayat navigasi, penyelesaian labirin, dan state parser melakukan push pada sebuah posisi lalu kembali ke posisi itu dengan pop saat menemui jalan buntu.

Lihat Queue untuk pasangannya yang first in, first out.

Stack vs Queue vs List

Untuk banyak thread, ConcurrentStack<T> di System.Collections.Concurrent menyediakan Push, TryPop, dan TryPeek tanpa lock.

Kesalahan umum

• Melakukan pop tanpa memeriksa. Stack kosong melempar InvalidOperationException; periksa Count atau pakai TryPop.
• Mengira foreach dimulai dari item yang pertama dimasukkan. Urutannya dimulai dari atas.
• Menyalin dengan new Stack<T>(stack). Salinannya terbalik.
• Melakukan push di dalam foreach pada stack yang sama. Ini melempar exception; pakai perulangan while (stack.Count > 0).