Javaでのキューの配列とリンクリストの実装

Queue の概要

Queue は先入れ先出し (FIFO) 線形データ構造です。キューの主な操作は次のとおりです。キューに参加してキューから外すことです。

キューの先頭: キューの出口端、キューの末尾: キューの入口端。通常、キューに入力された最後の要素の次の位置として配列で表されます。

配列を使用して実装する場合は、次の点に注意してください。要素がキューの先頭でデキューされ続けると、キューの利用可能なスペースが小さくなるため、通常は循環キューを使用して実装します。このとき、列の最後尾が列の先頭より前に現れることもあります。

推奨される関連学習ビデオ チュートリアル: java 学習

キュー配列の実装

キュー配列の実装はこちら キュー通常、循環行列になります。

特記事項:

(1) キューが満杯の場合の判定条件は、 (キュー末尾の添字 1) % 配列長 = キュー先頭の添字

(2) キューテールポインタの指す位置には空きが 1 つあるため、キューの最大容量は配列長から 1 引いた値となります。

public class MyQueue {
    private int[] array;
    private int front;
    private int rear;
    public MyQueue(int capacity){
        array = new int[capacity];
    }
 
    /*
    入队时，只需判断队列是否已满，若队列已满，则抛出异常，其他情况（包括队列为空）都正常插入
     */
    public void enQueue(int data) throws Exception{
        if((rear+1) % array.length  == front)
            throw new Exception("队列已满，不能入队！");
        array[rear] = data;
        rear = (rear+1) % array.length;
    }
 
    /*
    出队时，判断队列是否为空，若队列为空，抛出异常
     */
    public int deQueue() throws Exception{
        if(front == rear)
            throw new Exception("队列为空，不能出队！");
        int temp = array[front];
        front = (front+1) % array.length;
        return temp;
    }
 
//    public void output(){
//        for(int i = front; ((i+1) % array.length) <= rear; i++){
//一直在循环输出，严重错误！不能把取模判断语句写在条件里面！
//            i %= array.length;
//            System.out.println(array[i]);
//        }
//    }
 
    public void output(){
        for(int i = front; i != rear; i = (i+1) % array.length){
            System.out.println(array[i]);
        }
    }
    public static void main(String[] args) throws Exception{
        MyQueue myQueue = new MyQueue(5);//长度为5的队列只能插入4个元素
        myQueue.enQueue(1);
        myQueue.enQueue(3);
        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.enQueue(5);
        myQueue.enQueue(6);
        myQueue.output();
    }
 
}

キューのリンク リストの実装

キューがリンク リストを使用して実装されている場合、ヘッド ポインタを使用して次を指します。キューの最初のノードを使用し、末尾ポインタはキューの最後のノードを指します。

public class MyQueue_LinkList {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
 
    private Node front;
    private Node rear;
    private int size;//队列中实际元素的个数
    private int maxsize;
 
    public MyQueue_LinkList(int capacity){
        maxsize = capacity;
    }
 
    public void enQueue(int data) throws Exception{
        if(size >= maxsize)
            throw new Exception("队列已满，无法入队");
        Node insertedNode = new Node(data);
        if(size == 0){
            front = insertedNode;
            rear = insertedNode;
        }
        else{
            rear.next = insertedNode;
            rear = insertedNode;
        }
        size++;
    }
 
    public int deQueue() throws Exception{
        if(front == null)
            throw new Exception("队列为空，无法出队！");
        int temp;
        if(front == rear)//队列中只有一个节点
            rear = null;
        temp = front.data;
        front = front.next;
        size--;
        return temp;
    }
 
    public void output(){
        Node temp = front;
        for(int i = 0 ; i < size; i++){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyQueue_LinkList myQueue_linkList = new MyQueue_LinkList(5);
        myQueue_linkList.enQueue(1);
        myQueue_linkList.enQueue(3);
        myQueue_linkList.enQueue(2);
        myQueue_linkList.deQueue();
        myQueue_linkList.deQueue();
        myQueue_linkList.enQueue(5);
        myQueue_linkList.enQueue(7);
        myQueue_linkList.output();
 
    }
}

キュー アプリケーション シナリオ

(1) 銀行キュー、先着順。

(2) マルチスレッドでは、公平なロックを競合する待機キューが、アクセス順序に従ってキュー内のスレッドの順序を決定します。

(3) Web クローラーは、クロール対象の Web サイトの URL をキューに格納し、キューに格納された順序でクロールおよび解析することにより、Web サイトのクローリングを実装します。

おすすめの関連記事とチュートリアル: Java 入門チュートリアル

以上がJavaでのキューの配列とリンクリストの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。