循環キュー

2025年10月21日

“`

循環キュー

英語表記: Circular Queue

概要

循環キューは、「データ構造（リスト, スタック, キュー, ツリー） → キュー」という分類における、基本的なキュー構造が持つ効率上の課題を克服するために考案された仕組みです。通常のキュー（リニアキュー）を配列で実現する際、要素の取り出し（デキュー）によって配列の先頭側に未使用領域（デッドスペース）が生じてしまう問題を解決します。配列の末尾と先頭を論理的につなげることで、配列全体を循環的に利用し、メモリの再利用効率を劇的に向上させることができる、非常に重要な「キューの基本」技術の一つです。

詳細解説

この循環キューという概念は、データ構造の基礎である「キュー」を、限られたメモリ空間でいかに効率良く運用するか、という課題意識から生まれています。

1. リニアキューの課題と循環の必要性

まず、キューの基本動作を確認しましょう。キューは「先入れ先出し」（FIFO: First-In, First-Out）の原則に基づき、データを格納（エンキュー）し、取り出し（デキュー）ます。これを配列で実装する際、リニアキューでは、エンキューは末尾（Rear）で行い、デキューは先頭（Front）から行います。

問題はデキューの際に発生します。要素が取り出されると、Frontポインタが後方に移動しますが、その移動した後の配列の先頭側の領域は空きとなります。しかし、リニアキューの仕組みでは、この空き領域を再利用することなく、エンキューは配列の末尾に向かって進み続けます。結果として、配列の末尾に達すると、たとえ配列の先頭に大量の空きがあっても、「満杯」と判断されてしまい、新しいデータを受け入れられなくなるのです。これは、データ構造を学ぶ上で避けて通れない、配列ベースのキューの大きな非効率性でした。

循環キューは、この非効率性を解消するために、配列の論理的な構造を変更します。配列の最後の要素の次が、配列の最初の要素である、と定義するのです。これにより、データが配列の終端に到達しても、空きがあれば先頭に戻って格納を続けることが可能となり、配列全体を文字通り「循環」利用できるようになります。

2. 動作原理と主要コンポーネント

循環キューの運用には、主に以下の二つのポインタ（インデックス）が必要です。

Front (先頭): 次に取り出す要素の位置を示します。デキュー操作の後に移動します。
Rear (末尾): 次に格納する要素の位置を示します。エンキュー操作の後に移動します。

循環の実現には、ポインタを移動させる際に「剰余演算」（モジュロ演算、%）を用います。配列のサイズを $N$ とすると、ポインタ $P$ を一つ進める操作は、次のように定義されます。

$$P = (P + 1) \bmod N$$

この計算により、インデックスが $N-1$ （配列の最終位置）に達した後に $+1$ すると、自動的に $0$ （配列の先頭）に戻る仕組みが実現します。これが「キューの基本」を効率化する鍵となる技術です。

3. 満杯（Full）と空（Empty）の判定

循環キューを実装する上で、初心者の方が最もつまずきやすいのが、「満杯」と「空」の判定です。

空（Empty）の状態: Front ポインタと Rear ポインタが一致している場合（Front == Rear）。
満杯（Full）の状態: 循環しているため、Front の一つ手前の位置に Rear がいる場合（すなわち、Rear = (Front - 1) mod N の状態）も、Front と Rear が一致しているように見えてしまいます。

もし、すべてのスロットを埋めてしまうと、「空」と「満杯」の区別がつかなくなってしまうため、通常、以下のいずれかの対策が取られます。

要素数を別途管理する: キューに格納されている実際の要素数をカウントする変数を用意し、その変数が $0$ なら空、$N$ なら満杯と判断します。
常に一つ空きを残す（$N-1$ 方式）: 配列のサイズ $N$ に対し、最大 $N-1$ 個までしか格納しないルールを設けます。この場合、Front == (Rear + 1) mod N の状態を「満杯」と定義します。これにより、Front と Rear が一致するのは「空」の場合のみとなり、判定が容易になります。

この判定ロジックこそが、データ構造（リスト, スタック, キュー, ツリー）の学習において、循環キューが「キューの基本」の応用として重要視される理由なのです。

具体例・活用シーン

循環キューは、データの流れが一定で、かつ効率的なメモリ利用が求められる場面で広く活用されています。

1. コンピュータシステムでの活用

OSのバッファ管理: キーボード入力やプリンタ出力など、入出力（I/O）処理はCPUの処理速度に比べて非常に遅いです。これらのデータを一時的に保持するバッファ（緩衝領域）として循環キューがよく使われます。データが絶えず入ってきて、絶えず出ていくという環境では、配列を効率的に再利用できる循環キューが最適です。
通信プロトコルの実装: ネットワークパケットの送受信処理において、パケットを一時的に格納するリングバッファとして利用されます。

2. アナロジー：回転寿司のレーン

循環キューの動きを理解するための、最もわかりやすい比喩は「回転寿司のレーン」です。

想像してみてください。普通の（リニア）キューが、一度使われた席（配列の先頭）を二度と使わず、客が帰るたびに新しい席を後ろにどんどん継ぎ足していくような仕組みだとすれば、店はすぐに満席になってしまいます。

しかし、循環キューが採用されている回転寿司のレーンは違います。

皿の追加（エンキュー）: 厨房（Rear）から新しい皿がレーンに乗せられます。
皿の消費（デキュー）: 客（Front）が皿を取ります。皿が取られた場所は空席になります。
循環: レーンは一周しています。空席になった場所は、すぐに厨房の前に戻ってきて、次の新しい皿を置くための場所として再利用されます。

このように、限られた長さのレーン（配列）を無駄なく使い続けることができるのが、循環キューの大きなメリットです。配列の先頭をデッドスペースにせず、無限に続くかのように再利用できる点が、このデータ構造（リスト, スタック, キュー, ツリー）における「キューの基本」を効率化しているのです。

資格試験向けチェックポイント

循環キューは、特に基本情報技術者試験や応用情報技術者試験のアルゴリズム分野で頻出する、計算問題の定番です。ITパスポートでは概念理解が問われることが多いですが、上位試験では具体的なポインタ操作が問われます。

満杯・空の判定ロジック: 「常に一つ空きを残す」場合の満杯判定式が最も重要です。
- 満杯の条件: (Rear + 1) mod N == Front
- 空の条件: Rear == Front
- これらの条件を正確に理解しているかどうかが問われます。
ポインタの計算問題: 配列サイズ $N$ が与えられ、現在の Front と Rear の値、そしてエンキューまたはデキュー操作が行われた後の新しいポインタの位置を求めさせる問題が出ます。剰余演算（mod N）を正しく適用できるかが鍵となります。
リニアキューとの比較: 循環キューがリニアキューのどの問題点（デッドスペースの発生）を解決しているのか、その目的を問う知識問題も頻出します。
リングバッファとの関係: 循環キューは、しばしば「リングバッファ」という名称で呼ばれることがあります。この二つが同じ概念を指していることを覚えておくと、問題文を読み解く際に役立ちます。