C# で Deque(両端キュー)を実装してみる

C# で Deque(両端キュー)を実装してみる

両端キュー – Wikipedia

C# で Deque(両端キュー) を実装してみます。両端キューは以下の4つの操作が高速に行えるデータ構造のことです。

• 先頭に要素を挿入
• 先頭の要素を削除
• 末尾に要素を挿入
• 末尾の要素を削除

C# には標準ライブラリで LinkedList<T>(連結リスト) が用意されており、このデータ構造も先頭と末尾にデータの追加削除が可能です。List<T> も任意の位置に対してデータの挿入と削除が可能ですが、計算量が異なります。

計算量

今回実装する両端キューと LinkedList<T> の計算量については以下のようになります。Nは要素数です。

LinkedListはランダムアクセスしようとすると、先頭または末尾からリンクをたどりながら任意のインデックスの要素までたどらないといけないので、計算量が O(N) となってしまいます。

List は Insert() や RemoveAt() を使って任意の位置に挿入削除が行えますが、基本的には O(N) かかるので遅いです。

両端キューは内部で配列を使ってデータを管理するので、ランダムアクセスも O(1) で行えるようにします。

実装

両端キューの実装には内部で配列をリングバッファのように扱います。

リングバッファ – Wikipedia

配列を使ってデータを管理しますが、これをリング状に見立てて扱います。

先頭のインデックスを管理しておけば、こうすることで先頭または末尾に要素を追加するときはそれぞれ

• (現在の先頭のインデックス-1) % 配列のサイズ
• (現在の末尾のインデックス+1) % 配列のサイズ

にデータを書き込めばよいです。剰余を使えばうまくアクセスできます。

削除は先頭のインデックスと現在のデータサイズを更新しておけばよいです。

では実装します。

class Deque<T> : IEnumerable<T>
{
    public T this[int i]
    {
        get { return this.Buffer[(this.FirstIndex + i) % this.Capacity]; }
        set
        {
            if (i < 0) throw new ArgumentOutOfRangeException();
            this.Buffer[(this.FirstIndex + i) % this.Capacity] = value;
        }
    }
    private T[] Buffer;
    private int Capacity;
    private int FirstIndex;
    private int LastIndex
    {
        get { return (this.FirstIndex + this.Length) % this.Capacity; }
    }
    public int Length;
    public Deque(int capacity = 16)
    {
        this.Capacity = capacity;
        this.Buffer = new T[this.Capacity];
        this.FirstIndex = 0;
    }
    public void PushBack(T data)
    {
        if (this.Length == this.Capacity) this.Resize();
        this.Buffer[this.LastIndex] = data;
        this.Length++;
    }
    public void PushFront(T data)
    {
        if (this.Length == this.Capacity) this.Resize();
        var index = this.FirstIndex - 1;
        if (index < 0) index = this.Capacity - 1;
        this.Buffer[index] = data;
        this.Length++;
        this.FirstIndex = index;
    }
    public T PopBack()
    {
        if (this.Length == 0) throw new InvalidOperationException("データが空です。");
        var data = this[this.Length - 1];
        this.Length--;
        return data;
    }
    public T PopFront()
    {
        if (this.Length == 0) throw new InvalidOperationException("データが空です。");
        var data = this[0];
        this.FirstIndex++;
        this.FirstIndex %= this.Capacity;
        this.Length--;
        return data;
    }
    private void Resize()
    {
        var newArray = new T[this.Capacity * 2];
        for (int i = 0; i < this.Length; i++)
        {
            newArray[i] = this[i];
        }
        this.FirstIndex = 0;
        this.Capacity *= 2;
        this.Buffer = newArray;
    }
    public IEnumerator<T> GetEnumerator()
    {
        for (int i = 0; i < this.Length; i++)
        {
            yield return this[i];
        }
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        for (int i = 0; i < this.Length; i++)
        {
            yield return this[i];
        }
    }
}

Listのようにキャパシティーを管理しておき、これを超えるデータを追加しようとするとより大きなサイズ(2倍)の配列を確保して入れ替えるようにしています。

末尾への要素の追加は PushBack(T data) で行います。末尾のインデックスにデータを書き換えて、サイズも更新します。先頭への要素の追加は、PushFront(T data) で行います。先頭への追加時は先頭のインデックスも更新しておきましょう。

メソッド名はC++にそろえるように LinkedList で使われる名前から変更しました。

データの取り出しは、データを取り出して返すついでにインデックスと要素数を更新するだけです。削除した後にデータが残るのが嫌であれば、デフォルト値などで更新してもいいかもしれません。

あとはインデクサと、IEnumerable<T> を実装しておけば配列やほかのコンテナと同じように使えて便利です。

テスト

• No.1021 Children in Classrooms – yukicoder

yukicoder でいい感じに使えそうな問題を見つけたので実装した Deque を使ってテスト代わりに解いてみました。

ACしたのでたぶんうまく実装できていると思います。

以上。