両端キュー

コンピュータサイエンスにおいて、両端キュー（ deque、/ dɛk / DEK^[1]と略される）は、キューを一般化した抽象データ型であり、要素を先頭（ヘッド）または最後尾（テール）に追加したり削除したりすることができます。[^2]これはヘッドテール連結リストと呼ばれることもありますが、正確にはdequeの特定のデータ構造の実装を指します（以下を参照）。

命名規則

Deque はdequeue と書かれることもありますが、 dequeueは「キューから削除する」という意味の動詞でもあるため、技術文献や技術文書ではこの用法は一般的に推奨されていません。ただし、いくつかのライブラリや、 Aho、Hopcroft、Ullmanなどの一部の著者は、教科書Data Structures and Algorithmsでdequeueと表記しています。Concepts in Programming Languagesの著者であるJohn Mitchellもこの用語を使用しています。

区別とサブタイプ

これは、キュー抽象データ型や先入れ先出しリスト ( FIFO ) とは異なります。キュー抽象データ型や先入れ先出しリストでは、要素は一方の端にのみ追加でき、もう一方の端からのみ削除できます。この一般的なデータクラスには、いくつかのサブタイプがあります。

入力制限付きデックとは、削除は両端から実行できますが、挿入は一方の端からのみ実行できるデックです。
出力制限付きデキューは、挿入は両端で実行できますが、削除は一方の端からのみ実行できます。

コンピューティングにおける基本的かつ最も一般的なリストタイプであるキューとスタックは、デキューの特殊化と見なすことができ、デキューを使用して実装できます。デキューは、ユーザーが両端でプッシュ操作とポップ操作を実行できるデータ構造であり、要素の順序を柔軟に管理できます。

オペレーション

deque の基本的な操作は、両端でのenqueueとdequeueです。また、一般的には、その端にある値をデキューせずに返す peek操作も実装されています。

名前は言語によって異なりますが、主な実装は次のとおりです。

実装

deque を効率的に実装するには、修正された動的配列を使用する方法と、二重にリンクされたリストを使用する方法の少なくとも 2 つがあります。

動的配列アプローチでは、両端から拡張できる動的配列のバリアント(配列デックと呼ばれることもあります) を使用します。これらの配列デックには、定数時間のランダムアクセス、参照の優れた局所性、中間での非効率的な挿入/削除など、動的配列のすべてのプロパティがあり、さらに、片側だけではなく両端での償却定数時間の挿入/削除が追加されています。一般的な実装には次の 3 つがあります。

deque の内容を循環バッファに格納し、バッファがいっぱいになったときにのみサイズを変更します。これにより、サイズ変更の頻度が減ります。
基になる配列の中央から deque コンテンツを割り当て、どちらかの端に到達したときに基になる配列のサイズを変更します。このアプローチでは、特に要素が片方の端にのみ挿入される場合、より頻繁なサイズ変更が必要になり、より多くのスペースが無駄になる可能性があります。
複数の小さな配列に内容を保存し、必要に応じて先頭または末尾に追加の配列を割り当てます。インデックスは、各小さな配列へのポインターを含む動的配列を保持することによって実装されます。

純粋に機能的な実装

両端キューは、純粋に関数的なデータ構造として実装することもできます。^[3]^{: 115}実装には2つのバージョンがあります。最初のバージョンは「リアルタイムデキュー」と呼ばれ、以下で示します。これは、最悪ケース時間 $O$ $(1)$ で操作を実行してキューを永続化できますが、メモ化付きの遅延リストが必要です。遅延リストもメモ化も使用しない2番目のバージョンは、セクションの最後で示します。永続性を使用しない場合の償却時間は $O$ $(1)$ ですが、操作の最悪ケースの計算量は $O$ $($ $n$ $)$ です。ここで、 $n$ は両端キューの要素数です。

リストの場合、はその長さを表し、はl空のリストを表し、は先頭がで末尾がであるリストを表すことを思い出してください。関数とは、それぞれ最初の要素のないリスト、およびの最初の要素を返します。またはの場合、関数とはそれぞれ空のリストとを返します。 |l|NILCONS(h, t)htdrop(i, l)take(i, l)liil|l| < il

遅延再構築とスケジュールによるリアルタイムのデキュー

両端キューは、長さのキューの先頭を含むリンクリスト(len_front, front, tail_front, len_rear, rear, tail_rear)であるfront6組として表現されます。同様に、は、長さのキューの最後尾の逆を表すリンクリストです。さらに、およびであることが保証されています。直感的には、先頭と最後尾の両方に、要素の 3 分の 1 マイナス 1 から 3 分の 2 プラス 1 までが含まれることを意味します。最後に、およびはの末尾、の末尾であるため、いくつかの遅延操作が強制される瞬間をスケジュールできます。両端キューに先頭リストの要素と後部リストの要素が含まれる場合、のときに、挿入と削除の後も不等式不変条件が満たされることに注意してください。つまり、各再バランス調整の間には最大での操作が発生する可能性があります。 len_frontrearlen_rear|front| ≤ 2|rear|+1|rear| ≤ 2|front|+1tail_fronttail_rearfrontrearnnid(i+d) ≤ n/2n/2

まず、デキューの先頭に影響するさまざまな操作 (cons、head、tail) の実装を示します。これらの実装は、必ずしも不変条件を尊重するわけではありません。2 回目に、不変条件を満たさないデキューを不変条件を満たすように変更する方法を説明します。ただし、先頭が空の場合、後部には最大で 1 つの要素があるという点で、不変条件を使用します。リストの後部に影響する操作は、同様に対称性によって定義されます。

empty  =  ( 0 ,  NIL ,  NIL ,  0 ,  NIL ,  NIL ) 
fun  insert' ( x ,  ( len_front ,  front ,  tail_front ,  len_rear ,  rear ,  tail_rear ))  = 
  ( len_front+ 1 ,  CONS ( x ,  front ),  drop ( 2 ,  tail_front ),  len_rear ,  rear ,  drop ( 2 ,  tail_rear )) 
fun  head ((_,  CONS ( h ,  _),  _,  _,  _,  _))  =  h 
fun  head ((_,  NIL ,  _,  _,  CONS ( h ,  NIL ),  _))  =  h 
fun  tail' (( len_front ,  CONS ( head_front ,  front ),  tail_front ,  len_rear ,  rear ,  tail_rear ))  = 
  ( len_front  -  1 、 front 、 drop ( 2 、 tail_front )、 len_rear 、 rear 、 drop ( 2 、 tail_rear )) 
fun  tail' ((_、 NIL 、 _、 _、 CONS ( h 、 NIL )、 _))  = 空

残っているのは、またはが不変条件を破ったbalance場合に deque のバランスを再調整するメソッドを定義する方法です。メソッドおよびは、最初におよびを適用し、次にを適用することで定義できます。 insert'tailinserttailinsert'tail'balance

fun  balance ( q  as  ( len_front 、 front 、 tail_front 、 len_rear 、 rear 、 tail_rear ))  = 
  let  floor_half_len  =  ( len_front  +  len_rear )  /  2  in 
  let  ceil_half_len  =  len_front  +  len_rear  -  floor_half_len  in 
  if  len_front  >  2 *len_rear+ 1  then 
    let  val  front'  =  take ( ceil_half_len 、 front ) 
        val  rear'  =  rotateDrop ( rear 、 floor_half_len 、 front ) 
    in  ( ceil_half_len 、 front' 、 front' 、 floor_half_len 、 rear' 、 rear' ) 
  else  if  len_front  >  2 *len_rear+ 1  then 
    let  val  rear'  =  take ( floor_half_len 、 rear ) 
        val  front'  =  rotateDrop ( front 、 ceil_half_len 、 rear ) 
    in  ( ceil_half_len 、 front' 、 front' 、 floor_half_len 、 rear' 、 rear' )
  それ以外の場合 q

ここで、とのrotateDrop(front, i, rear))連結を返します。これはの内容に入れられ、にまだ含まれていないの内容が入れられます。要素の削除には時間がかかるため、遅延処理を使用して、各操作ごとに 2 つの削除が実行され、要素が 2 つずつ削除されるようにします。 frontdrop(i, rear)front' = rotateDrop(front, ceil_half_len, rear)front'frontrearrear'n $O(n)$ tail'insert'

fun  rotateDrop ( front ,  i ,  rear )  = 
  if  i  <  2  then  rotateRev ( front ,  drop ( i ,  rear ),  NIL ) 
  else  let  CONS ( x ,  front' )  =  front  in 
    CONS ( x ,  rotateDrop ( front' ,  j- 2 ,  drop ( 2 ,  rear )))

ここで、はrotateRev(front, middle, rear)、先頭、中央を反転したもの、最後尾を返す関数です。この関数は、各ステップで 1 ステップ実行されinsert'、tail'一定の時間で一定のステップを踏むことで、ステップごとに計算できるように遅延を使用して定義されています。この関数は、2 または 3 である不変量を使用します|rear|-2|front|。

fun  rotateRev ( NIL 、 rear 、 a )  = 
  river ( rear ) ++a 
fun  rotateRev ( CONS ( x 、 front )、 rear 、 a )  = 
  CONS ( x 、 rotateRev ( front 、 drop ( 2 、 rear )、 river ( take ( 2 、 rear )) ++a ))

ここで++、関数は 2 つのリストを連結します。

怠惰のない実装

$実装の遅延部分がなければ、これはO (1)$ 償却時間でのキューの非永続実装になることに注意してください。この場合、リストtail_frontとをtail_rear両端キューの表現から削除できます。

言語サポート

Adaのコンテナは、それぞれ動的配列とリンクリストの実装用に汎用パッケージAda.Containers.Vectorsとを提供します。Ada.Containers.Doubly_Linked_Lists

C++ の標準テンプレートライブラリは、複数の配列とリンクリストの実装用に、それぞれクラステンプレートstd::dequeとを提供します。std::list

Java 6 以降、Java のコレクションフレームワークは、Deque両端で挿入と削除の機能を提供する新しいインターフェイスを提供します。これは、ArrayDeque(これも Java 6 の新機能) やなどのクラスによって実装され、LinkedListそれぞれ動的配列とリンクリストの実装を提供します。ただし、はArrayDeque、その名前に反して、ランダムアクセスをサポートしません。

Javascript の配列プロトタイプとPerlの配列は、両端の要素の削除 (shift と pop) と追加 (unshift と push) の両方をネイティブでサポートしています。

Python 2.4 では、collectionsdeque オブジェクトをサポートするモジュールが導入されました。これは、固定長のサブ配列の二重リンクリストを使用して実装されています。

PHP 5.3 以降、PHP の SPL 拡張機能には、Deque データ構造を実装するために使用できる 'SplDoublyLinkedList' クラスが含まれています。以前は、Deque 構造を作成するには、代わりに配列関数 array_shift/unshift/pop/push を使用する必要がありました。

GHCの Data.Sequence モジュールは、Haskellで効率的で機能的な deque 構造を実装します。実装では、サイズが注釈された2～3 本のフィンガーツリーを使用します。純粋に機能的な (したがって永続的でもある) ダブルキューを実装する (高速な) 方法は他にもあります (そのほとんどは、遅延評価を多用しています)。^[3]^[4] Kaplan と Tarjan は、最適な合流永続的連結可能 deque を実装した最初の人物です。^[5]彼らの実装は、遅延評価を使用しないという意味で厳密に純粋に機能的でした。Okasaki は、ブートストラップされたデータ構造で遅延評価を使用し、パフォーマンス境界を最悪のケースから償却まで下げることで、データ構造を簡素化しました。^[6] Kaplan、Okasaki、および Tarjan は、遅延評価を使用するか、より広範だが制限のある方法で変異をより効率的に使用して実装できる、より単純でブートストラップされていない償却バージョンを作成しました。^[7]ミハエスクとタルジャンは、より単純な（しかし依然として非常に複雑な）連結可能なデックの厳密に純粋に機能的な実装と、さらにはるかに単純な連結不可能な純粋に機能的なデックの実装を作成した。どちらも最悪のケースの境界が最適である。^[8]

Rust には、std::collections拡張可能なリングバッファを使用して両端キューを実装する VecDeque が含まれています。

複雑

二重リンクリストの実装では、割り当て/割り当て解除のオーバーヘッドがないと仮定すると、すべての deque 操作の時間計算量はO(1)です。さらに、イテレータが与えられた場合、中間での挿入または削除の時間計算量は O(1) です。ただし、インデックスによるランダムアクセスの時間計算量は O(n) です。
増大する配列では、すべての deque 操作の償却時間計算量はO(1)です。さらに、インデックスによるランダムアクセスの時間計算量は O(1) ですが、途中の挿入または削除の時間計算量はO(n)です。

アプリケーション

デキューを使用できる例の 1 つは、ワークスチールアルゴリズムです。^[9]このアルゴリズムは、複数のプロセッサのタスクスケジューリングを実装します。各プロセッサごとに、実行するスレッドを含む個別のデキューが維持されます。次のスレッドを実行するために、プロセッサはデキューから最初の要素を取得します (「最初の要素を削除」デキュー操作を使用)。現在のスレッドが分岐した場合、デキューの先頭に戻され (「先頭に要素を挿入」)、新しいスレッドが実行されます。プロセッサの 1 つが自身のスレッドの実行を終了すると (つまり、デキューが空になると)、別のプロセッサからスレッドを「スチール」できます。つまり、別のプロセッサのデキューから最後の要素を取得し (「最後の要素を削除」)、それを実行します。ワークスチールアルゴリズムは、並列プログラミング用の Intel の Threading Building Blocks (TBB) ライブラリで使用されます。

参照

参考文献

^ Jesse Liberty、Siddhartha Rao、Bradley Jones。C ++ in One Hour a Day、Sams Teach Yourself、第 6 版。Sams Publishing、2009 年。ISBN 0-672-32941-7 。レッスン 18: STL 動的配列クラス、pp. 486。
^ Donald Knuth . The Art of Computer Programming、第 1 巻:基本的なアルゴリズム、第 3 版。Addison-Wesley、1997 年。ISBN 0-201-89683-4。セクション 2.2.1: スタック、キュー、およびデック、pp. 238–243。
^ ab Okasaki, Chris (1996 年 9 月). Purely Functional Data Structures (PDF) (博士論文). カーネギーメロン大学. CMU-CS-96-177.
^ Adam L. Buchsbaum と Robert E. Tarjan。データ構造ブートストラップによる合流的永続的デック。Journal of Algorithms、18(3):513–547、1995 年 5 月。(pp. 58、101、125)
^ Haim Kaplan と Robert E. Tarjan。連結可能なソート済みリストの純粋関数表現。ACM Symposium on Theory of Computing、202～211 ページ、1996 年 5 月。(pp. 4、82、84、124)
^ Chris Okasaki (1997 年 8 月)、連結可能な両端キュー、ACM SIGPLAN Notices Volume 32 Issue 8
^ Haim Kaplan、Chris Okasaki、Robert E. Tarjan (2000)、Simple Confluently Persistent Catenable Lists、SIAM Journal on Computing Vol. 30、Iss. 3
^ Radu Mihaescu と Robert Tarjan (2003 年 8 月)、「Pure Lisp における連結可能なデックに関するノート」、プリンスタウン大学、COS 528、2003 年秋
^ Blumofe, Robert D.; Leiserson, Charles E. (1999). 「ワークスティーリングによるマルチスレッド計算のスケジューリング」(PDF) . J ACM . 46 (5): 720–748. doi :10.1145/324133.324234. S2CID 5428476.

外部リンク

包括的な C アーカイブネットワークでの型安全なオープンソースの deque 実装
SGI STL ドキュメント: deque<T, Alloc>
コードプロジェクト: STL Deque コンテナの詳細な調査
C での Deque 実装 2014-03-06 にWayback Machineでアーカイブされました
スタック、キュー、デキュー、赤黒木の VBScript 実装
Haskell における連結不可能な deque の複数の実装

[1] Jesse Liberty、Siddhartha Rao、Bradley Jones。C ++ in One Hour a Day、Sams Teach Yourself、第 6 版。Sams Publishing、2009 年。ISBN 0-672-32941-7 。レッスン 18: STL 動的配列クラス、pp. 486。

[2] Donald Knuth . The Art of Computer Programming、第 1 巻:基本的なアルゴリズム、第 3 版。Addison-Wesley、1997 年。ISBN 0-201-89683-4。セクション 2.2.1: スタック、キュー、およびデック、pp. 238–243。

[functional-3] Okasaki, Chris (1996 年 9 月). Purely Functional Data Structures (PDF) (博士論文). カーネギーメロン大学. CMU-CS-96-177.

[4] Adam L. Buchsbaum と Robert E. Tarjan。データ構造ブートストラップによる合流的永続的デック。Journal of Algorithms、18(3):513–547、1995 年 5 月。(pp. 58、101、125)

[5] Haim Kaplan と Robert E. Tarjan。連結可能なソート済みリストの純粋関数表現。ACM Symposium on Theory of Computing、202～211 ページ、1996 年 5 月。(pp. 4、82、84、124)

[6] Chris Okasaki (1997 年 8 月)、連結可能な両端キュー、ACM SIGPLAN Notices Volume 32 Issue 8

[7] Haim Kaplan、Chris Okasaki、Robert E. Tarjan (2000)、Simple Confluently Persistent Catenable Lists、SIAM Journal on Computing Vol. 30、Iss. 3

[8] Radu Mihaescu と Robert Tarjan (2003 年 8 月)、「Pure Lisp における連結可能なデックに関するノート」、プリンスタウン大学、COS 528、2003 年秋

[jacm-9] Blumofe, Robert D.; Leiserson, Charles E. (1999). 「ワークスティーリングによるマルチスレッド計算のスケジューリング」(PDF) . J ACM . 46 (5): 720–748. doi :10.1145/324133.324234. S2CID 5428476.