Implémentation de tableaux et de listes chaînées de file d'attente en Java

Introduction à la file d'attente

La file d'attente est une structure de données linéaire premier entré, premier sorti (FIFO). L'opération principale de la file d'attente. est de rejoindre la file d'attente et de sortir de la file d'attente.

Tête de file d'attente : la fin de sortie de la file d'attente, queue de file d'attente : la fin d'entrée de la file d'attente, généralement représentée dans le tableau comme la position suivante du dernier élément entré dans la file d'attente.

Lors de son implémentation avec un tableau, veuillez noter : si la tête de la file d'attente continue à avoir des éléments retirés de la file d'attente, l'espace disponible de la file d'attente deviendra plus petit, nous utilisons donc généralement une file d'attente circulaire pour implémenter il, et à ce moment-là, la queue de la file d'attente pourra également apparaître devant le leader de la file.

Tutoriels vidéo d'apprentissage connexes recommandés : apprentissage Java

Implémentation de tableau de la file d'attente

L'implémentation de tableau de la file d'attente est ici Les files d'attente sont généralement des files d'attente circulaires !

Remarque spéciale :

(1) La condition de jugement lorsque la file d'attente est pleine est (indice de queue de file d'attente + 1) % de longueur du tableau = indice de tête de file d'attente

(2) La position pointée par le pointeur de queue de file d'attente est un poste vacant, donc la capacité maximale de la file d'attente est inférieure de 1 à la longueur du tableau.

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

Implémentation de liste chaînée de la file d'attente

Lorsque la file d'attente est implémentée avec une liste chaînée, utilisez le pointeur de tête pour pointer vers le premier nœud de la file d'attente, utilisez Le pointeur de queue pointe vers le dernier nœud de la file d'attente.

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

Scénarios d'application de file d'attente

(1) File d'attente bancaire, premier arrivé, premier servi.

(2) En multi-threading, la file d'attente en compétition pour les verrous équitables détermine l'ordre des threads dans la file d'attente en fonction de la séquence d'accès.

(3) Les robots d'exploration Web mettent en œuvre l'exploration de sites Web en stockant les URL de sites Web à explorer dans la file d'attente, puis en les explorant et en les analysant dans l'ordre où elles sont stockées dans la file d'attente.

Articles et tutoriels connexes recommandés : Tutoriel d'introduction à Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!