Stack trong C#: Push, Pop, Peek, hoàn tác và kiểm tra dấu ngoặc

Stack<T> là một chồng: bạn đặt phần tử lên trên bằng Push và lấy chúng ra từ trên cùng bằng Pop, nên phần tử vào sau cùng sẽ ra đầu tiên (LIFO). Chỉ có đỉnh là truy cập được, và mọi thao tác trên đỉnh đều mất thời gian hằng số.

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

Đầu ra:

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

green được push sau cùng nên được lấy ra đầu tiên. Peek trả về đỉnh mà không thay đổi stack, đó là cách bạn xem Pop sẽ trả về gì trước khi quyết định lấy nó.

Ngoại lệ khi stack rỗng và TryPop

Pop hoặc peek một stack rỗng sẽ ném InvalidOperationException. Lỗi này hay xuất hiện nhất trong các parser và thuật toán nhận đầu vào có nhiều phần tử đóng hơn phần tử mở.

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

Đầu ra:

Caught InvalidOperationException
True 10
False 0

TryPop và TryPeek (từ .NET Core 2.0) trả về false khi stack rỗng và đặt biến out về giá trị mặc định, ở đây là 0. Trên .NET Framework, hãy kiểm tra Count > 0 trước.

Thứ tự duyệt: đỉnh trước

Duyệt một stack không lấy phần tử nào ra, và nó đi từ đỉnh xuống, theo đúng thứ tự mà Pop sẽ trả về các phần tử:

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

Đầu ra:

checkout products home 
checkout > products > home
True
home
checkout

Bản sao bị đảo ngược hay khiến người ta bất ngờ: hàm khởi tạo nhận bất kỳ IEnumerable<T> nào và push các phần tử theo thứ tự, mà stack lại được duyệt từ đỉnh, nên đỉnh cũ rơi xuống đáy của bản sao. Đảo ngược dãy trước (Reverse() của LINQ trả về các phần tử từ đáy lên) sẽ cho bản sao có cùng đỉnh.

Push một danh sách phần tử vào stack mới cũng đảo ngược chúng, đây là cách nhanh để đảo một dãy: new Stack<char>("hello") pop ra lần lượt o, l, l, e, h.

Ví dụ: lịch sử hoàn tác

Trình soạn thảo lưu mọi thay đổi trên một stack. Hoàn tác (undo) pop thay đổi gần nhất và khôi phục lại; làm lại (redo) giữ một stack thứ hai chứa các thay đổi đã hoàn tác.

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

Đầu ra:

Hello, world!
Hello, world
Hello
Hello, world

Lưu toàn bộ bản chụp là phiên bản đơn giản nhất. Các trình soạn thảo thật push những đối tượng lệnh nhỏ (đã chèn gì, ở đâu), mỗi đối tượng có một phương thức để tự đảo ngược, nhưng hai stack vẫn hoạt động theo cùng một cách.

Ví dụ: dấu ngoặc cân bằng

Kiểm tra (, [ và { có được đóng đúng thứ tự hay không là bài tập stack tiêu chuẩn, và logic tương tự nằm bên trong mọi trình biên dịch và 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));
        }
    }
}

Đầu ra:

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

Ba phép kiểm tra lỗi tương ứng với ba cách dấu ngoặc có thể sai: một dấu đóng khi không có gì đang mở (a)b(, được bắt bằng Count == 0 thay vì ngoại lệ từ Pop), một dấu đóng sai loại ((]), và dấu mở không bao giờ được đóng (((a), được bắt bằng phép kiểm tra cuối cùng).

Các ứng dụng khác

• Tìm kiếm theo chiều sâu. Thay queue trong tìm kiếm theo chiều rộng bằng một stack và việc duyệt sẽ đi sâu trước khi đi rộng. Một stack tường minh cũng thay được đệ quy khi đầu vào đủ sâu để có nguy cơ gây StackOverflowException, ngoại lệ không thể bắt được.
• Tính giá trị biểu thức. Ký pháp hậu tố (3 4 + 2 *) được tính bằng cách push các số và pop hai số cho mỗi toán tử.
• Quay lui (backtracking). Lịch sử điều hướng, giải mê cung và trạng thái parser đều push một vị trí rồi pop để quay lại khi gặp ngõ cụt.

Xem Queue để biết cấu trúc vào trước, ra trước tương ứng.

Stack, Queue và List

Với nhiều luồng, ConcurrentStack<T> trong System.Collections.Concurrent cung cấp Push, TryPop và TryPeek mà không cần khóa.

Lỗi thường gặp

• Pop mà không kiểm tra. Stack rỗng sẽ ném InvalidOperationException; hãy kiểm tra Count hoặc dùng TryPop.
• Tưởng foreach bắt đầu từ phần tử được push đầu tiên. Nó bắt đầu từ đỉnh.
• Sao chép bằng new Stack<T>(stack). Bản sao bị đảo ngược.
• Push bên trong foreach trên chính stack đó. Sẽ ném ngoại lệ; hãy dùng vòng lặp while (stack.Count > 0).