スタックを利用するには？［C#／VB］：.NET TIPS

.NET Frameworkが提供するStack<T>クラスの基本的な使い方と注意点を説明する。また、List<T>クラスを使ったスタックの独自実装コードも紹介する。

» 2018年02月14日 05時00分公開

[山本康彦，BluewaterSoft／Microsoft MVP for Windows Development]

　スタック（積み重ね）とは、入れたものが入れたときとは逆の順で出てくるコレクションのことだ。「後入れ先出し」（LIFO、"Last in, First out"）のコレクションともいう。スタックを実現するには、配列やList<T>コレクション（System.Collections.Generic名前空間）などを使って実装することも可能だが、.NET Framework 2.0以降ではStack<T>コレクション（System.Collections.Generic名前空間）を利用するとよい。

　本稿では、Stack<T>コレクションの基本的な使い方とスタックのサイズを制限する方法を解説する。

POINT　Stack<T>コレクションの基本的な使い方

Stack<T>コレクションの基本的な使い方まとめ

　特定のトピックをすぐに知りたいという方は以下のリンクを活用してほしい。

Stackの基本的な使い方とは？
コレクションを与えて初期化したときの格納順は？
スタックの下端を削除してサイズを制限するには？

　なお、本稿に掲載したサンプルコードをそのまま試すにはVisual Studio 2015以降が必要である。サンプルコードはコンソールアプリの一部であり、コードの冒頭に以下の宣言が必要となる。

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

Imports System.Console

本稿のサンプルコードに必要な宣言（上：C#、下：VB）

Stackの基本的な使い方とは？

　スタックに対する基本的な操作は、「スタックにデータをぎゅっと押し込む」（push）／「スタックからデータをぽんと取り出す」（pop）／「一番上にあるデータを見る」（peek）の3つだ。Stack<T>コレクションは、それらを次の3つのメソッドとして実装している。

Pushメソッド：スタックの上端にデータを追加する
Popメソッド：スタックの上端からデータを取り出す
Peekメソッド：スタックの上端のデータを読み取る（取り出さない）

　Pushメソッドでデータをスタックの上端に追加するとき、スタックに空きがなければ自動的にスタックのサイズが拡張される。

　この他に、Stack<T>コレクションにはスタックに入っているデータの数を返すCountプロパティもある。スタックにデータが入っていないときにPop／Peekメソッドを呼び出すと例外が出るので、呼び出す前にCountプロパティをチェックすべきである。また、Stack<T>コレクションはIEnumerable<T>インタフェース（System.Collections.Generic名前空間）を実装しているので、LINQ拡張メソッドも利用できる。

　Stack<T>コレクションはスレッドセーフではない。非同期／並列処理でStack<T>コレクションにアクセスするにはスレッド間の排他処理が必要になる。その手法はキューと同様なので、次のTIPSを参照していただきたい。

　Stack<T>コレクションの基本的な使い方の例を示す（次のコード）。

static void Main(string[] args)
{
// 文字列を格納するスタック
var stack = new Stack<string>();

// スタックに"A"／"B"／"C"と順に投入
stack.Push("A");
stack.Push("B");
stack.Push("C");

// スタックから全てを取り出す
while (stack.Count > 0)
{
    WriteLine($"スタックの先頭を見る：{stack.Peek()}");
    WriteLine($"スタックの内容：{stack.Count}個");

    string s = stack.Pop();
    WriteLine($"スタックから取り出し：{s}");
    WriteLine($"スタックの内容：{stack.Count}個");
}
// 出力：
// スタックの先頭を見る：C
// スタックの内容：3個
// スタックから取り出し：C
// スタックの内容：2個
// スタックの先頭を見る：B
// スタックの内容：2個
// スタックから取り出し：B
// スタックの内容：1個
// スタックの先頭を見る：A
// スタックの内容：1個
// スタックから取り出し：A
// スタックの内容：0個

#if DEBUG
ReadKey();
#endif
}

Sub Main()
' 文字列を格納するスタック
Dim stack = New Stack(Of String)()

' スタックに"A"／"B"／"C"と順に投入
stack.Push("A")
stack.Push("B")
stack.Push("C")

' スタックから全てを取り出す
While (stack.Count > 0)
    WriteLine($"スタックの先頭を見る：{stack.Peek()}")
    WriteLine($"スタックの内容：{stack.Count}個")

    Dim s As String = stack.Pop()
    WriteLine($"スタックから取り出し：{s}")
    WriteLine($"スタックの内容：{stack.Count}個")
End While
' 出力：
' スタックの先頭を見る：C
' スタックの内容：3個
' スタックから取り出し：C
' スタックの内容：2個
' スタックの先頭を見る：B
' スタックの内容：2個
' スタックから取り出し：B
' スタックの内容：1個
' スタックの先頭を見る：A
' スタックの内容：1個
' スタックから取り出し：A
' スタックの内容：0個

#If DEBUG Then
ReadKey()
#End If
End Sub

Stack<T>コレクションの基本的な使い方の例（上：C#、下：VB）
Pushメソッドを使って文字列の"A"、"B"、"C"を順にスタックに投入している。その後、Popメソッドを使ってスタックから1つずつ取り出すと、投入したときとは逆の順で"C"、"B"、"A"と出てくる。なお、Peekメソッドは、得られる値はPopメソッドと同じだが、Popメソッドとは違ってそのデータはスタックに残ったままになる（スタックに入っている個数が変化しない）。

　Stack<T>コレクションのIEnumerable<T>インタフェースとLINQ拡張メソッドを利用する例を示す（次のコード）。Stack<T>コレクションには最後の要素を読み取るメソッドは用意されていないが、LINQのLast拡張メソッドを使えばよいのである。

// 文字列を格納するスタック
var stack = new Stack<string>();
// スタックに"A"／"B"／"C"と順に投入
stack.Push("A");
stack.Push("B");
stack.Push("C");

WriteLine($"IEnumerable<string>：スタックの内容：{string.Join(", ", stack)}");
// 出力：IEnumerable<string>：スタックの内容：C, B, A
WriteLine($"LINQ：スタックの最後の要素：{stack.Last()}");
// 出力：LINQ：スタックの最後の要素：A
WriteLine($@"LINQ：小文字に変換：{string.Join(", ",
stack.Select(s => s.ToLowerInvariant()))}");
// 出力：LINQ：小文字に変換：c, b, a

' 文字列を格納するスタック
Dim stack = New Stack(Of String)()
' スタックに"A"／"B"／"C"と順に投入
stack.Push("A")
stack.Push("B")
stack.Push("C")

WriteLine($"IEnumerable<String>：スタックの内容：{String.Join(", ", stack)}")
' 出力：IEnumerable<String>：スタックの内容：C, B, A
WriteLine($"LINQ：スタックの最後の要素：{stack.Last()}")
' 出力：LINQ：スタックの最後の要素：A
WriteLine($"LINQ：小文字に変換：{String.Join(", ",
stack.Select(Function(s) s.ToLowerInvariant()))}")
' 出力：LINQ：小文字に変換：c, b, a

Stack<T>コレクションのIEnumerable<T>インタフェースを利用する例（上：C#、下：VB）
IEnumerable<T>インタフェースを実装しているので、StringクラスのJoinメソッドの引数として使える。もちろんforeach（C#）／For Each（VB）ステートメントを使ってスタックの内容を順に読み取ることも可能だ。
LINQ拡張メソッドが使えるので、スタックの末尾を読み取ったり、スタックの全要素に同じ処理を加えたりなど、LINQ拡張の多様な機能も利用できる。

コレクションを与えて初期化したときの格納順は？

　Stack<T>クラスをインスタンス化するときに、他のコレクションを与えることもできる。そのときの格納順は、与えたコレクションとは逆順になるので注意してほしい。元のコレクションの先頭にあるデータから順にPushしていったのと同じ結果になるのだ（次のコード）。

// スタックの初期化時にコレクションを与える
int[] data = { 1, 2, 3,};
var stack = new Stack<int>(data);
WriteLine($"スタックの内容：{string.Join(", ", stack)}");
// 出力：スタックの内容：3, 2, 1

' スタックの初期化時にコレクションを与える
Dim data() As Integer = {1, 2, 3}
Dim stack = New Stack(Of Integer)(data)
WriteLine($"スタックの内容：{String.Join(", ", stack)}")
' 出力：スタックの内容：3, 2, 1

既存のコレクションを与えてStackを初期化する例（上：C#、下：VB）
整数の配列（内容は1、2、3）をStack<T>クラスのコンストラクタに与えた。スタックの内容を表示させると逆順の3、2、1になっている。これは、与えたコレクションの先頭の1から順にスタックへPushした形になっている。

スタックの下端を削除してサイズを制限するには？

　スタックは、キューと同様にしてデータの受け渡しに使う他に、履歴を保持しておいてundo（元に戻す）／redo（やり直し）を実現するためにもよく使われる。ユーザーの操作履歴や画面の遷移履歴などだ。履歴の場合は（データの受け渡しとは異なり）、スタックのサイズが増え続ける。一定のサイズを超えたら古いデータを削除する処理が必要になってくるのだ。

　スタックから要素を削除する方法はPopメソッド（上端を1つ削除する）しか用意されていない。そこで、下端を削除するには、いったん別のコレクションにコピーし、削除してから新しいスタックを作ればよい（次のコード）。前述したようにコレクションを渡してスタックを初期化するときは逆順になるので、その点は注意する必要がある。

var stack = new Stack<string>();
stack.Push("A");
stack.Push("B");
stack.Push("C");
WriteLine($"スタックの内容：{string.Join(", ", stack)}");
// 出力：スタックの内容：C, B, A

stack = new Stack<string>(stack.Reverse().Skip(1));
// C,B,A
// ↓ Reverse
// A,B,C
// ↓ Skip(1)
// B,C
// ↓ 新しいStackをインスタンス化（順にPushされる）
// C,B
WriteLine($"スタックの内容：{string.Join(", ", stack)}");
// 出力：スタックの内容：C, B

Dim stack = New Stack(Of String)()
stack.Push("A")
stack.Push("B")
stack.Push("C")
WriteLine($"スタックの内容：{String.Join(", ", stack)}")
' 出力：スタックの内容：C, B, A

stack = New Stack(Of String)(stack.Reverse().Skip(1))
' C,B,A
' ↓ Reverse
' A,B,C
' ↓ Skip(1)
' B,C
' ↓ 新しいStackをインスタンス化（順にPushされる）
' C,B
WriteLine($"スタックの内容：{String.Join(", ", stack)}")
' 出力：スタックの内容：C, B

Stackの下端の要素を1つ削除する例（上：C#、下：VB）
1つ追加するごとに1つ削除していたのではスタックの再作成が毎回発生してしまうので、実際には例えば最大容量の半分をまとめて削除するなどを行う。
その実装方法もいろいろと考えられるが、ここではLINQ拡張のReverseとSkipを使って1つ削除したコレクションを作り、それをStack<T>クラスのコンストラクタに渡している。それによってどのようにデータが変化するかを、コメントに記しておいた。

　このようにStack<T>クラスの使い勝手が少々よくないのは、データの受け渡しに使うことを主に考えてのことだと想像されるが、内部的に配列で実装されているからだ（公式ドキュメントに「implemented as an array」と明記されている）。配列なのでコンパクトで高速にアクセスできるが、途中の要素の削除はできないのである。そこで、履歴に使うのであれば、発想を切り替えて自前のコレクションを作ってしまってもよい。そのようなMyStack<T>クラスの例を、参考までにC#だけであるが掲載しておく（次のコード）。

public class MyStack<T> : IEnumerable<T>
{
const int DEFAULT_CAPACITY = 10; // 最大サイズの既定値
private readonly int MAX_COUNT; // 最大サイズ（コンストラクタで指定する）
private LinkedList<T> _list = new LinkedList<T>(); // データ格納用コレクション

// コンストラクタ（引数なしのものと、引数にサイズを指定するもの）
public MyStack(){ MAX_COUNT = DEFAULT_CAPACITY; }
public MyStack(int capacity){ MAX_COUNT = capacity; }

// Capacityプロパティ：最大サイズを返す
public int Capacity => MAX_COUNT;
// Countプロパティ：格納しているデータの個数を返す（Stack<T>と同名）
public int Count => _list.Count;

// Pushメソッド（Stack<T>と同名）
public void Push(T item)
{
    _list.AddFirst(item);
    if (_list.Count > MAX_COUNT)
      _list.RemoveLast();
}
// Peekメソッド（Stack<T>と同名）
public T Peek() => _list.First();
// Popメソッド（Stack<T>と同名）
public T Pop()
{
    var item = _list.First();
    _list.RemoveFirst();
    return item;
}

// IEnumerable<T>の実装
public IEnumerator<T> GetEnumerator() => ((IEnumerable<T>)_list).GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)_list).GetEnumerator();
}

……省略……

// コンソールアプリ内での使用例

var stack = new MyStack<string>(3);
WriteLine($"スタックに入っている個数：{stack.Count}");
// 出力：スタックに入っている個数：0
WriteLine($"スタックの最大容量：{stack.Capacity}");
// 出力：スタックの最大容量：3

// スタックに"A"／"B"／"C"と順に投入
stack.Push("A"); stack.Push("B"); stack.Push("C");
WriteLine($"スタックの内容：{string.Join(", ", stack)}（{stack.Count}個）");
// 出力：スタックの内容：C, B, A（3個）

// スタックに"D"を投入（一番下の"A"は消える）
stack.Push("D");
WriteLine($"スタックの内容：{string.Join(", ", stack)}（{stack.Count}個）");
// 出力：スタックの内容：D, C, B（3個）

// スタックから全てを取り出す
while (stack.Count > 0)
{
WriteLine($"スタックの先頭を見る：{stack.Peek()}");
string s = stack.Pop();
WriteLine($"スタックから取り出し：{s}");
WriteLine($"スタックの内容：{string.Join(", ", stack)}（{stack.Count}個）");
}
// 出力：
// スタックの先頭を見る：D
// スタックから取り出し：D
// スタックの内容：C, B（2個）
// スタックの先頭を見る：C
// スタックから取り出し：C
// スタックの内容：B（1個）
// スタックの先頭を見る：B
// スタックから取り出し：B
// スタックの内容：（0個）

……省略……

下端が自動的に削除されるスタックの実装例（C#）
ここではLinkedList<T>クラス（System.Collections.Generic名前空間）を使って実装してみた。Pushされたときは、AddFirstメソッドで上端に挿入し、それで最大サイズを超えた場合にはRemoveLastメソッドで下端の要素を削除している。