キュー (キュー) とは | 意味や読み方など丁寧でわかりやすい用語解説

キュー (キュー) の読み方

日本語表記

キュー (キュー)

英語表記

queue (キュー)

キュー (キュー) の意味や用語解説

キューは、コンピュータサイエンスにおける基本的なデータ構造の一つであり、データを一時的に保持し、決められた順序で処理するために用いられる。その最大の特徴は、FIFO（First-In, First-Out）、すなわち「先入れ先出し」という原則に従うことである。これは、最初に追加されたデータが、最初に取り出されるというルールを意味する。この振る舞いは、現実世界における順番待ちの列と同様であり、多数の処理要求を公平に、かつ整然と捌くための仕組みとして、様々なシステムで広く利用されている。 キューに対する基本的な操作は「エンキュー」と「デキュー」の二つである。エンキューは、キューの末尾に新しいデータを追加する操作を指す。一方、デキューは、キューの先頭からデータを取り出す操作を指す。キューのデータの入り口はリア（末尾）、出口はフロント（先頭）とも呼ばれる。データは常にリアから追加され、フロントから取り出されるため、格納された順序性が厳密に保たれる。この単純明快なルールが、キューの有用性の根幹をなしている。 プログラム上でキューを実装する方法はいくつか存在するが、代表的なものとして配列を用いる方法と連結リストを用いる方法がある。配列による実装は、固定長のメモリ領域を確保し、先頭と末尾の位置を指し示すインデックス変数を管理することで実現する。この方法は比較的シンプルに実装できるが、あらかじめ配列のサイズを決めておく必要があるため、格納するデータ数が想定を超えるとオーバーフローを引き起こす可能性がある。また、エンキューとデキューを繰り返すうちに、配列内に使用済みの領域が発生し、メモリ効率が悪化することがある。この問題を解決するため、配列の終端と先端を論理的につなげてリング状に扱う、リングバッファ（サーキュラーキュー）という実装も存在する。一方、連結リストによる実装は、各データが次のデータへの参照（ポインタ）を持つノードで構成される。データの追加や削除のたびに動的にメモリを確保・解放するため、キューのサイズを事前に固定する必要がなく、メモリを無駄なく利用できるという利点がある。ただし、ポインタの管理が必要となるため、配列による実装に比べてやや複雑になる。 キューのFIFOという特性は、ITシステムの様々な場面で応用されている。最も身近な例は、プリンターの印刷ジョブ管理である。複数のユーザーから送られてきた印刷要求はキューに一時的に格納され、受け付けた順番に一つずつプリンターで処理される。これにより、誰の印刷要求が先に処理されるかという公平性が保証される。Webサーバーにおけるリクエスト処理も同様である。サーバーが同時に処理できるリクエスト数には上限があるため、それを超えるアクセスが集中した場合、後続のリクエストはキューに待機させ、処理が完了したものから順次応答を返す。これにより、サーバーの過負荷を防ぎ、システム全体の安定稼働に寄与する。また、異なるシステムやコンポーネント間でデータを非同期に受け渡すメッセージキューイングシステムは、大規模で複雑なシステムにおいて不可欠な技術である。送信側はメッセージをキューに送信するだけで処理を完了でき、受信側は自身の都合の良いタイミングでキューからメッセージを取り出して処理を開始できる。これにより、システム間の依存関係を疎にし、柔軟性と耐障害性を高めることが可能となる。その他、オペレーティングシステムが実行すべきタスクを管理するスケジューリングや、グラフ構造を探索する幅優先探索（BFS）アルゴリズムにおいても、キューは中核的な役割を担っている。 基本的なFIFOのキュー以外にも、特定の要件に合わせて機能を拡張した派生形が存在する。両端キュー（Deque: Double-Ended Queue）は、キューの先頭と末尾の両方からデータの追加・削除ができるデータ構造である。また、優先度付きキュー（Priority Queue）は、格納される各データが優先度を持ち、デキューする際には格納順に関わらず最も優先度の高いデータが取り出される仕組みである。これは、緊急性の高い処理を優先的に実行する必要がある場合に用いられる。 キューを学ぶ上で、しばしば比較対象となるのがスタックである。スタックはLIFO（Last-In, First-Out）、すなわち「後入れ先出し」の原則に従うデータ構造で、最後に追加したデータが最初に取り出される。キューが処理の順序性を保証するのに対し、スタックは直近のデータを扱うのに適している。どちらのデータ構造を選択するかは、解決したい課題の性質によって決まるため、両者の特性の違いを正確に理解しておくことは、システムエンジニアにとって極めて重要である。