§1 Queue

System.Collections.Generic.Queueクラスは、先入れ先出し(FIFO: First-In, First-Out)のデータ構造を持つキューを提供するコレクションクラスです。

§1.1 基本的な操作

キューでは二つの操作エンキューデキューが定義されます。 エンキューはキューの末尾に要素を追加する操作で、デキューはキューの先頭から要素を取り出す操作です。 この二つの操作により先入れ先出しのデータ構造が実現されます。 待ち行列の最後尾に一人並べる作業がエンキュー、待ち行列の先頭から一人引き抜く作業がデキューに相当するとイメージするとよいと思います。

Queueクラスに要素を追加するエンキューの操作はEnqueueメソッド、Queueから要素を取り出すデキューの操作はDequeueメソッドで行います。 Queueから要素をデキューすると、取り出した要素はQueueから削除されます。

キュー

ListクラスDictionaryクラスとは異なり、Queueクラスでは要素が格納された順序が大きな意味を持ちます。 Queueに格納される要素は格納された順に並べられ、格納された後はその順序を並べ替えることはできません。 また、最初(または最後)に格納された要素のみに着目するため、インデックスを指定した要素へのアクセス(ランダムアクセス)はできません。

Queueに現在いくつの要素が含まれているかを知るにはCountプロパティを参照します。 Listなどと同様、Queueは可変長のコレクションであるため任意の数の要素をエンキューできます。 エンキューの際、Queue内部の容量は必要に応じて自動的に拡充されます。 デキューの際に要素数が減っても、Queue内部で確保されている容量が減ることはありません。


次の例では、5つの要素をQueueにエンキューし、その後Queueが空になるまでデキューしています。 キューでは一番最初に入れた要素は一番始めに取り出される(First-In, First-Out)という特性上、要素を入れた順番と同じ順番で表示されている点に注目してください。

Queueクラスと要素のEnqueue・Dequeue
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    // Queueに要素をEnqueue
    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");
    q.Enqueue("Dave");
    q.Enqueue("Eve");

    // Queueが空になるまで内容をDequeue
    while (0 < q.Count) {
      Console.WriteLine(q.Dequeue());
    }
  }
}
実行結果
Alice
Bob
Charlie
Dave
Eve

§1.2 ピーク操作 (Peek)

DequeueメソッドはQueueの先頭にある要素を取り出して取得しますが、Peekメソッドを使うとQueueの内容を変更せず(Queueから削除せず)に先頭にある要素を参照できます。

Queueの内容が空の場合にDequeueメソッドやPeekメソッドを呼び出すと、null/Nothingが返されるのではなく例外InvalidOperationExceptionがスローされます。 従って、戻り値を見てQueueが空になったかどうかを判断することはできません。 Queueが空であるかどうかを判断するにはPeekメソッドではなくCountプロパティを使います。

Peekによる要素の参照とDequeueによる取り出し
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    // Queueに要素をEnqueue
    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");

    // Queueの先頭にある要素をPeek
    Console.WriteLine("Peek: {0}", q.Peek());

    // Queueから要素を5つDequeue (Queueの要素数は3なので、途中で例外がスローされる)
    for (int i = 0; i < 5; i++) {
      Console.WriteLine("Dequeue: {0}", q.Dequeue());
    }
  }
}
実行結果
Peek: Alice
Dequeue: Alice
Dequeue: Bob
Dequeue: Charlie

ハンドルされていない例外: System.InvalidOperationException: Queue が空です。
   場所 System.ThrowHelper.ThrowInvalidOperationException(ExceptionResource resource)
   場所 System.Collections.Generic.Queue`1.Dequeue()
   場所 Sample.Main()

foreachなどによる列挙操作では、Queueの状態を変更せずにQueueに格納されているすべての内容を参照することができます。

§1.3 要素の有無 (Contains)

Queueに指定した内容の要素が含まれているか調べるには、Containsメソッドを使います。 ただし、このメソッドではIEqualityComparerを指定できないため、Dictionaryのように大文字小文字の違いを無視して比較するといったことはできません。 そういった比較条件を指定した上で要素が含まれているかを調べるには、LINQの拡張メソッドContainsなどを使う必要があります。

Queue.ContainsメソッドとLINQのContains拡張メソッドによる要素の有無の検証
using System;
using System.Collections.Generic;
using System.Linq;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    // Queueに要素をEnqueue
    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");

    // Queueに"CHARLIE"が含まれているか
    Console.WriteLine(q.Contains("CHARLIE"));

    // Queueに"CHARLIE"が含まれているか
    // (LINQのContainsメソッドを使い、大文字小文字の違いを無視して調べる)
    Console.WriteLine(q.Contains("CHARLIE", StringComparer.OrdinalIgnoreCase));
  }
}
実行結果
False
True

§1.4 同一の要素・nullの格納

Queueには同一の要素を複数格納することができます。 また、stringなどの参照型の場合はnull/Nothingを格納することもできます。

using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue(null); // nullをEnqueue
    q.Enqueue("Alice"); // 同一の要素をEnqueue

    // Queueが空になるまで内容をDequeue
    while (0 < q.Count) {
      string e = q.Dequeue();

      Console.WriteLine(e ?? "(null)");
    }
  }
}
実行結果
Alice
Bob
(null)
Alice

intなどの値型のQueueではnullを格納することはできません。 値型のStackで、値が空であることを表すためにnullを格納したいといった場合には、ヌル許容型を用いることができます。



§1.5 内容のクリア (Clear)

Queueの内容を空にするには、Clearメソッドを使います。 また、TrimExcessメソッドを呼び出すと、Queueが内部的に確保しているバッファを最小化することができます。 Clearメソッドで空にした後TrimExcessメソッドを呼び出すと、Queue内のバッファを初期状態に戻すことができます。 なお、List.CapacityのようなプロパティはQueueには用意されていないため、実際にQueueが保持しているバッファの容量を知ることはできません。

Queueの内容のクリア
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    // Queueに要素をEnqueue
    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");

    Console.WriteLine("Count = {0}", q.Count);

    // Queueの内容をクリア
    q.Clear();

    Console.WriteLine("Count = {0}", q.Count);

    // Queueが確保しているバッファを縮小
    q.TrimExcess();
  }
}
実行結果
Count = 3
Count = 0

TrimExcessメソッドはQueue内の再割当てを行うことで使用するメモリを最小化します。 そのため、Queueにそれ以上変更を加えない(追加によって容量を再度拡張する必要がない)ことが明らかな場合などに用いるべきで、不必要に何度も呼び出すことはパフォーマンスの劣化に繋がります。

容量とバッファを最小化に関しては、Listクラスでの解説ジェネリックコレクション(1) List §.容量を参照してください。

§1.6 列挙操作

QueueはIEnumerable<T>を実装しているためforeach文による列挙ができるようになっていますが、インデクサはサポートされないのでfor文による列挙はできません。 foreach文による列挙を行う場合は、Enqueueした順・Dequeueするときと同じ順で列挙されます。 Queueを列挙しても当然Dequeue操作とは異なり要素の削除は行われません。

foreachによるQueueの内容の列挙
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");
    q.Enqueue("Dave");
    q.Enqueue("Eve");

    // foreachでQueueの内容を列挙
    foreach (string e in q) {
      Console.WriteLine(e);
    }

    Console.WriteLine("Count: {0}", q.Count);
  }
}
実行結果
Alice
Bob
Charlie
Dave
Eve
Count: 5

for文でインデックスを用いた列挙を行うためには、Queueを配列に変換することができます。

一方で、単にインデックス付きでの列挙を行えればよいのであれば、LINQの拡張メソッドSelectを使って次のようにすることもできます。

LINQのSelect拡張メソッドを使ってQueueに対してインデックス付きの列挙を行う
using System;
using System.Collections.Generic;
using System.Linq;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");
    q.Enqueue("Dave");
    q.Enqueue("Eve");

    // Selectメソッドを使ってQueueの要素をインデックス付きで列挙する
    foreach (var pair in q.Select((e, i) => new {Element = e, Index = i})) {
      Console.WriteLine("{0} => {1}", pair.Index, pair.Element);
    }
  }
}
実行結果
0 => Alice
1 => Bob
2 => Charlie
3 => Dave
4 => Eve

§1.7 配列からの変換

配列からQueueに変換するには、コンストラクタが使えます。 あらかじめ内容を持った状態のQueueを作成したい場合も、コンストラクタに配列などを指定してインスタンスを作成します。 コンストラクタに配列を指定した場合、Queueの内容は配列の要素を先頭から一つずつEnqueueした場合と同じ内容になります。

配列の内容をQueueの初期内容としてインスタンスを作成する
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    string[] arr = new string[] {"Alice", "Bob", "Charlie", "Dave", "Eve"};
    Queue<string> q = new Queue<string>(arr); // 配列からQueueを作成

    while (0 < q.Count) {
      Console.WriteLine(q.Dequeue());
    }
  }
}
実行結果
Alice
Bob
Charlie
Dave
Eve

§1.8 配列への変換・コピー (ToArray・CopyTo)

Queueから配列へ変換する場合にはToArrayメソッドCopyToメソッドが使えます。 ToArrayメソッドではQueueの内容を配列に変換したものが得られ、CopyToメソッドではQueueの内容を既存の配列にコピーします。 変換・コピーした後の配列の内容は、列挙操作を行った場合と同様にQueueの内容を一つずつDequeueした場合と同じ順序になります。 当然、変換・コピーの前後でQueueの内容は変化しません。

ToArrayメソッドでQueueを配列に変換する・CopyToメソッドでQueueの内容を配列にコピーする
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");
    q.Enqueue("Dave");
    q.Enqueue("Eve");

    // 配列に変換
    Console.WriteLine("[ToArray]");

    string[] arr1 = q.ToArray();

    for (int i = 0; i < arr1.Length; i++) {
      Console.WriteLine("arr1[{0}] => {1}", i, arr1[i]);
    }

    // 配列にコピー
    Console.WriteLine("[CopyTo]");

    string[] arr2 = new string[q.Count];

    q.CopyTo(arr2, 0);

    for (int i = 0; i < arr2.Length; i++) {
      Console.WriteLine("arr2[{0}] => {1}", i, arr2[i]);
    }
  }
}
実行結果
[ToArray]
arr1[0] => Alice
arr1[1] => Bob
arr1[2] => Charlie
arr1[3] => Dave
arr1[4] => Eve
[CopyTo]
arr2[0] => Alice
arr2[1] => Bob
arr2[2] => Charlie
arr2[3] => Dave
arr2[4] => Eve

§1.8.1 一部分の配列への変換

Queueの一部分のみを配列として取得するメソッドは用意されていません。 そのため、全部を配列に変換した後必要な部分だけを抜き出して使うか、次のようにLINQの拡張メソッドSkipおよびTakeを組み合わせて一部分のみを取得します。

LINQの拡張メソッドSkip・Takeを使ってQueueの一部分を配列に変換する
using System;
using System.Collections.Generic;
using System.Linq;

class Sample {
  static void Main()
  {
    Queue<string> q = new Queue<string>();

    q.Enqueue("Alice");
    q.Enqueue("Bob");
    q.Enqueue("Charlie");
    q.Enqueue("Dave");
    q.Enqueue("Eve");

    // Queueの1番目から3つ分を配列に変換
    // (Queueから要素1つ分をSkip、そこから要素3つをTake、その結果をToArray)
    string[] arr = q.Skip(1).Take(3).ToArray();

    for (int i = 0; i < arr.Length; i++) {
      Console.WriteLine("arr[{0}] => {1}", i, arr[i]);
    }
  }
}
実行結果
arr[0] => Bob
arr[1] => Charlie
arr[2] => Dave

§2 LinkedListを使ったキューの実装

Queueクラス以外にも、双方向連結リストのデータ構造を構成するためのクラスであるLinkedList<T>クラスを用いることでもキューのデータ構造を実装することができます。 具体例についてはジェネリックコレクション(4) LinkedList §.キューとしての使用で紹介しています。