Gängige lineare Datenstrukturen in Java und ihre Implementierung: Erkundung vom Stapel bis zur Warteschlange

Vom Stapel zur Warteschlange: Entdecken Sie gängige lineare Datenstrukturen in Java und wie sie implementiert werden.

Einführung:
In der Informatik ist eine Datenstruktur eine Möglichkeit, Daten zu organisieren und zu speichern. Eine davon ist die lineare Datenstruktur, die durch eine klare Kontextbeziehung zwischen Datenelementen gekennzeichnet ist. In der Java-Entwicklung gehören zu den gängigen linearen Datenstrukturen Stapel und Warteschlangen, die sehr häufig verwendet werden. In diesem Artikel wird ausführlich untersucht, wie Stapel und Warteschlangen in Java implementiert werden, und es werden spezifische Codebeispiele bereitgestellt.

1. Das Konzept und die Implementierung von Stack:
Stack ist eine Last In First Out (LIFO)-Datenstruktur. Sein Merkmal besteht darin, dass Einfüge- und Löschvorgänge nur oben im Stapel ausgeführt werden können. In Java gibt es zwei gängige Implementierungen von Stacks: die Array-basierte Implementierung und die auf verknüpften Listen basierende Implementierung.

1. Array-basierte Stack-Implementierung:
   Array ist eine kontinuierlich gespeicherte Datenstruktur, die sich sehr gut für die Implementierung von Stacks eignet. Das Folgende ist ein Beispielcode einer Array-basierten Stack-Klasse:

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. Stack-Implementierung basierend auf einer verknüpften Liste:
   Eine verknüpfte Liste ist eine nicht kontinuierliche Speicherdatenstruktur, die sich auch für die Implementierung von Stacks eignet. Das Folgende ist ein Beispielcode einer Stack-Klasse, die auf einer verknüpften Liste basiert:

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. Das Konzept und die Implementierung der Warteschlange:
Queue ist eine FIFO-Datenstruktur (First In First Out). Seine Besonderheit besteht darin, dass nur Elemente am Ende der Warteschlange eingefügt und Elemente am Anfang der Warteschlange gelöscht werden können. In Java gibt es zwei gängige Implementierungen von Warteschlangen: eine Array-basierte Implementierung und eine auf verknüpften Listen basierende Implementierung. 🔜 basierte Stapelimplementierung. Das Folgende ist ein Beispielcode für eine auf verknüpften Listen basierende Warteschlangenklasse:

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];
    }
}

1. Fazit:
   Stapel und Warteschlangen sind häufig verwendete lineare Datenstrukturen in Java, und es gibt viele Möglichkeiten, sie zu implementieren. In diesem Artikel werden Array-basierte und auf verknüpften Listen basierende Stapel- und Warteschlangenimplementierungen vorgestellt und spezifische Codebeispiele bereitgestellt. Entwickler können entsprechend den tatsächlichen Anforderungen die geeignete Implementierungsmethode auswählen, um die Effizienz und Wartbarkeit des Programms zu verbessern.

Das obige ist der detaillierte Inhalt vonGängige lineare Datenstrukturen in Java und ihre Implementierung: Erkundung vom Stapel bis zur Warteschlange. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!