[C#] キューとスタックを自前で実装する方法

Stack, Queue を自前で実装する

C# の場合、データ構造の Stack と Queue は標準ライブラリで提供されますが、自前で実装して理解を深めようと思います。

順番に見ていきます。

Stack (スタック)

スタック – Wikipedia

Stack は先入れ後出し(FILO)を実現するためのデータ構造です。

Stack は、データを入れる Push と積まれたデータの先頭(最後に入れられたデータ)を取り出す Pop の2つの基本操作を提供します。Push と Pop の操作イメージは以下の通りです。

データを下から上に積み上げるようなイメージです。

そのほか Pop で次に取り出されるデータを確認するだけの Peek を実装します。

実装

では実装していきます。内部で持つデータは配列とし、それを PUSH POP で操作できるようにします。

public class Stack<T>
{
    public int Capacity { get; }
    public int Length { get; private set; }

    private T[] Array;

    public Stack(int capacity)
    {
        this.Capacity = capacity;
        this.Array = new T[capacity];
    }

    public void Push(T data)
    {
        this.Array[this.Length] = data;
        this.Length += 1;
    }

    public T Pop()
    {
        var result = this.Array[this.Length - 1];
        this.Length -= 1;
        return result;
    }

    public T Peek() => this.Array[this.Length - 1];
}

使い方

var stack = new Stack<int>(10);
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());
stack.Push(4);
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Pop());

// 3 2 4 1

コンストラクタでデータの入る上限(capacity)を受け取って内部の配列を初期化しています。この上限を超えて Push するとオーバーフローでれ外となります。

あとは格納されているデータ数 Length も別途管理することで Push, Pop を実装できるようにしています。Peek は単純にデータの先頭を参照して返します。

注意点として、この実装だと Pop されたデータも配列の中に残り続けることになります。つまりオブジェクトを積んでいる場合、参照が残り続けることになります。

this.Array[this.Length - 1] = default;

上記のようにするとデフォルト値で取り出したデータの場所に入っているデータを初期化できます。プリミティブ型であれば無駄なのですが。

また、上記実装の場合だと上限をコンストラクタで定義しなければなりませんが、これを動的に増やすことも可能です。方法は以下のいずれかが考えられます。

1. 配列ではなく List を使う
2. 上限近くになったらサイズを大きくした別の配列を作り、入れ替える

2 の配列の再確保が簡単だと思います。上限近くになればより大きい配列を初期化し、そこに既存のデータすべてを詰め込んだのち、丸っと置き換えるだけで済みます。

Queue (キュー)

キュー (コンピュータ) – Wikipedia

キューは 先入れ先出し(FIFO)を実現するためのデータ構造です。お店の行列みたいな感じです。先に並んだ人から順番に処理されるイメージです。

上のような感じです。

データを入れる処理を Enqueue 取り出す処理を Dequeue といいます。Stack と同じく先頭を除くだけの Peek も用意します。

実装

public class Queue<T>
{
    public int Capacity { get; }
    public int Length { get; private set; }

    private int Head;
    private int Tail;
    private T[] Array;

    public Queue(int capacity)
    {
        this.Capacity = capacity;
        this.Array = new T[this.Capacity];
    }

    public void Enqueue(T data)
    {
        if (this.Length == this.Capacity)
        {
            throw new Exception("overflow ...");
        }

        this.Array[this.Tail] = data;
        this.Tail += 1;
        if (this.Tail == this.Capacity) this.Tail = 0;
        this.Length += 1;
    }

    public T Dequeue()
    {
        var result = this.Array[this.Head];
        this.Head += 1;
        if (this.Head == this.Capacity) this.Head = 0;
        this.Length -= 1;
        return result;
    }

    public T Peek() => this.Array[this.Head];
}

使い方

var queue = new Queue<int>(10);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());
queue.Enqueue(4);
Console.WriteLine(queue.Dequeue());
Console.WriteLine(queue.Dequeue());

// 1 2 3 4

コンストラクタで上限を定義するのは Stack と同じです。Stack との大きな違いは、Queue の場合先頭要素を取り出す必要があるので、末尾だけでなく先頭のインデックスも管理しなければならない点にあります。

Head はキューの先頭要素が入っているインデックス、Tail は末尾の要素が入っているインデックスの1つ後ろのインデックスです。つまり次に取り出されるインデックスと次に値が入るインデックスです。

Head と Tail の大きさは逆転する場合もあります。なぜなら先頭要素は先に取り出されるためです。

Enqueu では Tail にデータを挿入し、Tail をインクリメントします。この時配列の上限を超える場合は 0 に戻ります。

Dequeu では Head のデータを取り出し、Head をインクリメントします。同じく必要に応じて 0 に戻ります。

この方法では配列の境界外部にアクセスして例外が発生するすることはありませんが、上限を超えるデータ数を入れようとしたときに先頭データを上書きしてしまう可能性があります。したがってデータ数を別途 Length として管理し Enqueue の時に上限を超えてないか確認しましょう。

以上。