- ジェネリックコレクション ページ一覧
Queue
データ構造としてのキュー(queue)には、二つの操作エンキュー(enqueue)とデキュー(dequeue)が定義されます。 エンキューはキューの末尾に要素を追加する操作で、デキューはキューの先頭から要素を取り出す操作です。 この二つの操作により先入れ先出し(FIFO: First-In, First-Out)のデータ構造が実現されます。
例を挙げると、待ち行列の最後尾に一人並べる作業がエンキュー、待ち行列の先頭から一人引き抜く作業がデキューに相当します。
.NETにおいて、キューのデータ構造を持つコレクションクラスがSystem.Collections.Generic.Queueクラスです。
Queueクラスに要素を追加するエンキューの操作はEnqueueメソッド、Queueから要素を取り出すデキューの操作はDequeueメソッドで行います(§.エンキュー操作とデキュー操作 (Enqueue/Dequeue))。 Queueから要素をデキューすると、取り出した要素はQueueから削除されます。 Queueから要素を取り出さずに参照だけ行う場合はPeekメソッドを使います。 Queueに現在いくつの要素が含まれているかを知るにはCountプロパティを参照します。
ListクラスやDictionaryクラスとは異なり、Queueクラスでは要素が格納された順序が大きな意味を持ちます。 最初(または最後)に格納された要素のみに着目するため、インデックスを指定した要素へのアクセス(ランダムアクセス)はできません(§.インデックス付きの列挙操作)。 また、Queueに格納される要素は格納された順に並べられ、格納された後はその順序を並べ替えることはできません。
Listなどと同様、Queueは可変長のコレクションであるため任意の数の要素をエンキューできます。 エンキューの際、Queue内部の容量は必要に応じて自動的に拡充されます。 デキューの際に要素数が減っても、明示的に指示しない限りはQueue内部で確保されている容量が減ることはありません。
JavaScriptなど他のスクリプト言語では、配列をスタックやキューのように扱うための操作が用意されているものもありますが、Queueクラスではキューとしての操作しか提供されません。 つまり、Queueクラスに対してpush/pop操作を行うようなメソッドは用意されていません。 そういった操作を行いたい場合はStackクラスを使用します。
エンキュー操作とデキュー操作 (Enqueue/Dequeue)
Queueクラスでは、EnqueueメソッドでQueueに対して要素の追加(プッシュ操作)、DequeueメソッドでQueueからの要素の取り出し(ポップ操作)を行います。
次の例では、3つの要素をQueueにエンキューし、その後Queueが空になるまでデキューしています。 キューでは一番最初に入れた要素は一番始めに取り出される(First-In, First-Out)という特性上、要素を入れた順番と同じ順番で表示されている点に注目してください。
Queueでもforeachによる列挙操作を行うことができます。 Queueの内容をforeachで列挙すると、Enqueueしたのと同じ順序、Dequeueする場合と同じ順序で要素が列挙されます。
空のQueueに対するDequeue
Queueが空のときにDequeueメソッドを呼び出すと、null
/Nothing
が返されるのではなく、例外InvalidOperationExceptionがスローされます。 このため、Dequeueメソッドの戻り値からQueueが空だったかどうかを判断することはできません。
Queueが空かどうかに関わらず、例外をスローせずにポップ操作を試行するメソッドとしてTryDequeueメソッドが用意されています。
このほか、DequeueメソッドでInvalidOperationExceptionを避けるには、Dequeueメソッドを呼び出す前にCountプロパティを参照して、要素が1つ以上格納されているかチェックするようにします。
デキュー操作の試行 (TryDequeue)
Queueが空のときにDequeueメソッドを呼び出すと、例外InvalidOperationExceptionがスローされます。 一方、TryDequeueメソッドを使うと、Queueが空の場合でも例外をスローさせずにポップ操作を試行することができます。 TryDequeueメソッドは.NET Standard 2.1/.NET Core 2.0以降で使用できます。
TryDequeueメソッドは、成功した場合はデキューした要素をoutパラメータで出力し、戻り値true
を返します。 失敗した場合、つまりQueueが空だった場合は単に戻り値false
を返します。
ピーク操作 (Peek)
DequeueメソッドはQueueの先頭にある要素を取り出して取得しますが、Peekメソッドを使うとQueueの内容を変更せず(Queueから削除せず)に先頭にある要素を参照できます。
foreachなどによる列挙操作では、Queueの状態を変更せずにQueueに格納されているすべての内容を参照することができます。
Dequeueメソッドと同様に、Queueの内容が空の場合にPeekメソッドを呼び出すと、例外InvalidOperationExceptionがスローされます。
したがって、Peekメソッドの戻り値を見てQueueが空かどうかを判断することはできません。 Queueが空であるかどうかを判断するにはPeekメソッドではなくCountプロパティを参照します。
ピーク操作の試行 (TryPeek)
TryDequeueメソッドと同様に、TryPeekメソッドを使うと、Queueが空の場合でも例外をスローさせずにピーク操作を試行することができます。 TryPeekメソッドは.NET Standard 2.1/.NET Core 2.0以降で使用できます。
要素数の取得 (Count)
Queueに現在格納されている要素の数を取得するには、Countプロパティを参照します。 Queueが空の状態、何も格納されていない状態の場合は、当然Countプロパティは0となります。
要素の有無の検証 (Contains)
Queueに指定した内容の要素が含まれているか調べるには、Containsメソッドを使います。
ただし、このメソッドではIEqualityComparerを指定できないため、Dictionaryのように大文字小文字の違いを無視して比較するといったことはできません。 そういった比較条件を指定した上で要素が含まれているかを調べるには、LINQの拡張メソッドContainsなどを使う必要があります。
文字列の比較オプション(StringComparer)については文字列と比較オプション・カルチャの並べ替え規則、IEqualityComparer<T>インターフェイスによる同値比較のカスタマイズについては等価性の定義と比較 §.IEqualityComparer, IEqualityComparer<T>を参照してください。
同一の要素の格納
Queueには同一の要素(値)を複数格納することができます。 同じ要素を複数回Enqueueした場合でもそれぞれ個別の要素として扱われます。
null
/Nothing
の格納
stringなどの参照型を格納するQueueの場合はnull
/Nothing
を格納することもできます。
intなどの値型を格納するQueueの場合、C#ではnull
を格納することはできません。 VBではNothing
を格納しようとすると、Nothing
そのものではなく、0
などその型のデフォルト値が格納されます。
値型の値を格納するStackで、値が空であることを表すためにnull
/Nothing
を格納したいといった場合には、ヌル許容型を用いることができます。
内容のクリア (Clear)
Clearメソッドを呼び出すことで、Queueの内容を空にすることができます。
TrimExcessメソッドを使うことで、Queue内部で確保されているバッファを最小化することができます。
容量の縮小 (TrimExcess)
Queueに対してそれ以上要素を追加や取り出しをする必要がなくなった場合には、TrimExcessメソッドを呼び出すことで、Queueが内部的に確保しているバッファを最小化することができ、不要な容量を減らすことができます。
TrimExcessメソッドはQueue内の再割当てを行うことで使用するメモリを最小化します。 そのため、Queueにそれ以上変更を加えない(追加によって容量を再度拡張する必要がない)ことが明らかな場合などに用いるべきで、不必要に何度も呼び出すことは逆にパフォーマンスの劣化に繋がります。
なお、List.CapacityのようなプロパティはQueueには用意されていないため、実際にQueueが確保しているバッファの容量を知ることはできません。
容量とバッファを最小化に関しては、Listクラスでの解説ジェネリックコレクション(1) List §.容量を参照してください。
列挙操作
QueueはIEnumerable<T>を実装しているためforeach文による列挙ができるようになっています。 foreach文による列挙では、Enqueueした順と同じ順、つまりDequeueする順と同じ順で要素が列挙されます。 デキュー操作とは異なり、Queueを列挙するだけでは要素の削除は行われません。
インデックス付きの列挙操作
一方、Queueではインデクサがサポートされないのでfor文による列挙はできません。 for文でインデックスを用いた列挙を行うためには、Queueを配列に変換してから列挙するか、LINQの拡張メソッドSelectを使って次のようにします。
配列からの変換
配列からQueueに変換するには、コンストラクタが使えます。 あらかじめ内容を持った状態のQueueを作成したい場合も、コンストラクタに配列などを指定してインスタンスを作成します。 コンストラクタに配列を指定した場合、Queueの内容は配列の要素を先頭から一つずつEnqueueした場合と同じ内容になります。
配列への変換・コピー (ToArray・CopyTo)
Queueから配列へ変換する場合にはToArrayメソッドやCopyToメソッドが使えます。 ToArrayメソッドではQueueの内容を配列に変換したものが得られ、CopyToメソッドではQueueの内容を既存の配列にコピーします。 変換・コピーした後の配列の内容は、列挙操作を行った場合と同様にQueueの内容を一つずつDequeueした場合と同じ順序になります。 当然、変換・コピーの前後でQueueの内容は変化しません。
一部分の配列への変換
Queueの一部分のみを配列として取得するメソッドは用意されていません。 そのため、全部を配列に変換した後必要な部分だけを抜き出して使うか、次のようにLINQの拡張メソッドSkipおよびTakeを組み合わせて一部分のみを取得します。
LinkedListを使ったキューの実装
Queueクラス以外にも、双方向連結リストのデータ構造を構成するためのクラスであるLinkedList<T>クラスを用いることでもキューのデータ構造を実装することができます。 具体例についてはジェネリックコレクション(4) LinkedList §.キューとしての使用で紹介しています。