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。这种情况最常出现在解析器和算法中：输入里的闭合项比开启项还多。

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> 并按顺序压入其中的元素，而栈枚举时栈顶在前，所以原来的栈顶最终落到了副本的底部。先把序列反转（LINQ 的 Reverse() 会从栈底开始返回元素），得到的副本栈顶就和原来一样了。

把一组元素压入一个新栈也会把它们反转，这是反转序列的一个快捷方法：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 *）的求值方法是：遇到数字就压入，遇到运算符就弹出两个数。
• 回溯。 浏览历史、走迷宫和解析器状态都会压入一个位置，遇到死路时再弹回到这个位置。

先进先出的对应数据结构见 Queue。

Stack、Queue 与 List 对比

多线程场景下，System.Collections.Concurrent 中的 ConcurrentStack<T> 提供了无需加锁的 Push、TryPop 和 TryPeek。

常见错误

• 弹出前不做检查。 空栈会抛出 InvalidOperationException；检查 Count 或使用 TryPop。
• 以为 foreach 会从第一个压入的元素开始。 它是从栈顶开始的。
• 用 new Stack<T>(stack) 复制栈。 得到的副本是反的。
• 在遍历同一个栈的 foreach 中压入元素。 会抛出异常；请使用 while (stack.Count > 0) 循环。