キューとはどのようなデータ構造ですか?

キューは線形データ構造です。キューでは、テーブルのフロントエンドでの削除操作と、テーブルのバックエンドでの挿入操作のみが許可されます。スタックと同様、キューは操作が制限された線形テーブルです。挿入操作が実行される端は、キューと呼ばれます。キューの最後尾、削除操作が実行されます。最後尾はチームの先頭と呼ばれます。

#この記事の動作環境: Windows10 システム、Thinkpad t480 コンピューター。

キューは線形データ構造です。

キューは特殊な線形テーブルです。特別なのは、テーブルの前端 (前) では削除操作のみが許可され、テーブルの後端 (後端) では挿入操作のみが許可されることです。スタックと同様、キューは操作が制限された線形リストです。挿入操作を実行する端はキューの末尾と呼ばれ、削除操作を実行する端はキューの先頭と呼ばれます。キュー内に要素が存在しない場合、それは空のキューと呼ばれます。

キューのデータ要素はキュー要素とも呼ばれます。キュー要素をキューに挿入することをエンキューといい、キュー要素をキューから削除することをデキューといいます。キューでは一方の端での挿入ともう一方の端での削除のみが許可されるため、キューに最も早く入った要素のみが最初にキューから削除できるため、キューは先入れ先出し (FIFO - 最初に) とも呼ばれます。先出し) 線形リスト。

シーケンシャル キュー

シーケンシャル キュー構造を確立するには、連続ストレージ スペースを静的に割り当てるか動的に適用し、管理用の 2 つのポインタを設定する必要があります。 1 つはヘッド要素を指すヘッド ポインター前部で、もう 1 つはキュー内の次の要素の格納場所を指すテール ポインター後部です (図

# を参照)。

キューの最後に要素が挿入されるたびに、rear が 1 ずつ増加し、キューの先頭で要素が削除されるたびに、front が 1 ずつ増加します。挿入および削除操作が進むにつれて、キュー要素の数は変化し続け、キューによって占有される記憶領域もキュー構造に割り当てられた連続領域内で移動します。フロント=リアの場合、キューには要素がありません。これは空のキューと呼ばれます。割り当てを指す連続スペースを超えて後部が増加すると、キューは新しい要素を挿入できなくなりますが、多くの場合、この時点では占有されていない利用可能なスペースが大量に存在します。デキューされたキュー要素。

シーケンシャルキューのオーバーフロー現象:

(1) 「アンダーフロー」現象: キューが空の場合、キューの操作によって引き起こされるオーバーフロー現象。 「アンダーフロー」は正常な現象であり、プログラム制御転送の条件としてよく使用されます。

(2) 「真のオーバーフロー」現象: キューがいっぱいの場合、スタック上のプッシュ操作によりスペース オーバーフローが発生します。 「真のオーバーフロー」はエラー状態であり、回避する必要があります。

(3) 「偽のオーバーフロー」現象: エンキューおよびデキュー操作中に先頭ポインタと末尾ポインタが増加するだけで減少しないため、削除された要素の領域は再利用できません。キュー内の実際の要素数がベクトル空間のサイズよりもはるかに小さい場合、末尾ポインタがベクトル空間の上限を超えているため、キューの操作が不可能になる可能性があります。この現象を「偽オーバーフロー」といいます。

循環キュー

実際にキューを使用する場合、キュー空間を再利用できるようにするために、キューの使用方法がわずかに改良されることがよくあります。挿入または挿入に関係なく、削除、1回 後方ポインタが1インクリメントされるか、前方ポインタが1インクリメントされて割り当てられたキュースペースを超えた場合、この連続スペースの開始位置を指すようにします。実際に MaxSize-1 を 1 ずつ 0 に変更する場合は、剰余演算 Rear%MaxSize と Front%MaxSize を使用してそれを実現できます。これは、実際にはキュー空間を循環空間としてイメージし、その循環空間内の記憶装置を循環的に使用するものであり、このように管理されるキューを循環キューとも呼ぶ。いくつかの単純なアプリケーションに加えて、実際に実用的なキューは循環キューです。

循環キューでは、キューが空の場合は前=後、キューのスペースがすべていっぱいの場合は前=後となります。 2 つの状況を区別するために、循環キューには最大で MaxSize-1 のキュー要素しか含めることができないと規定されており、循環キューに空のストレージ ユニットが 1 つだけ残っている場合、キューはいっぱいになります。したがって、キューが空である条件は、フロント=リアであり、キューがいっぱいである条件は、フロント=(リア 1)%MaxSize です。空のキューと満杯のキューの状況は次の図に示されています。

推奨事項: " プログラミング ビデオ "

以上がキューとはどのようなデータ構造ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。