深掘り.NET：Queue<T>を読み解く

はじめに

C#のQueue<T>は先入れ先出し（FIFO）のデータ構造として広く使われていますが、その内部実装は単純な配列の先頭・末尾操作ではなく、リングバッファ（循環バッファ） として実装されています。この記事では、.NET ランタイムの実際のソースコードを元に、Queue<T>の内部構造と効率的な動作原理を解説します。

内部構造の概要

Queue<T>は以下の4つの主要なフィールドで管理されています。

private T[] _array;      // データを格納する配列
private int _head;       // デキューする位置（先頭）
private int _tail;       // エンキューする位置（末尾）
private int _size;       // 要素数

これらのフィールドが、リングバッファとしての動作を実現する鍵となります。

リングバッファとしての動作

なぜリングバッファなのか？

通常の配列で先入れ先出しを実現しようとすると、先頭から削除するたびに全要素を前方にシフトする必要があり、O(n)の時間計算量がかかってしまいます。

リングバッファを使うことで、配列を循環的に使い回せるため、Enqueue/Dequeueを通常O(1)で実行できます。

リングバッファの仕組み

_headと_tailの2つのインデックスを使い、配列を循環的に利用します。

初期状態（空）:
[_, _, _, _, _]
 ↑
 head, tail

Enqueue(A), Enqueue(B), Enqueue(C):
[A, B, C, _, _]
 ↑     ↑
 head  tail

Dequeue() → A:
[_, B, C, _, _]
    ↑  ↑
    head tail

Enqueue(D), Enqueue(E):
[_, B, C, D, E]
    ↑        ↑
    head     tail (末尾に到達)

Enqueue(F) → 配列の先頭に戻る:
[F, B, C, D, E]
    ↑
    head
 ↑
 tail (循環)

MoveNext：循環の実装

インデックスを進める際、配列の末尾に達したら0に戻す処理がMoveNextメソッドです。

private void MoveNext(ref int index)
{
    // It is tempting to use the remainder operator here but it is actually much slower
    // than a simple comparison and a rarely taken branch.
    // JIT produces better code than with ternary operator ?:
    int tmp = index + 1;
    if (tmp == _array.Length)
    {
        tmp = 0;
    }
    index = tmp;
}

注目すべきは、剰余演算子（%）を使わない点です。コメントにもあるように、単純な比較と分岐の方が剰余演算より高速だからです。

主要メソッドの実装

Enqueue：要素の追加

public void Enqueue(T item)
{
    if (_size == _array.Length)
    {
        Grow(_size + 1);  // 容量が足りなければ拡張
    }

    _array[_tail] = item;
    MoveNext(ref _tail);
    _size++;
    _version++;
}

1. 容量チェックと必要に応じた拡張
2. _tailの位置に要素を格納
3. _tailを次の位置に移動（循環）
4. サイズをインクリメント

Dequeue：要素の取り出し

public T Dequeue()
{
    int head = _head;
    T[] array = _array;

    if (_size == 0)
    {
        ThrowForEmptyQueue();
    }

    T removed = array[head];
    if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
    {
        array[head] = default!;  // 参照型の場合はクリア
    }
    MoveNext(ref _head);
    _size--;
    _version++;
    return removed;
}

1. 空チェック
2. _headの位置から要素を取得
3. 参照型の場合、メモリリークを防ぐためdefaultでクリア
4. _headを次の位置に移動（循環）
5. サイズをデクリメント

CopyTo：配列へのコピー

リングバッファの特性上、データが配列内で2つの部分に分かれている可能性があります。

public void CopyTo(T[] array, int arrayIndex)
{
    // ... バリデーション ...
    
    int numToCopy = _size;
    if (numToCopy == 0) return;

    // 第1部分: _headから配列末尾まで
    int firstPart = Math.Min(_array.Length - _head, numToCopy);
    Array.Copy(_array, _head, array, arrayIndex, firstPart);
    numToCopy -= firstPart;
    
    // 第2部分: 配列先頭から_tailまで（もし循環していれば）
    if (numToCopy > 0)
    {
        Array.Copy(_array, 0, array, arrayIndex + _array.Length - _head, numToCopy);
    }
}

データが配列を跨いでいる場合でも、2回のコピー操作で正しく取り出せます。

容量管理とGrowの仕組み

Grow：動的な容量拡張

private void Grow(int capacity)
{
    const int GrowFactor = 2;
    const int MinimumGrow = 4;

    int newcapacity = GrowFactor * _array.Length;

    // オーバーフロー対策
    if ((uint)newcapacity > Array.MaxLength) 
        newcapacity = Array.MaxLength;

    // 最小増加量の保証
    newcapacity = Math.Max(newcapacity, _array.Length + MinimumGrow);

    // 要求容量が計算値より大きければそれを使用
    if (newcapacity < capacity) 
        newcapacity = capacity;

    SetCapacity(newcapacity);
}

• 基本は現在の2倍に拡張（GrowFactor = 2）
• 最低でも4要素は増やす
• 配列の最大長を超えないよう制御

SetCapacity：容量変更とデータ再配置

private void SetCapacity(int capacity)
{
    T[] newarray = new T[capacity];
    if (_size > 0)
    {
        if (_head < _tail)
        {
            // データが連続している場合
            Array.Copy(_array, _head, newarray, 0, _size);
        }
        else
        {
            // データが循環している場合、2回に分けてコピー
            Array.Copy(_array, _head, newarray, 0, _array.Length - _head);
            Array.Copy(_array, 0, newarray, _array.Length - _head, _tail);
        }
    }

    _array = newarray;
    _head = 0;
    _tail = (_size == capacity) ? 0 : _size;
    _version++;
}

容量変更時には、リングバッファを線形配列に整列し直すことで、新しい配列では_head = 0から始まるようにします。

パフォーマンス特性

時間計算量

操作	平均	最悪
Enqueue	O(1)	O(n)*
Dequeue	O(1)	O(1)
Peek	O(1)	O(1)
Contains	O(n)	O(n)

* 容量拡張が発生した場合のみO(n)

リングバッファの利点

1. メモリ効率: 配列全体を有効活用し、無駄な空間を最小化
2. 高速な操作: インデックス操作のみで追加・削除が可能
3. 予測可能な性能: 容量拡張時以外は常にO(1)

まとめ

Queue<T>は、リングバッファという巧妙なデータ構造により、以下を実現しています。

• O(1)の高速なEnqueue/Dequeue（通常時）
• 効率的なメモリ利用（配列全体を循環的に使用）
• 最小限のデータ移動（容量変更時のみ再配置）

単純な配列操作では実現できない、高性能かつ実用的なキュー実装となっています。このような内部実装を理解することで、適切なデータ構造の選択や、パフォーマンスチューニングに役立てることができるでしょう。

参考資料

• Microsoft Docs: Queue<T>クラス
• GitHub: Queue.cs