待ち行列は、データ要素が一方の端部（後端）から挿入され、他方の端部（前端）から削除されるＦＩＦＯ順序に従う非原始線形データ構造として説明することができる。 キューの他のバリエーションは、循環キュー、二重終了キュー、および優先順位キューです。
比較表
| 比較基準 | リニアキュー | 循環キュー |
|---|---|---|
| 基本 | データ要素と命令を順番に並べます。 | 最後の要素が最初の要素に接続される円形パターンでデータを配置します。 |
| タスク実行順序 | タスクは前に配置された順に実行されます（FIFO）。 | タスクの実行順序は変わる可能性があります。 |
| 挿入と削除 | 新しい要素が後端から追加され、前面から削除されます。 | 挿入と削除はどの位置でも可能です。 |
| パフォーマンス | 非効率的な | リニアキューよりも効果的です。 |
リニアキューの定義
リニアキューは、合理的に先入れ先出し順リストです。 要素が次々に配置されている直線に似ているため、これは線形と呼ばれます。 それは新しい要素が一方の端で追加され、もう一方の端から削除される要素の同種のコレクションを含みます。 待ち行列の概念は、劇場のチケットを入手するためにチケットカウンタの外側で待機している観客の待ち行列の例によって理解することができる。 このキューでは、人がキューの後端に参加してチケットを受け取り、チケットがキューのフロントエンドで発行されます。
キューで実行されたいくつかの操作があります
- まず、キューがゼロに初期化されます（つまり、空になります）。
- キューが空かどうかを調べます。
- キューがいっぱいかどうかを確認してください。
- 後端からの新しい要素の挿入（エンキュー）。
- フロントエンドからの要素の削除（デキュー）。
キューは2つの方法で実装できます。
- 静的に（配列を使用して）
- 動的に（ポインタを使用して）
線形キューの制限は、キューに空のスペースが含まれている場合でも、キューに新しい要素を追加できないというシナリオを作成することです。 この状況は、下の図に示されています。 ここではすべてのボックスがまだ空の間、後ろが最後のインデックスを指しているので、新しい要素を追加することはできません。
循環キューの定義
循環待ち行列は、線形待ち行列の変形を効果的に克服する線形待ち行列の変形である。 循環キューでは、最後の要素が占有されていてスペースが使用可能であれば、新しい要素がキューの最初の位置に追加されます。 リニアキューになると、挿入は後端から、削除は前端からのみ実行できます。 キュー内で一連の連続した削除を実行した後のフルキューでは、アンダーフロー条件（Rear = max - 1）がまだ存在するために使用可能なスペースがあってもそれ以上新しい要素を追加できないという状況が発生します。
循環キューは、一番最初の要素が最後の要素の後にくるポインタを介して両端を接続します。 また、挿入および削除される要素をトレースできるように、いくつかの追加ロジックを実装することで前面と背面を追跡します。 これにより、循環キューは、実際にキューがいっぱいになるまでオーバーフロー状態を生成しません。
循環キューが続くいくつかの条件：
- Frontは最初の要素を指していなければなりません。
- Front = Rearの場合、キューは空になります。
- 新しい要素が追加されると、キューは値1だけインクリメントされます（Rear = Rear + 1）。
- 要素がキューから削除されると、先頭は1ずつ増加します（Front = Front + 1）。
線形キューと循環キューの主な違い
- 線形待ち行列は、データ要素が順番に並べられている順序付きリストです。 対照的に、循環キューはデータを循環方式で格納します。
- 線形キューは、タスクを実行するためのFIFOの順序に従います（最初の位置に追加された要素は最初の位置で削除されます）。 逆に、循環キューでは、要素に対して実行される操作の順序が変わる可能性があります。
- 要素の挿入と削除は線形キュー、すなわち後端からの追加と前端からの削除で固定されています。 一方、循環キューは、要素が占有されるまで、任意の時点から要素を挿入および削除できます。
- 線形キューはメモリスペースを浪費し、循環キューはスペースを効率的に使用します。
リニアキューの実装
以下に示すアルゴリズムは、キューに要素を追加する方法を示しています。
キューには、キューを格納するための1つの配列と、前後の初期位置-1を格納するための配列を含む3つのデータ変数が必要です。
insert（item、queue、n、rear）{if（rear == n）の場合、 "queue overflow"を表示します。 そうでなければ{rear = rear + 1; queue [rear] = item; }} 以下に示すアルゴリズムは、キュー内の要素の削除を示しています。
delete_circular（item、queue、rear、front）{if（rear == front）の場合、 "queue underflow"を出力します。 else {front = front + 1; item = queue [front]; }} 循環キューの実装
循環キュー内の要素の追加を解釈するためのアルゴリズム。
insert_circular（item、queue、rear、front）{rear =（rear + 1）mod n; （front == rear）ならば、 "queue is full"を表示します。 else {queue [rear] = item; }} アルゴリズムは循環キューの要素の削除を説明します。
delete_circular（item、queue、rear、front）{if（front == rear）の場合、print（ "queue is empty"）; else {front = front + 1; item = queue [front]; }} 結論
線形キューは、挿入操作を実行するために要素が空きスペースに移動する必要がある場合には非効率的です。 これが、空きスペースが存在する場合に要素が任意の位置に追加されるため、循環キューがストレージスペースを適切に使用する一方で、ストレージスペースを無駄にする傾向がある理由です。
