Structures de données linéaires courantes en Java et leur implémentation : exploration de la pile à la file d'attente

De la pile à la file d'attente : explorez les structures de données linéaires courantes en Java et comment elles sont implémentées

Introduction :
En informatique, une structure de données est un moyen d'organiser et de stocker des données. L'un d'eux est la structure de données linéaire, caractérisée par une relation contextuelle claire entre les éléments de données. Dans le développement Java, les structures de données linéaires courantes incluent les piles et les files d'attente, qui sont très fréquemment utilisées. Cet article explorera en profondeur comment les piles et les files d'attente sont implémentées en Java et fournira des exemples de code spécifiques.

1. Le concept et la mise en œuvre de la stack :
Stack est une structure de données Last In First Out (LIFO). Sa particularité est que les opérations d'insertion et de suppression ne peuvent être effectuées qu'en haut de la pile. En Java, il existe deux implémentations courantes de piles : l'implémentation basée sur un tableau et l'implémentation basée sur une liste chaînée.

1. Implémentation de pile basée sur un tableau :
   Array est une structure de données stockée en continu, ce qui est très approprié pour l'implémentation de piles. Voici un exemple de code d'une classe de pile basée sur un tableau :

public class ArrayStack {
    private int[] stack;
    private int top;  // 栈顶指针

    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stack.length - 1;
    }

    public void push(int item) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }
}

2. Implémentation de pile basée sur une liste chaînée :
   La liste chaînée est une structure de données de stockage non continue, qui convient également à l'implémentation de piles. Ce qui suit est un exemple de code d'une classe de pile basée sur une liste chaînée :

public class LinkedStack {
    private Node top;

    public LinkedStack() {
        top = null;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int item = top.data;
        top = top.next;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    private class Node {
        private int data;
        private Node next;

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

2. Le concept et l'implémentation de la file d'attente :
La file d'attente est une structure de données premier entré, premier sorti (FIFO). Sa particularité est qu'il ne peut insérer que des éléments en fin de file et supprimer des éléments en tête de file. En Java, il existe deux implémentations courantes de files d'attente : l'implémentation basée sur un tableau et l'implémentation basée sur une liste chaînée.

1. Implémentation de file d'attente basée sur un tableau :
   Semblable à l'implémentation de pile basée sur un tableau, voici un exemple de code d'une classe de file d'attente basée sur un tableau :

public class ArrayQueue {
    private int[] queue;
    private int front;  // 队头指针
    private int rear;  // 队尾指针

    public ArrayQueue(int capacity) {
        queue = new int[capacity + 1];  // 额外预留一个空位
        front = rear = 0;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public boolean isFull() {
        return (rear + 1) % queue.length == front;
    }

    public void enqueue(int item) {
        if (isFull()) {
            throw new RuntimeException("Queue is full");
        }
        queue[rear] = item;
        rear = (rear + 1) % queue.length;
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = queue[front];
        front = (front + 1) % queue.length;
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return queue[front];
    }
}

2. Implémentation de file d'attente basée sur une liste chaînée :
   Similaire à une liste chaînée- implémentation de pile basée sur une liste chaînée, voici un exemple de code pour une classe de file d'attente basée sur une liste chaînée :

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

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

    public boolean isEmpty() {
        return front == null;
    }

    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        int item = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return item;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return front.data;
    }

    private class Node {
        private int data;
        private Node next;

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

Conclusion :
Les piles et les files d'attente sont des structures de données linéaires couramment utilisées en Java, et il existe de nombreuses façons de les implémenter. Cet article présente les implémentations de pile et de file d'attente basées sur des tableaux et des listes chaînées, et fournit des exemples de code spécifiques. Les développeurs peuvent choisir la méthode de mise en œuvre appropriée en fonction des besoins réels pour améliorer l'efficacité et la maintenabilité du programme.

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!