キュー（列、データ構造、待ち行列理論）

特徴と基本操作

抽象的なキューは、単純な規律に従う。すなわち first in, first out（FIFO、先入れ先出し）である。基本操作には、enqueue（末尾に要素を追加する）、dequeue（先頭から取り除く）、peek（取り除かずに先頭要素を確認する）がある。キューには、容量が固定された bounded（有界）と、容量を事実上持たない unbounded（無界）があり、あふれたときの挙動には、処理を待たせる、到着した新しい要素を捨てる、エラーを通知する、などが含まれる。FIFOは、最後に入ったものが最初に出る LIFO のスタックとは対照的であり、また、順序がキーによって決まる優先度ベースの構造とも異なる。

種類と実装

• 配列や単方向連結リストで実装された単純なキュー。enqueue と dequeue をわかりやすく行える。
• 循環バッファー（リングバッファー）。固定長の保存領域を使い、要素を動かさずに空き領域を効率よく再利用する。
• 両端キュー（deque）。両端で挿入と削除ができる。優先度キューは、到着時刻ではなく優先度で要素を並べる。
• 並行キューとロックフリー実装。マルチスレッド・プログラムや高性能システム向けに設計される。

待ち行列理論と性能

待ち行列理論は、待ち行列を数学的に研究する分野である。モデルは、到着過程、サービス過程、サーバー数、容量制約を記述し、平均待ち時間、行列長、スループット、サーバー利用率などの指標を見積もる。一般的な略記で表される標準的な記法や単純モデルは、ボトルネックの分析や、電話、交通、製造、コンピュータネットワークにおける資源配分の判断に役立つ。研究される行動には、列に加わるのをやめる balking（加入拒否）、順番が来る前に離れる reneging（途中離脱）、および優先度規律が含まれる。

用途と例

キューはきわめて広く使われている。たとえば、切符売り場の列、窓口の順番待ち、レストランの待機リスト、空港の保安検査などである。コンピューティングでは、ジョブスケジューラ、印刷キュー、メッセージキュー、イベントループ、さらに幅優先探索のようなアルゴリズムに現れる。キューは、生産側と消費側を調整し、到着速度と処理速度のずれをなだらかにし、オペレーティングシステムや分散システムの基礎的な構成要素となる。

社会的・文化的な注記

列に並ぶことは、公平さと順序に関する社会規範を伴う。割り込みは広く非難される。また、この語には歴史や文化における別の意味もある。たとえば、特定の社会で着用されたり、着用を求められたりした、編み込んだ長い髪の束を指して「queue」と呼ぶことがある。技術的な側面と人間的な側面の両方を意識すると、単純な順序づけの原理が、技術、組織、そして日常生活をどのように形づくるかが見えてくる。