キュー（抽象データ型）

列
FIFO（先入れ先出し）キューの表現
ビッグ O 記法による時間計算量 手術 平均 最悪の場合 検索 の上） の上） 入れる オー(1) オー(1) 消去 オー(1) オー(1) 空間の複雑さ 空間 の上） の上）

コンピュータ サイエンスでは、キューとは、シーケンス内に維持されるエンティティのコレクションであり、シーケンスの一方の端にエンティティを追加したり、シーケンスのもう一方の端からエンティティを削除したりすることで変更できます。慣例により、要素が追加されるシーケンスの端は、キューの後ろ、末尾、または後部と呼ばれ、要素が削除される端は、キューの先頭または前部と呼ばれます。これは、人々が商品やサービスを待つために列に並ぶときに使用される言葉に似ています。

キューの後ろに要素を追加する操作はenqueueと呼ばれ、先頭から要素を削除する操作はdequeueと呼ばれます。その他の操作も許可される場合があり、これには、デキューされる次の要素の値をデキューせずに返す peekまたはfront操作が含まれることがよくあります。

キューの操作により、キューは先入れ先出し (FIFO) データ構造になります。FIFO データ構造では、キューに最初に追加された要素が最初に削除されます。これは、新しい要素が追加されると、新しい要素を削除する前に、以前に追加されたすべての要素を削除する必要があるという要件に相当します。キューは線形データ構造、またはより抽象的にシーケンシャル コレクションの例です。キューは、アクセス ルーチンと結合されたデータ構造、抽象データ構造、またはオブジェクト指向言語のクラス として実装されるコンピューター プログラムで一般的です。

キューには 2 つの端があり、上部はプッシュ操作が発生する唯一の位置であり、下部はポップ操作が発生する唯一の位置です。キューは、循環バッファとリンク リストとして実装することも、スタック ポインタとベース ポインタの 両方を使用して実装することもできます。

キューは、コンピュータ サイエンス、輸送、オペレーション リサーチの分野で、データ、オブジェクト、人物、イベントなどのさまざまなエンティティを格納して後で処理するために保持するサービスを提供します。これらのコンテキストでは、キューはバッファの機能を実行します。キューのもう 1 つの用途は、幅優先探索の実装です。

理論的には、キューの特徴の 1 つは、特定の容量がないことです。すでに含まれている要素の数に関係なく、新しい要素をいつでも追加できます。また、キューが空になることもあります。その場合、新しい要素が再度追加されるまで、要素を削除することは不可能になります。

固定長配列は容量が限られていますが、項目をキューの先頭に向かってコピーする必要があるというのは真実ではありません。配列を閉じた円に変え、先頭と末尾をその円の中で際限なく漂わせるという単純なトリックにより、配列に格納されている項目を移動する必要がなくなります。配列のサイズが n の場合、n を法とするインデックスを計算すると、配列は円になります。これは、高水準言語でキューを作成する概念的に最も簡単な方法ですが、配列のインデックスをゼロと配列のサイズと比較する必要があるため、確かに少し遅くなります。これは、配列のインデックスが範囲外であるかどうかを確認するのにかかる時間と同程度です。一部の言語では、このチェックが行われますが、これは、手っ取り早く汚い実装や、ポインター構文を持たない高水準言語では間違いなく選択される方法です。配列のサイズは事前に宣言する必要がありますが、一部の実装では、オーバーフローが発生したときに宣言された配列のサイズを単純に 2 倍にします。オブジェクトまたはポインターを持つほとんどの最新言語では、動的リストを実装するか、動的リストのライブラリが付属しています。このようなデータ構造では、メモリ制約以外に固定容量制限が指定されていない可能性があります。キューオーバーフローは、満杯のキューに要素を追加しようとすると発生し、キューアンダーフローは、空のキューから要素を削除しようとすると発生します。

制限付きキューは、アイテムの数が固定されたキューです。^[1]

FIFOキューには、いくつかの効率的な実装があります。効率的な実装とは、エンキューとデキューの操作をO(1)時間で実行できる実装です。

• リンクリスト
  • 二重リンクリストは両端で O(1) の挿入と削除を行うため、キューには自然な選択です。
  • 通常の単一リンク リストでは、一方の端でのみ効率的な挿入と削除が可能です。ただし、最初のノードに加えて最後のノードへのポインタを保持するという小さな変更を加えると、効率的なキューを実装できるようになります。
• 修正された動的配列を使用して実装されたデキュー

キューは別のデータ型として実装されるか、両端キュー（deque）の特殊なケースとして別々に実装されない場合もあります。たとえば、PerlとRuby では配列を両端からプッシュおよびポップできるため、push関数とshift関数を使用してリストをエンキューおよびデキューできます（または、逆にunshiftとpop を使用することもできます）が、^[2]これらの操作は効率的でない場合もあります。

C++ の標準テンプレート ライブラリはqueue、push/pop 操作のみに制限された" " テンプレート クラスを提供します。J2SE5.0 以降、Java のライブラリにはQueueキュー操作を指定するインターフェイスが含まれています。実装クラスにはLinkedList、および (J2SE 1.6 以降)が含まれます。PHP には、SplQueue クラスと、beanstalk'd やGearmanArrayDequeなどのサードパーティ ライブラリがあります。

JavaScriptで実装されたシンプルなキュー:

クラスQueue {コンストラクター() { this . items = []; }  
     
          
    

    enqueue (要素) { this.items.push (要素) ; }​​​ 
        
    

    dequeue () { this.items.shift ( )を返します; } } 
         
    

キューは、純粋に関数的なデータ構造として実装することもできます。^[3]実装には2つあります。最初の実装では、平均して の操作あたりしか達成されません。つまり、償却時間は ですが、個々の操作には かかる場合があります。ここで、nはキュー内の要素数です。2番目の実装はリアルタイムキュー^[4]と呼ばれ、最悪の場合 O(1) 時間で操作を実行してキューを永続化できます。これはより複雑な実装であり、メモ化を伴う遅延リストが必要です。 ${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

このキューのデータは、 および という 2 つの片方向リンク リストに格納されます。リストはキューの先頭部分を保持します。リストは、残りの要素 (キューの最後尾とも呼ばれます) を逆の順序で保持します。 の先頭にノードを追加することで、 をキューの先頭に簡単に挿入できます。また、が空でない場合は、 の先頭のノードを削除することで、 をキューの最後から簡単に削除できます。が空の場合、リストは逆順にされて に割り当てられ、 の先頭が削除されます。 ${\displaystyle f}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$${\displaystyle f}$${\displaystyle r}$${\displaystyle r}$

挿入 ("エンキュー") には常に時間がかかります。リストが空でない場合、削除 ("デキュー") には 時間がかかります。が空の場合、逆の処理は かかります(は 内の要素数) 。ただし、 内のすべての要素を挿入する必要があり、 内の各要素に挿入時と逆の一定のコストを割り当てることができる ため、これは償却時間であると言えます。${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle r}$${\displaystyle r}$${\displaystyle O(n)}$${\displaystyle n}$${\displaystyle f}$${\displaystyle O(1)}$ ${\displaystyle f}$

リアルタイム キューは、償却なしですべての操作の時間を実現します。この説明は技術的なものになりますので、リストの場合、 はその長さを表し、NIL は空のリストを表し、は先頭がhで末尾がtであるリストを表すことを思い出してください。 ${\displaystyle O(1)}$${\displaystyle l}$${\displaystyle |l|}$${\displaystyle \operatorname {CONS} (h,t)}$

キューを実装するために使用するデータ構造は、3 つの単方向リンク リスト で構成されます。ここで、fはキューの先頭、rはキューの最後尾を逆順にしたものです。この構造の不変条件は、s がfの最初の要素を除いた最後尾、つまり であることです。キューの末尾はほぼ であり、に要素x を挿入することはほぼ です。 ほぼ であると言われるのは、どちらの結果でも であるためです。不変条件を満たすためには、補助関数を呼び出す必要があります。が空のリストであるかどうか (この場合は ) によって、2 つのケースを考慮する必要があります。正式な定義は であり、はfの後にr を逆にしたものです。 ${\displaystyle (f,r,s)}$${\displaystyle |r|}$${\displaystyle |s|=|f|-|r|}$${\displaystyle (\operatorname {CONS} (x,f),r,s)}$${\displaystyle (f,r,s)}$${\displaystyle (f,r,s)}$${\displaystyle (f,\operatorname {CONS} (x,r),s)}$${\displaystyle |s|=|f|-|r|+1}$${\displaystyle aux}$${\displaystyle s}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}$${\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}$${\displaystyle f'}$

fの後にr を逆にしたものを返す関数を と呼びます。さらに、この関数が呼び出されたときに となるので、 と仮定します。より正確には、 、となる 3 つのリストを入力として受け取り、 f、rを逆にしたもの、およびa を連結したものを返す遅延関数を定義します。すると となります。rotate の帰納的定義はおよび です。その実行時間は ですが、遅延評価が使用されるため、計算によって結果が強制されるまで計算は遅延されます。 ${\displaystyle \operatorname {逆} (f,r)}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {回転} (f,r,a)}$${\displaystyle |r|=|f|+1}$${\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}$${\displaystyle \operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)}$${\displaystyle \operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))}$${\displaystyle O(r)}$

データ構造のリストsには 2 つの目的があります。このリストは、s が空のリストである場合に限り、のカウンタとして機能します。このカウンタにより、後方のリストが前方のリストより長くならないことが保証されます。さらに、 fの末尾であるs を使用すると、各末尾および挿入操作中に (遅延) リストfの一部の計算が強制されます。したがって、 の場合、リストf は完全に強制されます。そうでない場合、fの内部表現は追加の追加の追加の... の追加である可能性があり、強制は定数時間の操作ではなくなります。 ${\displaystyle |f|-|r|}$${\displaystyle |f|=|r|}$${\displaystyle |f|=|r|}$

• イベントループ- イベントはキューに保存されます
• メッセージキュー
• 優先キュー
• 待ち行列理論
• スタック（抽象データ型） - キューの「反対」：LIFO（後入れ先出し）

•  この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「Bounded queue」。アルゴリズムとデータ構造の辞書。NIST 。

• ドナルド・クヌース著『コンピュータプログラミングの技法』第 1 巻:基本アルゴリズム、第 3 版。Addison-Wesley、1997 年。ISBN 0-201-89683-4。セクション 2.2.1: スタック、キュー、デキュー、pp. 238–243。 
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション10.1 :スタックとキュー、pp. 200–204。 
• William Ford、William Topp。C ++ および STL によるデータ構造、第 2 版。Prentice Hall、2002 年。ISBN 0-13-085850-1。第 8 章: キューと優先度キュー、386 ～ 390 ページ。 
• Adam Drozdek。C ++ のデータ構造とアルゴリズム、第 3 版。Thomson Course Technology、2005 年。ISBN 0-534-49182-0。第 4 章: スタックとキュー、pp. 137–169。 

ウィキメディア・コモンズには、キューデータ構造に関連するメディアがあります。

• STL クイックリファレンス
• スタック、キュー、デキュー、赤黒木の VBScript 実装