実行できるC#ドキュメント: Stack

Q: C#のStackとは何ですか？

System.Collections.Generic の Stack は、後入れ先出し（LIFO）のコレクションです。Push は一番上に要素を置き、Pop は一番上の要素を削除して返し、Peek は一番上の要素を削除せずに返します。3つとも定数時間で動きます。

Q: C#で空のスタックにPopするとどうなりますか？

スタックが空だと、Pop と Peek は InvalidOperationException を投げます。先に stack.Count > 0 を確認するか、例外を投げずに false を返す TryPop(out var item) と TryPeek(out var item) を使います（.NET Core 2.0以降）。

Q: foreachはStackをどの順序でたどりますか？

上から下へです。最後にプッシュした要素が最初に来て、Pop が返すのと同じ順序になります。ToArray() も同じ順序です。その結果、new Stack (otherStack) は逆順のコピーを作ります。コンストラクターは列挙した順に要素をプッシュするからです。

Q: C#のStackとQueueの違いは何ですか？

Stack は最も新しい要素を最初に返し（後入れ先出し）、Queue は最も古い要素を最初に返します（先入れ先出し）。元に戻す履歴、入れ子の構造、深さ優先探索にはスタックを、到着順の処理と幅優先探索にはキューを使います。

Q: C#でかっこの対応をチェックするには？

文字列を1回走査します。開きかっこはすべて Stack にプッシュします。閉じかっこでは、スタックが空でなく、その一番上が対応する開きかっこでなければならず、それをポップします。走査が終わったときにスタックが空なら、対応が取れています。

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> を受け取って要素を順にプッシュし、スタックは上から列挙されるので、元の一番上がコピーの一番下になります。先にシーケンスを反転させる（LINQの Reverse() は要素を下から返します）と、一番上が同じコピーになります。

要素のリストを新しいスタックにプッシュしても逆順になるので、シーケンスを手早く反転する方法になります：new Stack<char>("hello") は o, l, l, e, h の順にポップされます。

例：元に戻す履歴

エディターはすべての変更をスタックに保持します。元に戻す操作は最新の変更をポップして戻し、やり直しは元に戻した変更を2つ目のスタックに保持します。

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

スナップショット全体を保存するのが最も単純な版です。実際のエディターは代わりに、自分自身を元に戻すメソッドを持つ小さなコマンドオブジェクト（何をどこに挿入したか）をプッシュしますが、2つのスタックの仕組みは同じです。

例：かっこの対応

(、[、{ が正しい順序で閉じられているかを確認するのは、スタックの標準的な練習問題で、同じ論理がすべてのコンパイラや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

3つの失敗のチェックは、かっこがおかしくなる3つのパターンに対応しています。何も開いていないのに閉じかっこがある（a)b(、Pop の例外ではなく Count == 0 で検出）、種類の違う閉じかっこ（(]）、閉じられていない開きかっこ（((a)、最後のチェックで検出）です。

その他の用途

深さ優先探索。 幅優先探索のキューをスタックに置き換えると、走査は広く進む前に深く進みます。明示的なスタックは、キャッチできない StackOverflowException の危険があるほど入力が深いときに、再帰の代わりにもなります。
式の評価。 後置記法（3 4 + 2 *）は、数値をプッシュし、演算子ごとに2つをポップして評価します。
バックトラッキング。 ナビゲーションの履歴、迷路の解法、パーサーの状態では、位置をプッシュし、行き止まりでそこまでポップして戻ります。

先入れ先出しの対になるものはQueueを参照してください。

Stack、Queue、Listの比較

	`Stack<T>`	`Queue<T>`	`List<T>`
取り出す順序	最新のものから	最古のものから	任意、インデックスで
追加	`Push`	`Enqueue`	`Add`、`Insert`
削除	`Pop`（一番上）	`Dequeue`（先頭）	`Remove`、`RemoveAt`
見る	`Peek`	`Peek`	`list[i]`
安全な版	`TryPop`、`TryPeek`	`TryDequeue`、`TryPeek`	不要

複数のスレッドには、System.Collections.Concurrent の ConcurrentStack<T> が、ロックなしで Push、TryPop、TryPeek を提供します。

よくある間違い

確認せずにポップする。 空のスタックは InvalidOperationException を投げます。Count を確認するか、TryPop を使います。
foreach が最初にプッシュした要素から始まると思う。 一番上から始まります。
new Stack<T>(stack) でコピーする。 コピーは逆順になります。
同じスタックを foreach している最中にプッシュする。 例外が投げられます。while (stack.Count > 0) ループを使います。

よくある質問

C#のStackとは何ですか？

System.Collections.Generic の Stack<T> は、後入れ先出し（LIFO）のコレクションです。Push は一番上に要素を置き、Pop は一番上の要素を削除して返し、Peek は一番上の要素を削除せずに返します。3つとも定数時間で動きます。

C#で空のスタックにPopするとどうなりますか？

スタックが空だと、Pop と Peek は InvalidOperationException を投げます。先に stack.Count > 0 を確認するか、例外を投げずに false を返す TryPop(out var item) と TryPeek(out var item) を使います（.NET Core 2.0以降）。

foreachはStackをどの順序でたどりますか？

上から下へです。最後にプッシュした要素が最初に来て、Pop が返すのと同じ順序になります。ToArray() も同じ順序です。その結果、new Stack<T>(otherStack) は逆順のコピーを作ります。コンストラクターは列挙した順に要素をプッシュするからです。

C#のStackとQueueの違いは何ですか？

Stack<T> は最も新しい要素を最初に返し（後入れ先出し）、Queue<T> は最も古い要素を最初に返します（先入れ先出し）。元に戻す履歴、入れ子の構造、深さ優先探索にはスタックを、到着順の処理と幅優先探索にはキューを使います。

C#でかっこの対応をチェックするには？

文字列を1回走査します。開きかっこはすべて Stack<char> にプッシュします。閉じかっこでは、スタックが空でなく、その一番上が対応する開きかっこでなければならず、それをポップします。走査が終わったときにスタックが空なら、対応が取れています。