Array- und verknüpfte Listenimplementierung der Warteschlange in Java

Einführung in die Warteschlange

Warteschlange ist eine lineare First-In-First-Out-Datenstruktur (FIFO), die Hauptoperation der Warteschlange ist, sich der Warteschlange anzuschließen und aus der Warteschlange auszusteigen.

Kopf der Warteschlange: das Ausgangsende der Warteschlange, Ende der Warteschlange: das Eingangsende der Warteschlange, normalerweise im Array dargestellt als nächste Position des letzten in die Warteschlange eingegebenen Elements.

Bitte beachten Sie bei der Implementierung mit einem Array: Wenn am Kopf der Warteschlange weiterhin Elemente aus der Warteschlange entfernt sind, wird der verfügbare Speicherplatz der Warteschlange kleiner, daher verwenden wir normalerweise eine kreisförmige Warteschlange zur Implementierung es, und zu diesem Zeitpunkt wird auch das Ende der Warteschlange möglicherweise vor dem Anführer der Warteschlange erscheinen.

Empfohlene verwandte Lernvideo-Tutorials: Java-Lernen

Array-Implementierung der Warteschlange

Array-Implementierung der Warteschlange ist hier Die Warteschlange ist im Allgemeinen eine kreisförmige Warteschlange!

Besonderer Hinweis:

(1) Die Beurteilungsbedingung, wenn die Warteschlange voll ist, ist (Warteschlangenende-Index + 1) % Array-Länge = Warteschlangenkopf-Index

(2) Die Position, auf die der Warteschlangenendzeiger zeigt, ist eine freie Stelle, daher ist die maximale Kapazität der Warteschlange 1 kleiner als die Array-Länge.

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();
    }
 
}

Verknüpfte Listenimplementierung der Warteschlange

Wenn die Warteschlange mit einer verknüpften Liste implementiert ist, verwenden Sie den Kopfzeiger, um auf die zu zeigen Verwenden Sie den ersten Knoten der Warteschlange. Der Endzeiger zeigt auf den letzten Knoten der Warteschlange.

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();
 
    }
}

Warteschlangen-Anwendungsszenarien

(1) Bankwarteschlange, wer zuerst kommt, mahlt zuerst.

(2) Beim Multithreading bestimmt die Warteschlange, die um faire Sperren konkurriert, die Reihenfolge der Threads in der Warteschlange entsprechend der Zugriffssequenz.

(3) Webcrawler implementieren das Website-Crawling, indem sie die zu crawlenden Website-URLs in der Warteschlange speichern und sie dann in der Reihenfolge crawlen und analysieren, in der sie in der Warteschlange gespeichert sind.

Empfohlene verwandte Artikel und Tutorials: Java-Einführungs-Tutorial

Das obige ist der detaillierte Inhalt vonArray- und verknüpfte Listenimplementierung der Warteschlange in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!