Java プログラミングスキル - データ構造とアルゴリズム「キュー」

[[386219]]

基本的な紹介

キューは、配列またはリンクリストを使用して実装できる順序付きリストです。

先入先出の原則に従います。つまり、キューに最初に格納されたデータは最初に取り出され、後に格納されたデータは後で取り出されます。

配列シミュレーションキュー

キュー自体は順序付きリストです。キューデータの格納に配列構造を使用する場合、キュー配列の宣言は以下のようになります。ここで、maxSize はキューの最大容量です。

キューの入力と出力はそれぞれフロントエンドとバックエンドから処理されるため、キューのフロントエンドとバックエンドの添え字をそれぞれ記録するために、front と rear という 2 つの変数が必要です。front はデータ出力に応じて変化し、rear はデータ入力に応じて変化します。

コード例

パッケージ com.structures.queue; 
 
 java.util.Scanner をインポートします。 
 
パブリッククラスArrayQueueDemo {
公共 静的void main(String[] args) {
        ArrayQueue 配列Queue = 新しいArrayQueue(3);
文字  key = ' ' ; // ユーザー入力を受け入れる
        スキャナー scanner = new Scanner( System.in );
        ブールループ = true ;
        // メニューを出力する
        while (ループ) {
            System.out.println ( "s(show): キューを表示" );
            System.out.println ( "e(exit): プログラムを終了します" );
            System.out.println ( "a(add): キューにデータを追加します" );
            System.out.println ( "g(get): キューからデータを取得します" );
            System.out.println ( "h(head): キューの先頭にあるデータを表示します" );
キー= scanner.next ( ).charAt(0);
            スイッチ（キー）{
場合  's' :
                    配列キューを表示します。
                    壊す;
場合  'あ' :
                    System.out.println ( "整数を入力してください" ) ;
 int値 = scanner.nextInt();
                    配列キューにキュー値を追加します。
                    壊す;
場合  'グ' :
                    試す {
 intキュー = arrayQueue.getQueue();
                        System.out.printf ( "取得されたデータは%dです" 、queue);
                    }catch (例外 e){
                        System.out.println (e.getMessage()) ;
                    }
                    壊す;
場合  'え' :
                    スキャナーを閉じます() ;
                    ループ = false ;
                    壊す;
場合  'h' :
                    試す {
配列キューのheadQueue();
                        System.out.printf ( "キューの先頭から取り出されたデータは%dです" ,head);
                    }catch (例外 e){
                        System.out.println (e.getMessage()) ;
                    }
デフォルト：
                    壊す;
            }
        }
        System.out.println ( "プログラムが終了します" ) ;
    }
 } 
 
 //配列を使用してキューをシミュレートする - ArrayQueueクラスを記述する
クラスArrayQueue {
    //配列の最大容量を示します
    プライベートint maxSize;
    //キューの先頭
    プライベートintフロント;
    // キューの末尾
    プライベートintリア;
    //データの保存とキューのシミュレートに使用
    プライベートint []arr; 
 
    //キューコンストラクタを作成する
パブリックArrayQueue( int arrMaxSize) {
        最大サイズ = arrMaxSize;
        arr = 新しいint [最大サイズ];
        front = -1; //キューの先頭の前の位置を指す
        rear = -1; // キューの末尾のデータ、つまりキューの最後のデータを指します
    } 
 
    // キューがいっぱいかどうか確認する
パブリックブール値isFull() {
リア == maxSize - 1 を返します。
    } 
 
    // キューが空かどうか確認する
パブリックブール値isEmpty() {
後方 == 前方を返します。
    } 
 
    //キューにデータを追加する
パブリックvoid addQueue( int n) {
        満杯の場合（）{
            System.out.println ( "キューにデータを追加できません" ) ;
戻る;
        }
        rear++; //後部を後方に移動する
        arr[後方] = n;
    } 
 
    //キューデータを取得してキューを終了する
公共 整数getQueue() {
        空の場合（）{
            throw new RuntimeException( "キューが空なので、データを取得できません" );
        }
        フロント++;
 arr[front]を返します。
    } 
 
    //すべてのキューデータを表示
パブリックvoid showQueue() {
        空の場合（）{
            System.out.println ( "キューは空です。データがありません" ) ;
        }
 ( int i = 0; i < this.arr.length; i++) {
            システム.out.printf ( "arr[%d]=%d\n" , i, arr[i]);
        }
    } 
 
    //キューヘッダーデータを表示します。データを取得するのではないことに注意してください
公共  intヘッドキュー() {
        空の場合（）{
            throw new RuntimeException( "キューが空です。データがありません" );
        }
 arr[front + 1]を返します。
    } 
 
 }

問題分析

現在、この配列は一度しか使用できず、再利用の効果は得られません。
この配列を循環キューに改善するアルゴリズム: modulo%

リングキューを改善するためのアイデアの分析

front変数の意味が調整されました。frontはキューの最初の要素を指します。つまり、arr[front]はキューの最初の要素であり、frontの初期値は0です。
リア変数の意味は調整されています。リアはキューの最後の要素の後の位置を指します。これは慣例的にスペースを残したいためです。リアの初期値は0です。
キューがいっぱいの場合、条件は (rear+1)%maxSize = front になります。
キューが空の場合、後部 == 前面が空になります。
このように分析すると、キュー内の有効なデータの数 = (rear + maxSize - front) % maxSize となります。

リングキューのコード例

パッケージ com.structures.queue; 
 
 java.util.Scanner をインポートします。 
 
パブリッククラスCircleArrayQueue {
公共 静的void main(String[] args) {
        CircleArray arrayQueue = new CircleArray(4); //ここで4を設定します。キュー内の有効なデータの最大数は3です。
文字  key = ' ' ; // ユーザー入力を受け入れる
        スキャナー scanner = new Scanner( System.in );
        ブールループ = true ;
        // メニューを出力する
        while (ループ) {
            System.out.println ( "s(show): キューを表示" );
            System.out.println ( "e(exit): プログラムを終了します" );
            System.out.println ( "a(add): キューにデータを追加します" );
            System.out.println ( "g(get): キューからデータを取得します" );
            System.out.println ( "h(head): キューの先頭にあるデータを表示します" );
キー= scanner.next ( ).charAt(0);
            スイッチ（キー）{
場合  's' :
                    配列キューを表示します。
                    壊す;
場合  'あ' :
                    System.out.println ( "整数を入力してください" ) ;
 int値 = scanner.nextInt();
                    配列キューにキュー値を追加します。
                    壊す;
場合  'グ' :
                    試す {
 intキュー = arrayQueue.getQueue();
                        System.out.printf ( "取得されたデータは%dです" 、queue);
                    }catch (例外 e){
                        System.out.println (e.getMessage()) ;
                    }
                    壊す;
場合  'え' :
                    スキャナーを閉じます() ;
                    ループ = false ;
                    壊す;
場合  'h' :
                    試す {
配列キューのheadQueue();
                        System.out.printf ( "キューの先頭から取り出されたデータは%dです" ,head);
                    }catch (例外 e){
                        System.out.println (e.getMessage()) ;
                    }
デフォルト：
                    壊す;
            }
        }
        System.out.println ( "プログラムが終了します" ) ;
    } 
 
 } 
 
クラス CircleArray {
    //配列の最大容量を示します
    プライベートint maxSize;
    //front変数の意味が調整されます。frontはキューの最初の要素を指します。つまり、arr[front]はキューの最初の要素であり、frontの初期値は0です。
    プライベートintフロント;
    //rear変数の意味は調整されます。rearはキューの最後の要素の後の位置を指します。これは慣例的にスペースを残したいためです。rearの初期値 = 0
    プライベートintリア;
    //データの保存とキューのシミュレートに使用
    プライベートint []arr; 
 
パブリックCircleArray( int arrMaxSize) {
        最大サイズ = arrMaxSize;
        arr = 新しいint [最大サイズ];
    } 
 
    // キューがいっぱいかどうか確認する
パブリックブール値isFull() {
戻り値(rear + 1) % maxSize == front;
    } 
 
    // キューが空かどうか確認する
パブリックブール値isEmpty() {
後方 == 前方を返します。
    } 
 
    //キューにデータを追加する
パブリックvoid addQueue( int n) {
        満杯の場合（）{
            System.out.println ( "キューがいっぱいなので、キューにデータを追加できません" );
戻る;
        }
        //データを直接追加する
        arr[後方] = n;
        //後部を後ろに移動、ここでは係数を考慮する必要があります
        リア = (リア + 1) % maxSize;
    } 
 
    //キューデータを取得してキューを終了する
公共 整数getQueue() {
        空の場合（）{
            throw new RuntimeException( "キューが空なので、データを取得できません" );
        }
        //ここで、frontがキューの最初の要素を指していることを分析する必要があります。
        //1. まず、frontに対応する値を一時変数に保存します。
        //2. フロントを後ろに移動して係数を取ることを検討します
        //3. 一時的に保存した変数を返す
int値 = arr[front];
        前面 = (前面 + 1) % 最大サイズ;
戻り値;
    } 
 
    //すべてのキューデータを表示
パブリックvoid showQueue() {
        空の場合（）{
            System.out.println ( "キューは空です。データがありません" ) ;
        }
        // 先頭から走査を開始する
( int i = front; i < front + size (); i++) {
            システム.out.printf ( "arr[%d]=%d\n" 、i%maxSize、arr[i%maxSize]);
        }
    } 
 
    // 現在のキュー内の有効なデータの数を計算する
公共 整数 サイズ（） {
 (rear + maxSize - front) % maxSize を返します。
    } 
 
    //キューヘッダーデータを表示します。データを取得するのではないことに注意してください
公共  intヘッドキュー() {
        空の場合（）{
            throw new RuntimeException( "キューが空です。データがありません" );
        }
 arr[front]を返します。
    }
 }