配列&コレクション

[C#] Stackクラスの使い方をわかりやすく解説

Stackクラスは、LIFO(Last In, First Out)方式でデータを管理するコレクションです。

要素を追加する際はPush()メソッドを使い、取り出す際はPop()メソッドを使用します。

Peek()メソッドを使うと、スタックの一番上の要素を削除せずに取得できます。

スタックが空かどうかはCountプロパティやAny()メソッドで確認できます。

スタックは、再帰的な処理や逆順処理などに便利です。

目次から探す

Stackクラスとは

Stackクラスは、C#におけるデータ構造の一つで、LIFO(Last In, First Out)方式で要素を管理します。

つまり、最後に追加された要素が最初に取り出される特性を持っています。

この特性により、スタックは特定のアルゴリズムや処理において非常に便利です。

例えば、関数の呼び出し履歴や、ブラウザの戻るボタンの履歴管理など、直近のデータを扱う際に利用されます。

C#のStackクラスは、System.Collections.Generic名前空間に含まれており、型安全なコレクションとして、任意のデータ型を格納することができます。

スタックの基本的な操作には、要素の追加(Push)、取り出し(Pop)、確認(Peek)などがあります。

これらの操作を通じて、スタックの特性を活かしたプログラミングが可能になります。

Stackクラスの基本操作

Stackクラスのインスタンス化

Stackクラスを使用するには、まずインスタンスを作成する必要があります。

以下のコードでは、整数型のスタックをインスタンス化しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        // 整数型のスタックをインスタンス化
        Stack<int> stack = new Stack<int>();
    }
}

要素の追加：Pushメソッド

Pushメソッドを使用すると、スタックに要素を追加できます。

以下の例では、整数をスタックに追加しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        
        // 要素を追加
        stack.Push(1); // 1を追加
        stack.Push(2); // 2を追加
        stack.Push(3); // 3を追加
    }
}

出力結果はありませんが、スタックには1, 2, 3が追加されています。

要素の取り出し：Popメソッド

Popメソッドを使用すると、スタックの最上部の要素を取り出し、スタックから削除します。

以下の例では、要素を取り出して表示しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        
        // 要素を取り出す
        int topElement = stack.Pop(); // 3を取り出す
        Console.WriteLine(topElement); // 3を表示
    }
}

要素の確認：Peekメソッド

Peekメソッドを使用すると、スタックの最上部の要素を取り出すことなく確認できます。

以下の例では、要素を確認しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        
        // 最上部の要素を確認
        int topElement = stack.Peek(); // 3を確認
        Console.WriteLine(topElement); // 3を表示
    }
}

スタックのサイズ確認：Countプロパティ

Countプロパティを使用すると、スタックに格納されている要素の数を確認できます。

以下の例では、スタックのサイズを表示しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        
        // スタックのサイズを確認
        Console.WriteLine(stack.Count); // 3を表示
    }
}

スタックのクリア：Clearメソッド

Clearメソッドを使用すると、スタック内のすべての要素を削除できます。

以下の例では、スタックをクリアしています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        
        // スタックをクリア
        stack.Clear();
        Console.WriteLine(stack.Count); // 0を表示
    }
}

Stackクラスの活用例

数値の逆順処理

Stackクラスを使用して、数値の配列を逆順にすることができます。

以下の例では、整数の配列をスタックに追加し、スタックから取り出すことで逆順に表示しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        int[] numbers = { 1, 2, 3, 4, 5 };
        Stack<int> stack = new Stack<int>();
        
        // 配列の要素をスタックに追加
        foreach (int number in numbers)
        {
            stack.Push(number);
        }
        
        // スタックから要素を取り出して逆順に表示
        while (stack.Count > 0)
        {
            Console.WriteLine(stack.Pop());
        }
    }
}

括弧の対応チェック

Stackクラスを使用して、文字列内の括弧の対応をチェックすることができます。

以下の例では、開き括弧と閉じ括弧の対応を確認しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        string input = "{[()]}";
        Console.WriteLine(IsBalanced(input) ? "対応しています" : "対応していません");
    }
    static bool IsBalanced(string input)
    {
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in input)
        {
            if (c == '{' || c == '[' || c == '(')
            {
                stack.Push(c); // 開き括弧をスタックに追加
            }
            else if (c == '}' || c == ']' || c == ')')
            {
                if (stack.Count == 0) return false; // スタックが空なら不均衡
                char top = stack.Pop(); // 最上部の要素を取り出す
                if (!IsMatchingPair(top, c)) return false; // 対応を確認
            }
        }
        return stack.Count == 0; // スタックが空なら均衡
    }
    static bool IsMatchingPair(char open, char close)
    {
        return (open == '{' && close == '}') ||
               (open == '[' && close == ']') ||
               (open == '(' && close == ')');
    }
}

対応しています

再帰処理のシミュレーション

Stackクラスを使用して、再帰処理をシミュレーションすることができます。

以下の例では、フィボナッチ数列をスタックを使って計算しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        int n = 5; // フィボナッチ数列のn番目
        Console.WriteLine(Fibonacci(n)); // 5を表示
    }
    static int Fibonacci(int n)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(n); // nをスタックに追加
        
        int result = 0;
        
        while (stack.Count > 0)
        {
            int current = stack.Pop(); // スタックから取り出す
            
            if (current == 0) result += 0; // F(0) = 0
            else if (current == 1) result += 1; // F(1) = 1
            else
            {
                stack.Push(current - 1); // F(n-1)をスタックに追加
                stack.Push(current - 2); // F(n-2)をスタックに追加
            }
        }
        
        return result;
    }
}

Stackクラスの注意点

スタックが空の場合のPopメソッドの挙動

StackクラスのPopメソッドは、スタックが空の場合に呼び出されると、InvalidOperationExceptionをスローします。

これは、取り出す要素が存在しないためです。

したがって、Popメソッドを使用する前に、スタックが空でないことを確認することが重要です。

以下の例では、空のスタックからPopメソッドを呼び出す際の注意点を示しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        
        try
        {
            // スタックが空のため、例外が発生
            int topElement = stack.Pop(); 
        }
        catch (InvalidOperationException ex)
        {
            Console.WriteLine("エラー: " + ex.Message); // エラーメッセージを表示
        }
    }
}

エラー: Stack empty.

スタックオーバーフローのリスク

スタックは、メモリに制限があるため、要素を追加し続けるとスタックオーバーフローが発生する可能性があります。

特に、再帰処理や無限ループでスタックに要素を追加し続けると、メモリ不足に陥ることがあります。

スタックオーバーフローが発生すると、プログラムは異常終了します。

以下の例では、無限ループによるスタックオーバーフローのリスクを示しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<int> stack = new Stack<int>();
        
        // 無限ループでスタックに要素を追加
        while (true)
        {
            stack.Push(1); // 常に1を追加
        }
    }
}

このコードを実行すると、スタックオーバーフローが発生し、プログラムが異常終了します。

スタックとキューの違い

スタックとキューは、どちらもデータ構造ですが、要素の追加と取り出しの順序が異なります。

以下の表に、スタックとキューの主な違いを示します。

特徴	スタック (Stack)	キュー (Queue)
データの順序	LIFO(Last In, First Out)	FIFO(First In, First Out)
要素の追加	`Pushメソッド`	`Enqueueメソッド`
要素の取り出し	`Popメソッド`	`Dequeueメソッド`
主な用途	再帰処理、履歴管理	プロセス管理、タスク処理

このように、スタックは最後に追加した要素を最初に取り出すのに対し、キューは最初に追加した要素を最初に取り出す特性を持っています。

用途に応じて、適切なデータ構造を選択することが重要です。

Stackクラスの応用

カスタムオブジェクトのスタック操作

Stackクラスは、カスタムオブジェクトを格納することも可能です。

以下の例では、Personクラスのインスタンスをスタックに追加し、取り出す操作を示しています。

using System;
using System.Collections.Generic;
class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
    public Person(string name, int age)
    {
        Name = name;
        Age = age;
    }
}
class Program
{
    static void Main()
    {
        Stack<Person> stack = new Stack<Person>();
        
        // カスタムオブジェクトをスタックに追加
        stack.Push(new Person("Alice", 30));
        stack.Push(new Person("Bob", 25));
        
        // スタックから取り出して表示
        while (stack.Count > 0)
        {
            Person person = stack.Pop();
            Console.WriteLine($"{person.Name}, {person.Age}歳"); // 名前と年齢を表示
        }
    }
}

Bob, 25歳
Alice, 30歳

Undo/Redo機能の実装

Stackクラスは、Undo/Redo機能の実装にも利用できます。

以下の例では、操作履歴をスタックに保存し、UndoとRedoを実行しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Stack<string> undoStack = new Stack<string>();
        Stack<string> redoStack = new Stack<string>();
        
        // 操作を追加
        PerformAction(undoStack, redoStack, "操作1");
        PerformAction(undoStack, redoStack, "操作2");
        
        // Undoを実行
        string lastAction = Undo(undoStack, redoStack);
        Console.WriteLine($"Undo: {lastAction}"); // 操作2を取り消す
        
        // Redoを実行
        string redoAction = Redo(undoStack, redoStack);
        Console.WriteLine($"Redo: {redoAction}"); // 操作2を再実行
    }
    static void PerformAction(Stack<string> undoStack, Stack<string> redoStack, string action)
    {
        undoStack.Push(action); // 操作を追加
        redoStack.Clear(); // Redoスタックをクリア
    }
    static string Undo(Stack<string> undoStack, Stack<string> redoStack)
    {
        if (undoStack.Count > 0)
        {
            string action = undoStack.Pop(); // 最後の操作を取り消す
            redoStack.Push(action); // Redoスタックに追加
            return action;
        }
        return "操作なし";
    }
    static string Redo(Stack<string> undoStack, Stack<string> redoStack)
    {
        if (redoStack.Count > 0)
        {
            string action = redoStack.Pop(); // Redoスタックから取り出す
            undoStack.Push(action); // Undoスタックに戻す
            return action;
        }
        return "操作なし";
    }
}

Undo: 操作2
Redo: 操作2

深さ優先探索(DFS)での利用

Stackクラスは、深さ優先探索(DFS)アルゴリズムの実装にも利用されます。

以下の例では、グラフのDFSをスタックを使って実行しています。

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        // グラフの隣接リスト
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            { 1, new List<int> { 2, 3 } },
            { 2, new List<int> { 4, 5 } },
            { 3, new List<int> { 6 } },
            { 4, new List<int>() },
            { 5, new List<int>() },
            { 6, new List<int>() }
        };
        
        Console.WriteLine("DFSの結果:");
        DepthFirstSearch(graph, 1); // ノード1からDFSを開始
    }
    static void DepthFirstSearch(Dictionary<int, List<int>> graph, int startNode)
    {
        Stack<int> stack = new Stack<int>();
        HashSet<int> visited = new HashSet<int>();
        
        stack.Push(startNode); // スタックに開始ノードを追加
        
        while (stack.Count > 0)
        {
            int node = stack.Pop(); // スタックからノードを取り出す
            
            if (!visited.Contains(node))
            {
                visited.Add(node); // 訪問済みとしてマーク
                Console.WriteLine(node); // ノードを表示
                
                // 隣接ノードをスタックに追加
                foreach (int neighbor in graph[node])
                {
                    stack.Push(neighbor);
                }
            }
        }
    }
}