線形キューと円形キューの主な違いは、線形キューはデータを順番に並べていくのに対し、円形キューは最後の要素を最初の要素に戻してつなぐことで円に近い形でデータを並べることです。
データ構造とは、データを効率的に利用するための体系的な整理方法です。
データ構造を実装する際には、時間的複雑性と空間的複雑性を考慮することが重要です。
時間の複雑さは実行時間を表し、空間の複雑さはデータ構造の必要メモリ量を表す。
計算機における主要なデータ構造の1つに待ち行列があります。
待ち行列には、線形待ち行列と循環待ち行列の2種類があります。
リニアキューとは
線形キューとは、直線のようなキューです。
これは、一連のデータ要素を次々に並べたものです。
したがって、片方の端から新しい要素をキューに追加することが可能です。
したがって、この操作をenqueueと呼ぶ。
同様に、もう一方の端からキューから要素を削除することが可能である。
そして、この操作をdequeueと呼ぶ。
待ち行列の前方をhead、最後方をtailまたはrearと呼ぶ。
線形待ち行列では、後方から新しい項目を挿入し、前方から項目を削除することが可能である。
また、待ち行列は、ATMの機械にアクセスするために一列に並んで待っている人に似ています。
新しい人が来て、行列の最後に加わり、行列の最初の人が機械にアクセスできる。
線形待ち行列に対して、いくつかの操作を行うことができる。
待ち行列をゼロに初期化することができる。
また、待ち行列が空であるかどうかも調べることができる。
もう一つの操作は、待ち行列が空であるかどうかを調べることである。
これらは、enqueue と dequeue の操作に加えて、線形キューに対して実行する一般的な操作です。
線形キューは実装が簡単な反面、いくつかの欠点があります。
キューから項目を削除すると、より多くのスペースが生まれます。
しかし、アンダーフロー状態を引き起こす可能性があるため、新しい要素を入力することはまだ困難です。
円形キューは、この問題を克服するのに役立ちます。
循環型待ち行列とは
円形キューでは、最後の項目が最初の項目に戻って接続し、円を作ります。
したがって、円形キューはリングバッファとも呼ばれます。
図2: 24バイトのキーボード円形キュー
円形キューは両端を結ぶので、最初の項目は最後の項目の後に来ます。
円形待ち行列では、実際に待ち行列が一杯になるまで、オーバーフロー条件はありません。
従って、新しい要素を入力するのは簡単です。
さらに、円形キューは以下の2つの条件に従って動作する。
maxSize は、キューが構成できる項目の最大数を示す。
rear = (rear +1 ) % maxSize;
front = (front + 1) % maxSize;
リニアキューとサーキュラーキューの違い
定義
線形待ち行列は、現実の待ち行列と同様にデータの並びとして格納する線形データ構造であるのに対し、円形待ち行列は、最後の項目が最初の項目に戻って円を形成する線形データ構造です。
これが線形待ち行列と円形待ち行列の主な違いです。
挿入と削除
線形キューでは、後方から新しい項目を入力し、前方から項目を削除する ことが可能である。
しかし、円形待ち行列では、どの位置からでも要素の入力と削除が可能である。
従って、この点も線形待ち行列と円形待ち行列の違いと言える。
メモリ容量
さらに、メモリ容量も線形キューと円形キューの違いの一つです。
線形キューは、円形キューよりも多くのメモリを必要とする。
パフォーマンス
さらに、効率も線形キューと円形キューの違いの一つです。
円形キューは線形キューよりも効率的です。
結論
待ち行列には、線形待ち行列と円形待ち行列の2種類があります。
線形待ち行列と循環待ち行列の主な違いは、線形待ち行列はデータを順番に並べるのに対し、循環待ち行列は最後の要素を最初の要素に戻すことで円に似た形でデータを並べることである。
