[C#] System.Collections.Generic.Stack<T> — 型安全な LIFO スタックの仕組みと使いどころ

System.Collections.Generic.Stack<T> は、型安全な LIFO（後入れ先出し）コレクション です。.NET 2.0 で非ジェネリック版 System.Collections.Stack を置き換える形で導入され、現代の C# でスタックと言えば実質的にこの型を指します。

`Stack<T>` とは

名前空間：System.Collections.Generic
内部構造：T[] バッファ + _size。容量超過時は 2 倍に拡張
API は Push／Pop／Peek の 3 つが中心
値型もボックス化なしで格納可能

var stack = new Stack<string>();
stack.Push("first");
stack.Push("second");
stack.Push("third");

string top = stack.Peek(); // "third"
string pop = stack.Pop();  // "third"

サポートするインターフェース

インターフェース	役割
`IEnumerable<T>`	`foreach` でトップから底へ列挙
`IReadOnlyCollection<T>`	読み取り専用の `Count`
`ICollection`	非ジェネリック互換（`CopyTo` / 同期サポート）
`IEnumerable`	非ジェネリック互換

Queue<T> 同様に IList<T> も ICollection<T> も実装しません。「先頭の追加・取り出し」しかしないという LIFO のセマンティクスを API 表面に明示する設計です。

各インターフェースの詳細は次を参照してください。

ICollection: ArrayList の記事
IEnumerable<T> / IEnumerator<T>: IEnumerable と IEnumerator の記事

`foreach` の列挙順に注意

非ジェネリック版と同じく、foreach は 最後に Push した要素から順 に取り出します。

var s = new Stack<int>();
s.Push(1); s.Push(2); s.Push(3);
foreach (var x in s) Console.Write($"{x} "); // 3 2 1

底から順に並べたい場合は ToArray() も同じ順序なので Reverse() を挟むか、Pop で取り出した後に Reverse してください。

主な API と計算量

操作	API	計算量
プッシュ	`Push(item)`	O(1) 償却
ポップ	`Pop()`	O(1)
トップ参照	`Peek()`	O(1)
安全な取り出し	`TryPop(out item)`	O(1)
安全な参照	`TryPeek(out item)`	O(1)
含有判定	`Contains(item)`	O(n)
列挙	`foreach`	O(n)
配列化	`ToArray()`	O(n)
容量縮小	`TrimExcess()`	O(n)

Pop / Peek は空のスタックに対して InvalidOperationException。.NET Core 2.0+ の TryPop / TryPeek を使えば例外を回避できます。

while (stack.TryPop(out var item))
    Process(item);

非ジェネリック `Stack` との比較

観点	`Stack<T>`	`Stack`
型安全	◯	× `object`
値型のボックス化	なし	あり
`TryPop` / `TryPeek`	あり	なし
推奨	標準	レガシー

新規コードで非ジェネリック版を選ぶ理由はありません。

並行版 — `ConcurrentStack<T>`

Stack<T> はスレッドセーフではありません。並行アクセスが必要なら System.Collections.Concurrent.ConcurrentStack<T> を使います。PushRange / TryPopRange でまとめてプッシュ／ポップできるのが特徴です。

var stack = new System.Collections.Concurrent.ConcurrentStack<int>();
stack.PushRange(new[] { 1, 2, 3 });
var buffer = new int[3];
int popped = stack.TryPopRange(buffer);

使いどころ

1. 深さ優先探索（DFS）

Queue<T> を使った BFS と対になる典型例。

static IEnumerable<TNode> Dfs<TNode>(TNode start, Func<TNode, IEnumerable<TNode>> children)
    where TNode : notnull
{
    var visited = new HashSet<TNode>();
    var stack   = new Stack<TNode>();
    stack.Push(start);

    while (stack.TryPop(out var node))
    {
        if (!visited.Add(node)) continue;
        yield return node;
        foreach (var c in children(node)) stack.Push(c);
    }
}

再帰実装でも DFS は書けますが、スタックオーバーフローが心配な深さ や 明示的に状態を保持したい ときは反復実装の Stack<T> が安全です。

2. Undo / Redo

var undo = new Stack<ICommand>();
var redo = new Stack<ICommand>();

void Execute(ICommand cmd) { cmd.Do();   undo.Push(cmd); redo.Clear(); }
void Undo()                { if (undo.TryPop(out var c)) { c.Undo(); redo.Push(c); } }
void Redo()                { if (redo.TryPop(out var c)) { c.Do();   undo.Push(c); } }

3. 括弧の対応・式の評価

逆ポーランド記法、括弧対応チェック、HTML/XML の開閉タグ検証など。

static bool IsBalanced(string s)
{
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else if (c is ')' or ']' or '}')
        {
            if (!stack.TryPop(out var open)) return false;
            if (!Match(open, c)) return false;
        }
    }
    return stack.Count == 0;

    static bool Match(char o, char c) =>
        (o == '(' && c == ')') || (o == '[' && c == ']') || (o == '{' && c == '}');
}

4. バックトラッキング

迷路探索、N クイーン、パズルソルバなど、「進んだ → 行き止まり → 戻る」を表現する用途。再帰の代わりに Stack<T> で明示的に状態を持たせると、デバッグもキャンセルもしやすくなります。

向かないケース

任意位置の参照や検索が必要 → List<T>
両端への追加・削除 → LinkedList<T>、または Deque 的に使う List<T>
シンプルな FIFO → Queue<T>
並行アクセス → ConcurrentStack<T>

注意点

foreach はトップから底の順。底から順を期待すると間違う。
列挙中の変更は例外。
スレッドセーフではない。

まとめ

Stack<T> は 型安全な LIFO。内部は動的配列で Push/Pop/Peek が O(1)。
IEnumerable<T> / IReadOnlyCollection<T> を実装。IList<T>/ICollection<T> は実装しない。
TryPop / TryPeek で空判定をアトミックに。
DFS、Undo/Redo、括弧対応、再帰の反復化が代表的な使いどころ。並行アクセスには ConcurrentStack<T>。

Stack<T> とは