Javaデータ構造とアルゴリズム[オリジナル]——キュー

声明:コードワードは容易ではありません.転載は出典を明記してください.文章の下で討論して交流することを歓迎します.
前言:Javaデータ構造とアルゴリズムのテーマは不定期に更新され、読者の監督を歓迎します.本稿では,データ構造におけるキュー(queue)の概念,ストレージ構造,キューの特徴を紹介し,javaがループキューを実現するコード実装を読者の参考として学習する.
1.キューの概念
キューはその名の通り、 (head)と (tail)、キュー長の列のようです.キューはスタックと同様で、特殊なルール制約に従うデータ構造でもあります.前回の記事javaデータ構造とアルゴリズム--スタックで紹介されているスタックは (LIFO)のデータ構造で、キューは正反対で、先進的な先出し(FIFO、First In First Out)であり、例えばケンタッキーに行って列に並び、先に列に並んだ人は必ず先に食事を取って列を出た.これは私たちの列に対する認識と一致している.
キューは特殊なルールに従うデータ構造であり、先進的な先発を除いて、キューの挿入はキューの一端からしか操作できない.私たちはこの端をキューの尾と呼ぶ.対応して、削除は反対側からしか出られません.私たちはチームトップと呼ばれています.
要素のないキューを空のキュー、キューに要素を挿入するプロセスをエンキュー、キューから要素を除去するプロセスをアウトキューと呼びます.
一般的に、キューの実装には2つの方式がある:配列実装とチェーンテーブル実装、本編では配列実装を採用し、チェーンテーブル実装は後続の補充である.配列で実装されるキューには、シーケンスキューとループキューの2つがあります.この2つのキューのストレージ構造と特徴は、後述します.
説明:キューを配列で実装します.キューにキューがいっぱいになった場合(キューを宣言するときに初期容量が指定されるのが一般的なため)、新しい要素がキューに入った場合、位置がない場合はどうしますか?捨てるか、待つか.
2.キューのストレージ構造
以下は配列実装を採用し、1つのキュー長が6であることを初期化し、キューには2つのタグがあり、1つのキューヘッダの位置head、1つのキューテールの位置tailは、図に示すように、初期は配列の下に0と表記された位置を指す.
要素を挿入する場合、tailタグ+1、例えば3つの要素がエンキューされ、順にA,B,C(順序に注意)である場合、現在のキュー格納状況は図:現在headは0、tailは3であり、次にデキュー操作を行い、ここでA要素がデキューされるとhead+1、このときキュー格納状況は図:
上記の例によれば、tail-headによってキュー内の要素の個数を得ることができる.tail=headの場合、キューは空ですが、tailが配列長に等しい場合、要素に出入りできません.キューは満タンですか?必ずしも!headとtailは、エンキューおよびデキュー操作で増加するだけで減少しないため、headとtailは最終的にキュー外のストレージ位置を指します.この場合、配列は空ですが、要素をエンキューすることはできません.
オーバーフロー:キューに要素を挿入できない場合、オーバーフローと呼ばれます.偽オーバーフロー:シーケンスキューでは、配列にはまだ空間がある(必ずしも空ではない)が、エンキューできないことを偽オーバーフローと呼ぶ.真上溢:headが0の場合、tailは配列の外を指し、すなわち配列が本当にいっぱいで、真上溢と呼ばれます.≪オーバーフロー|Overflow|emdw≫:空のキューでデキュー操作が実行された場合、キューに要素がなく、オーバーフローと呼ばれます.
「偽上溢」の問題をどう解決するのか.このとき、 が導入される.ダミーオーバーフローが発生した場合、配列にはまだ空きがあるので、図に示すように、tailを新しい配列を指す0インデックスから行えます.
エンキューEおよびFが継続される場合、キューの記憶構造は、図のように、通常、headおよびtailに1を加える場合、配列長の余剰操作を容易にするために使用される.また,シーケンスキューには「ダミーオーバーフロー」の現象があるため,ループキューで実現するのが一般的である.
ループキューを用いて実装する過程で、キューが満キューの場合、tailはheadに等しいが、キューが空の場合、tailもheadに等しい.2つの状態を区別するために、ループキューの長さは配列長-1、すなわち要素を置かない位置があり、head=tailの場合、空キューであり、head=(tail+1)%配列長の場合、対満を示す.
3.キューのjavaコード実装
次に、ループキューのjavaコードを配列で実装します.

public class ArrayQueue {
    private final Object[] queue;  //      
    private int head;
    private int tail;
    
    /**
     *      
     * @param capacity     
     */
    public ArrayQueue(int capacity){
        this.queue = new Object[capacity];
    }
    
    /**
     *   
     * @param o     
     * @return       
     */
    public boolean put(Object o){
        if(head == (tail+1)%queue.length){
            //    
            return false;
        }
        queue[tail] = o;
        tail = (tail+1)%queue.length;  //tail      
        return true;
    }
    
    /**
     *       ，    
     * @return
     */
    public Object peak() {
        if(head==tail){
            //  
            return null;
        }
        return queue[head];        
    }
    
    /**
     *   
     * @return     
     */
    public Object pull(){
        if(head==tail){
            return null;
        }
        Object item = queue[head];
        queue[head] = null;
        return item;
    }
    
    /**
     *       
     * @return
     */
    public boolean isEmpty(){
        return head == tail;
    }
    
    /**
     *       
     * @return
     */
    public boolean isFull(){
        return head == (tail+1)%queue.length;
    }
    
    /**
     *           
     * @return
     */
    public int getsize(){
        if(tail>=head){
            return tail-head;
        }else{
            return (tail+queue.length)-head;
        }
    }    
}

次はキューのテストコードです

public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue q = new ArrayQueue(4);  //        3，             
        System.out.println(q.put("  "));  //  ，true
        System.out.println(q.put("  "));  //  ，true 
        System.out.println(q.put("  "));  //  ，true
        System.out.println(q.put("  "));  //  ，false
        
        System.out.println(q.isFull());  //   true
        System.out.println(q.getsize()); //3，    3   
        
        System.out.println(q.peak());  //  “  ”     
        System.out.println(q.pull());  //  “  ”  
        System.out.println(q.pull());  //  “  ”  
        System.out.println(q.pull());  //  “  ”  
        
        System.out.println(q.isEmpty());  //true   
    }
}

4.キューの適用シーン
キュー の特徴は、キューが「バッファ」として、コンピュータと周辺機器の速度が一致しない問題を解決することができ、FIFOの特徴はデータ伝送の順序を保証する.それ以外にキューは後ろの木の層順遍歴にも応用されており,FIFOの特徴は処理順序が間違っていないことを保証している.