Comment implémenter les opérations d'insertion et de suppression de file d'attente en Java

Comment implémenter des opérations d'insertion et de suppression de file d'attente en Java

La file d'attente est une structure de données couramment utilisée qui suit le principe du premier entré, premier sorti (FIFO). En Java, les files d'attente peuvent être implémentées à l'aide de tableaux ou de listes chaînées. Les deux méthodes de mise en œuvre seront présentées ci-dessous et des exemples de code seront donnés.

1. Utilisez des tableaux pour implémenter des files d'attente :

L'idée des tableaux pour implémenter des files d'attente est d'utiliser un tableau comme structure de données sous-jacente de la file d'attente et d'implémenter les opérations d'insertion et de suppression en conservant les pointeurs de tête et de queue.

Exemple de code :

public class ArrayQueue {
    private int[] queueArray;    // 队列数组
    private int front;  // 队头指针
    private int rear;   // 队尾指针
    private int maxSize;    // 队列的最大容量

    public ArrayQueue(int size) {
        queueArray = new int[size];
        maxSize = size;
        front = 0;
        rear = -1;
    }

    // 入队操作
    public void enqueue(int data) {
        if (isFull()) {
            throw new IllegalStateException("队列已满，无法入队");
        }
        rear++;
        queueArray[rear] = data;
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = queueArray[front];
        front++;
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (rear + 1 == front);
    }

    // 判断队列是否已满
    public boolean isFull() {
        return (rear == maxSize - 1);
    }
}

2. Utiliser une liste chaînée pour implémenter une file d'attente :

L'idée d'une liste chaînée implémentant une file d'attente est d'implémenter des opérations d'insertion et de suppression en maintenant un pointeur vers la tête de la file d'attente et un pointeur vers la queue de la file d’attente. Chaque fois qu'un nouvel élément est inséré, il est ajouté à la fin de la file d'attente, et le pointeur de fin de file d'attente pointe vers le nouvel élément, chaque fois qu'un élément est supprimé, le pointeur de tête de file d'attente pointe vers le suivant ; élément.

Exemple de code :

public class LinkedQueue {
    private Node front;    // 队头指针
    private Node rear;     // 队尾指针

    public LinkedQueue() {
        front = null;
        rear = null;
    }

    // 节点类
    private class Node {
        private int data;   // 数据
        private Node next;  // 指向下一个节点的指针

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 入队操作
    public void enqueue(int data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // 出队操作
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法出队");
        }
        int data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (front == null);
    }
}

Voici deux façons d'implémenter les opérations d'insertion et de suppression de file d'attente en Java. L'utilisation de l'implémentation de tableaux peut améliorer l'efficacité de l'accès aléatoire dans une certaine mesure, tandis que l'utilisation de l'implémentation de listes chaînées est plus flexible et peut ajuster dynamiquement la taille de la file d'attente. Choisissez simplement la méthode de mise en œuvre appropriée en fonction des besoins réels.

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!