キュー（抽象データ型）

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

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

TypeScriptで実装されたシンプルなキュー：

class Queue < T > { private items : T [] = [];enqueue ( element : T ) : void { this.items.push ( element ) ; }​​​dequeue ( ) : T | undefined { return this.items.shift ( ) ; }​isEmpty ( ) : boolean { return this.items.length === 0 ; } }​​​

このキューのデータは、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}$挿入する必要があり、挿入されたタイミングの逆の順序で各要素に一定のコストを割り当てることができます。

リアルタイムキューは${\displaystyle O(1)}$償却なしの全操作にかかる時間。この議論は技術的なものになるので、次の点に留意してください。${\displaystyle l}$リスト、${\displaystyle |l|}$長さを表す。${\displaystyle {\texttt {null}}}$空のリストを表し、${\displaystyle {\texttt {cons}}(h,t)}$先頭が${\displaystyle h}$そしてその尻尾は${\displaystyle t}$。

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

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

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

•  この記事は、ポール・E・ブラック著「境界付きキュー」、『アルゴリズムとデータ構造の辞典』、NIST のパブリックドメイン資料を組み込んでいます。