[C#] System.Collections.Stack — 非ジェネリックな LIFO スタックの仕組みと使いどころ

System.Collections.Stack は、.NET Framework 1.0 から提供されている 非ジェネリックな LIFO（後入れ先出し）コレクション です。Stack<T>（.NET 2.0+）に主役を譲りましたが、本記事では System.Collections シリーズの締めくくりとして整理します。

`Stack` とは

名前空間：System.Collections
内部構造：object[] バッファ + size。容量超過時は 2 倍に拡張
要素の型は object、値型はボックス化
API は Push／Pop／Peek の 3 つが中心

using System.Collections;

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

string top = (string)stack.Peek()!; // "third"（取り出さない）
string pop = (string)stack.Pop()!;  // "third"（取り出す）

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

インターフェース	役割
`ICollection`	`Count` / `CopyTo` / 同期サポート
`IEnumerable`	`foreach` でトップから底へ列挙（最後に Push したものから順）
`ICloneable`	`Clone()` で浅いコピー

Queue 同様に IList は実装しません。任意位置のアクセスや挿入・削除をサポートしないコレクション だからです。これは Stack の「先頭の追加／取り出ししかできない」セマンティクスを反映しています。

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

ICollection: ArrayList の記事
IEnumerable / IEnumerator: IEnumerable と IEnumerator の記事
ICloneable: ICloneable インターフェースの記事

Stack.Clone() は配列バッファを新しく確保する 浅いコピー です。

`foreach` の列挙順に注意

Stack を foreach で回すと、最後に Push した要素から順 に取り出されます。

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

Pop() を繰り返したのと同じ順序です。これに気付かずに「底から順」を期待すると順序が逆転するので注意します。底から順に並べたいときは ToArray() も同様に「トップから底」順なので Reverse() してください。

主な API と計算量

操作	API	計算量	備考
プッシュ	`Push(obj)`	O(1) 償却	容量超過時のみ O(n)
ポップ	`Pop()`	O(1)
トップ参照	`Peek()`	O(1)	取り出さない
含有判定	`Contains(obj)`	O(n)	線形探索
列挙	`foreach`	O(n)	トップから底へ
配列化	`ToArray()`	O(n)	トップから底の順

Pop() / Peek() を空のスタックに対して呼ぶと InvalidOperationException。Count 確認、または Stack<T>.TryPop / TryPeek（ジェネリック版にのみある）を使います。

ボックス化のコスト

値型を扱うと Push と Pop の両方 でボックス化／アンボックス化が発生します。

var s = new Stack();
for (int i = 0; i < 1_000_000; i++) s.Push(i); // 100 万回ボックス化

while (s.Count > 0)
{
    int x = (int)s.Pop()!; // アンボックス化 + キャスト
}

ヒープ割り当てと GC 圧、キャスト命令のコストが積み上がるため、Stack<T> を使うのが現代の標準 です。

`Stack<T>` との比較

観点	`Stack`	`Stack<T>`
型安全	× `object` のキャスト	◯
値型のボックス化	発生	発生しない
推奨度	レガシー	新規コードの標準
API	`Push`/`Pop`/`Peek`	同上＋`TryPop`/`TryPeek`

並行アクセスが必要なら System.Collections.Concurrent.ConcurrentStack<T> を使います。Stack.Synchronized(stack) ラッパもありますが、粒度が粗く現代では推奨されません。

使いどころ

1. 深さ優先探索（DFS）

Queue での BFS と対になる典型例。

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

    while (stack.Count > 0)
    {
        var node = stack.Pop();
        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()                { var c = undo.Pop(); c.Undo(); redo.Push(c); }
void Redo()                { var c = redo.Pop(); 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.Count == 0) return false;
            char open = stack.Pop();
            if (!Match(open, c)) return false;
        }
    }
    return stack.Count == 0;

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

4. バックトラッキング・再帰の反復化

迷路探索やパズルソルバーで「進んだ → 行き止まり → 戻る」を表現するときに、現在地・選択肢を Stack<T> に積んで明示的に管理します。

向かないケース

任意位置の参照や検索が頻繁 → List<T> のほうが向く
先頭・末尾どちらにも入れる／取り出す → LinkedList<T> か Deque 的に使える List<T>
並行アクセス → ConcurrentStack<T> を使う

まとめ

Stack は 非ジェネリックな LIFO。内部は動的配列で Push/Pop/Peek が O(1)。
ICollection / IEnumerable / ICloneable を実装。IList は実装しない。
foreach は トップから底へ 列挙される点に注意。
値型はボックス化されるため、新規コードでは Stack<T> 一択、並行なら ConcurrentStack<T>。
DFS、Undo/Redo、括弧対応、再帰の反復化など 「最後にやったことから戻したい」 場面の定番ツール。

これで System.Collections の主要 6 クラス（ArrayList / BitArray / Hashtable / Queue / SortedList / Stack）を一通り整理しました。実務ではほぼジェネリック版（System.Collections.Generic）を使うことになりますが、内部実装の発想や API の系譜は今もそのまま生きています。次は System.Collections.Specialized や System.Collections.Generic の世界に踏み込んでいきます。

Stack とは