線形キューと循環キューの違いは何ですか
目次:
NS 主な違い 線形キューと循環キューの間は 線形キューはデータを次々に順番に配置し、循環キューは最後の要素を最初の要素に接続して円のようにデータを配置します。
データ構造は、データを効率的に使用するためにデータを編成する体系的な方法です。データ構造を実装するときは、時間と空間の複雑さを考慮することが重要です。時間計算量は実行時間を表し、空間計算量はデータ構造のメモリ要件を表します。コンピューティングにおける主要なデータ構造の1つは、キューです。キューには、線形キューと循環キューの2種類があります。
サークルキュー、リニアキュー、キュー
線形キューとは何ですか
線形キューは、直線に似たキューです。これは、次々とデータ要素のセットで構成されます。したがって、一方の端からキューに新しい要素を追加することができます。したがって、この操作をエンキューと呼びます。同様に、もう一方の端のキューから要素を削除することもできます。そして、この操作をデキューと呼びます。キューの前部はヘッドで、キューの最後はテールまたはリアです。リニアキューでは、後ろから新しいアイテムを挿入したり、前からアイテムを削除したりすることができます。さらに、キューは、ATMマシンにアクセスするためにまっすぐに待っている人々に似ています。新しい人がキューの最後に来て参加し、キューの最初の人がマシンにアクセスします。
図1:線形キュー
線形キューでいくつかの操作を実行できます。キューをゼロに初期化できます。キューが空かどうかを確認することもできます。もう1つの操作は、キューが空かどうかを確認することです。これらは、エンキューおよびデキュー操作に加えて、線形キューで実行するいくつかの一般的な操作です。
線形キューは実装が簡単ですが、いくつかの欠点があります。キューからアイテムを削除すると、より多くのスペースを作成できます。ただし、アンダーフロー状態が発生する可能性があるため、新しい要素を入力するのは依然として難しい場合があります。循環キューは、この問題を克服するのに役立ちます。
循環キューとは何ですか
循環キューでは、最後のアイテムが最初のアイテムに接続して円を作成します。したがって、循環キューはリングバッファとも呼ばれます。
図2:24バイトのキーボード循環キュー
循環キューが両端を接続するため、最初のアイテムは最後のアイテムの後に来ます。キューが実際にいっぱいになるまで、循環キューにオーバーフロー条件はありません。したがって、新しい要素を入力するのは簡単です。
また、循環キューは以下の2つの条件で動作します。 maxSizeは、キューを構成できるアイテムの最大数を示します。
リア=(リア+1)%maxSize;
フロント=(フロント+ 1)%maxSize;
線形キューと循環キューの違い
意味
線形キューは、実際のキューと同様の要素のシーケンスとしてデータを格納する線形データ構造ですが、循環キューは、最後のアイテムが最初のアイテムに接続して円を形成する線形データ構造です。したがって、これが線形キューと循環キューの主な違いです。
挿入と削除
リニアキューでは、後ろから新しいアイテムを入力し、前からアイテムを削除することができます。ただし、循環キューでは、任意の位置から要素を入力および削除できます。したがって、これは線形キューと循環キューのもう1つの違いです。
メモリスペース
さらに、メモリスペースは、線形キューと循環キューのもう1つの違いです。線形キューは、循環キューよりも多くのメモリを必要とします。
パフォーマンス
結論
キューには、線形キューと循環キューの2種類があります。線形キューと循環キューの主な違いは、線形キューはデータを順番に並べるのに対し、循環キューは最後の要素を最初の要素に接続して円のようにデータを配置することです。
リファレンス:
「1。リニアキューチュートリアル。」ネットワークトポロジ(そのタイプ、長所と短所)– IncludeHelp、ここで利用可能2。 「循環キュー|セット1(導入とアレイの実装)。」 GeeksforGeeks、2018年12月24日、こちらから入手できます。
画像提供:
1.コモンズウィキメディア経由のVegpuff自身の作品(CC BY-SA 3.0)による「データキュー」2. MuhannadAjjanによる「循環バッファアニメーション」–コモンズウィキメディア経由の自身の作品(CC BY-SA 4.0)
![線形キューと循環キューの違いは何ですか 線形キューと循環キューの違いは何ですか](https://img.books-kingdom.com/images/002/image-5094.jpg)