循環バッファまたは循環キューは、最後のインデックスと末尾のインデックスが循環構造で接続されている通常のキューの高度なバージョンです。 C++ の循環バッファーは、enqueue() と dequeue() という 2 つのメソッドに従います。これらの方法に基づいて循環バッファまたは循環キューの操作を実行します。
- enqueue() メソッドは、バッファがいっぱいかどうかを確認します。それ以外の場合は、終了インデックスが最後のインデックスであることを確認してください。そうである場合は、末尾の値を 0 に設定します。そうでない場合は、そのインデックスの値だけ末尾の値を増やします。
- dequeue() 関数は、循環キューの先頭インデックスから値を取得します。キューが空の場合は、その空のキューがメッセージに表示されます。それ以外の場合は、最後の値を取得し、キューから削除します。
C++ で循環バッファを実装するプログラム
前述の 2 つの方法に従って、C++ で循環バッファーを実装します。 C++ で循環キューを実装するためのすべての手順を検討してみましょう。
#include
名前空間 std を使用します。
構造体MyQueue
{
整数 頭 、 しっぽ ;
int Qsize;
整数 * 新しい到着;
マイキュー ( 整数いいえ ) {
頭 = しっぽ = -1 ;
Qsize = サイズ;
NewArr = 新しい整数 [ s 】 ;
}
エンキューを無効にする ( 整数 ) ;
int デキュー ( ) ;
無効なショーキュー ( ) ;
} ;
コードから始めて、最初に「MyQueue」構造体を作成して、先頭変数と末尾変数を初期化します。 head 変数はフロント インデックスを表し、tail は配列のリア バック インデックスを表します。その後、変数「Qsize」で示される循環キューのサイズが定義されます。
次に、循環キューの値を格納する動的に割り当てられる配列「NewArr」を定義します。次に、コンストラクターである MyQueue() を呼び出し、循環キュー サイズの「sz」パラメーターを渡します。 MyQueue() コンストラクター内で、先頭ポインターと末尾ポインターに「-1」値を割り当てます。この負の値は、キューが現在空であることを示します。次に、循環キューのサイズを表す「sz」値を割り当てます。 「NewArr」循環キューには、指定された「sz」サイズ内の整数の配列を作成するための new キーワードが設定されます。
次に、enQueue() 関数と dequeue() 関数を定義します。 enqueue() は、定義された循環キューに末尾から値を挿入します。ただし、循環キューの先頭の要素は dequeue() 関数によって削除されます。 showQueue() メンバー関数は、循環キューの値を表示します。
ステップ 1: 循環バッファーに要素を挿入する関数を作成する
前のステップでは、プライベート メンバーが初期化されるクラスを設定し、循環キューを実装するようにプライベート メンバー関数を設定しました。次に、循環キューを作成する関数を設定し、アルゴリズムを使用して循環キュー内に値を挿入します。
void MyQueue::enQueue ( 整数 ){
もし ( ( 頭 == 0 && しっぽ == Qサイズ - 1 ) || ( しっぽ == ( 頭 - 1 ) % ( Qサイズ - 1 ) ) )
{
コート << 」 \n キューがいっぱいです」 ;
戻る ;
}
それ以外 もし ( 頭 == - 1 )
{
頭 = しっぽ = 0 ;
新しい到着 [ しっぽ 】 = 値;
}
それ以外 もし ( しっぽ == Qサイズ - 1 && 頭 ! = 0 )
{
しっぽ = 0 ;
新しい到着 [ しっぽ 】 = 値;
}
それ以外 {
しっぽ ++;
新しい到着 [ しっぽ 】 = 値;
}
}
ここでは、キューが空またはアンダーフローの場合に、「MyQueue」クラスから「enqueue()」関数を呼び出して、循環キューに要素を挿入します。 「enqueue()」関数は「val」パラメータとともに渡され、循環キューの末尾から値を挿入します。このために循環キューに値を挿入するために「if-else」条件を設定します。最初の「if」ステートメント「if ((head == 0 && tail == Qsize – 1) || (tail == (head – 1) % (Qsize – 1)))」は、head がは循環キューの開始位置にあり、末尾は循環キューの終了位置にあります。次に、尻尾が頭の後ろの位置にあるかどうかを確認します。これらの条件のいずれかが満たされる場合、キューは空ではなく、プロンプトによってメッセージが生成されます。
次に、キューが空かどうかを識別する「else-if」条件があります。そうであれば、値がキューに挿入されます。ヘッドは -1 に等しいままであるため、キューが空であり、値を循環キューに挿入する必要があることを示しています。このため、先頭と末尾を 0 に設定します。次に、末尾の位置からの値を「NewArr」循環キューに挿入します。
次に、末尾がキューの最後の位置にあり、先頭がキューの開始位置ではないかどうかをチェックする 3 番目の「else-if」条件があります。この条件は、テールが最後尾に到達し、開始位置にまだスペースがある場合に適用されます。このためには、先頭を 0 に設定する必要があり、要素は末尾の位置から追加されます。最後に、指定された条件がすべて満たされていない場合、キューは空でも満杯でもありません。この場合、末尾を 1 ずつインクリメントし、新しい末尾の位置から値が追加されます。
ステップ 2: 循環バッファから要素を削除する関数を作成する
enqueue() 関数を使用して要素を作成し、循環キューに挿入するように前のコードを設定しました。ここで、循環バッファーがオーバーフローした場合に要素を削除する実装を定義します。
int MyQueue::deQueue ( ){
もし ( 頭 == - 1 )
{
コート << 」 \n キューは無料です」 ;
戻る INT_MIN;
}
int MyData = NewArr [ 頭 】 ;
新しい到着 [ 頭 】 = -1 ;
もし ( 頭 == しっぽ )
{
頭 = -1 ;
しっぽ = -1 ;
}
それ以外 もし ( 頭 == Qサイズ - 1 )
頭 = 0 ;
それ以外
頭 ++;
戻る マイデータ;
}
指定されたコードでは、「Myqueue」クラスから dequeue() 関数を呼び出して、ヘッド インデックスから要素を削除します。したがって、キューが空かどうかをチェックする「if」ステートメントがあります。先頭には、空のキューを表す「-1」値が設定されます。キューが空であることを示すメッセージが生成され、int の定数最小値である INT_MIN が返されます。 「if」ステートメントは、キューが空いているかどうかを判断します。このために、「MyData」変数を定義し、キューの先頭に要素の値を設定します。次に、ヘッドを -1 の位置に設定します。これは、この値がキューから削除されることを示します。この後、頭と尾が等しいかどうかを確認します。両方が等しい場合は、空の循環キューを表す「-1」値を両方に割り当てます。最後に、ヘッドがキューの最後のインデックスにある場合に dequeue() が機能するかどうかを確認します。このため、配列の先頭でループする値「0」を設定します。指定された条件がいずれも当てはまらない場合、head の値がインクリメントされ、デキューされた要素が返されます。
ステップ 3: 循環バッファーの要素を表示する関数を作成する
このセクションでは、showQueue() 関数を呼び出して、「NewArr」循環キューの要素を表示します。
void MyQueue::showQueue ( ){
もし ( 頭 == - 1 )
{
コート << 」 \n キューは無料です」 ;
戻る ;
}
コート << 」 \n 循環キュー要素: ' ;
もし ( しっぽ > = 頭 )
{
のために ( int i = 頭 ;私 < = しっぽ ; i++ )
コート << 新しい到着 [ 私 】 << 「」 ;
}
それ以外
{
のために ( int i = 頭 ;私 < Qサイズ; i++ )
コート << 新しい到着 [ 私 】 << 「」 ;
のために ( int i = 0 ;私 < = しっぽ ; i++ )
コート << 新しい到着 [ 私 】 << 「」 ;
}
}
最初にキューの空のステータスが確認されます。キューが空いている場合は、循環キューが空いていることを示すメッセージが表示されます。それ以外の場合、関数は循環キューの要素を表示します。このために、尾部が頭部以上である「if」ステートメントを定義します。この条件は、循環キューが完了していない場合に対処するために設定されます。
この場合、「for」ループを使用して先頭から末尾まで反復し、循環キューの値を出力します。次のケースは、循環キューが完了した場合です。このために、尾部が頭よりも小さい「if」条件を使用してチェックします。次に、2 つのループを使用する必要があります。最初のループはキューの先頭から最後まで反復し、2 番目のループは末尾の先頭から反復します。
ステップ 4: 循環キュー プログラムの Main() 関数を作成する
最後に、循環キューに 5 つの整数を挿入し、キューの整数を表示するプログラムの main() 関数を作成します。その後、dequeue() 関数を呼び出して、循環キューから削除された整数を表示します。いくつかの要素をキューから取り出した後、enqueue() 関数を使用して新しい要素を挿入してキューを再度埋めます。
整数メイン ( ){
MyQueue その ( 5 ) ;
// 要素の挿入 で 循環キュー
que.enQueue ( 十一 ) ;
que.enQueue ( 12 ) ;
que.enQueue ( 13 ) ;
que.enQueue ( 14 ) ;
que.enQueue ( 15 ) ;
// 表示要素が存在する で 循環キュー
que.showQueue ( ) ;
// 循環キューからの要素の削除
コート << 」 \n 削除された要素 = ' << que.deQueue ( ) ;
コート << 」 \n 削除された要素 = ' << que.deQueue ( ) ;
que.showQueue ( ) ;
que.enQueue ( 16 ) ;
que.enQueue ( 17 ) ;
que.enQueue ( 18 ) ;
que.showQueue ( ) ;
戻る 0 ;
}
出力:
循環キューの実装の結果は、C++ プロンプト画面に表示されます。
結論
結論として、この記事では循環バッファのトピックについて詳しく説明しています。最初に循環バッファを作成し、次に循環キューから削除する方法を説明し、次に循環の要素を C++ で表示しました。