jario_
Wróć do przeglądu

Algorytmy i struktury danych · Rozdział 5

Listen, Stack und Queue

Bisher hast du Daten in Arrays oder in fertigen Collections abgelegt. In diesem Kapitel baust du die wichtigsten Datenstrukturen selbst: den Stack, die Queue und die verkettete Liste. Sie unterscheiden sich vor allem darin, wo Elemente hinzukommen und wieder herausgehen, und davon hängt ab, wie schnell jede Operation ist.

LIFO und FIFO

Ein Stack (Stapel) arbeitet nach LIFO, Last In, First Out: Was du zuletzt drauflegst, nimmst du zuerst wieder herunter. Die Operationen heißen push (drauflegen), pop (herunternehmen) und peek (nur anschauen). Stacks stecken überall, wo etwas rückgängig gemacht oder verschachtelt wird: der Zurück-Knopf im Browser, Strg+Z, Klammern prüfen, Methodenaufrufe.

Eine Queue (Warteschlange) arbeitet nach FIFO, First In, First Out: Wer zuerst kommt, ist zuerst dran. Die Operationen heißen enqueue (hinten anstellen) und dequeue (vorne entnehmen). Beispiele sind Druckaufträge oder Anfragen an einen Server.

ArrayDeque aus java.util kann beides. Im Beispiel kommen dieselben drei Buchstaben einmal umgekehrt und einmal in Einfügereihenfolge heraus.

import java.util.ArrayDeque;import java.util.Deque;
public class Main {    public static void main(String[] args) {        Deque<String> stack = new ArrayDeque<>();        stack.push("A");        stack.push("B");        stack.push("C");        System.out.print("Stack: ");        while (!stack.isEmpty()) {            System.out.print(stack.pop() + " ");        }        System.out.println();
        Deque<String> queue = new ArrayDeque<>();        queue.offer("A");        queue.offer("B");        queue.offer("C");        System.out.print("Queue: ");        while (!queue.isEmpty()) {            System.out.print(queue.poll() + " ");        }        System.out.println();    }}

Ein Stack mit Array

Für einen eigenen Stack genügen ein Array und ein Zähler size. size ist gleichzeitig der Index des nächsten freien Platzes, das oberste Element liegt bei data[size - 1].

  • push: nach data[size] schreiben, dann size++.
  • pop: size--, dann data[size] zurückgeben. Gelöscht wird nichts, der Platz gilt einfach als frei.

Beide Operationen brauchen keine Schleife, egal wie viele Elemente auf dem Stack liegen. Ihre Laufzeit ist O(1), also konstant. Was bei leerem oder vollem Stack passiert, musst du festlegen: hier eine IllegalStateException.

public class Main {    static int[] data = new int[10];    static int size = 0;
    static void push(int value) {        if (size == data.length) {            throw new IllegalStateException("Stack is full");        }        data[size] = value;        size++;    }
    static int pop() {        if (size == 0) {            throw new IllegalStateException("Stack is empty");        }        size--;        return data[size];    }
    public static void main(String[] args) {        push(1);        push(2);        push(3);        System.out.println(pop());        System.out.println(pop());        push(9);        System.out.println(pop());        System.out.println("Size: " + size);    }}

Eine Queue als Ring

Bei einer Queue mit Array kommen Elemente hinten dazu und gehen vorne weg. Würdest du nach jedem dequeue alle Elemente einen Platz nach vorne schieben, wäre das O(n). Stattdessen wandert der Anfang: head zeigt auf das vorderste Element, count zählt die Elemente.

Kommt ein Index am Ende des Arrays an, geht es bei 0 weiter. Das erledigt der Modulo-Operator:

int tail = (head + count) % data.length;   // next free slothead = (head + 1) % data.length;           // after dequeue

So wird das Array zum Ringpuffer, und enqueue wie dequeue bleiben O(1). Im Beispiel landen 40 und 50 wieder auf Index 0 und 1, weil dort schon Platz frei geworden ist.

public class Main {    static int[] data = new int[3];    static int head = 0;    static int count = 0;
    static void enqueue(int value) {        if (count == data.length) {            throw new IllegalStateException("Queue is full");        }        int tail = (head + count) % data.length;        data[tail] = value;        count++;        System.out.println("enqueue " + value + " at index " + tail);    }
    static int dequeue() {        if (count == 0) {            throw new IllegalStateException("Queue is empty");        }        int value = data[head];        head = (head + 1) % data.length;        count--;        return value;    }
    public static void main(String[] args) {        enqueue(10);        enqueue(20);        enqueue(30);        System.out.println("dequeue " + dequeue());        System.out.println("dequeue " + dequeue());        enqueue(40);        enqueue(50);        while (count > 0) {            System.out.println("dequeue " + dequeue());        }    }}

Verkettete Listen

Eine einfach verkettete Liste besteht aus Knoten. Jeder Knoten kennt seinen Wert und den nächsten Knoten (next), der letzte zeigt auf null. Die Liste selbst merkt sich nur head, den ersten Knoten.

Durchlaufen wird sie immer gleich:

Node current = head;while (current != null) {    // use current.value    current = current.next;}

Array und verkettete Liste im Vergleich:

  • Element an Index i lesen: Array O(1), Liste O(n), weil du Knoten für Knoten laufen musst.
  • Vorne einfügen: Array O(n), weil alles verschoben wird, Liste O(1) mit neuem head.
  • Hinten einfügen: Array O(1), solange Platz ist, Liste O(n), mit einem tail-Verweis O(1).
  • Größe: Ein Array ist fest, eine Liste wächst beliebig.

Ein Stack lässt sich mit beidem bauen. Für eine Queue mit Knoten merkt man sich zusätzlich tail, damit enqueue nicht bis zum Ende laufen muss.

public class Main {    static class Node {        int value;        Node next;
        Node(int value) {            this.value = value;        }    }
    public static void main(String[] args) {        Node head = new Node(3);        head.next = new Node(5);        head.next.next = new Node(8);
        Node node = new Node(1);        node.next = head;        head = node;
        int sum = 0;        Node current = head;        while (current != null) {            System.out.print(current.value + " -> ");            sum += current.value;            current = current.next;        }        System.out.println("null");        System.out.println("Sum: " + sum);    }}

Typowe błędy

  • Über null hinausgelaufen

    Der letzte Knoten hat next == null. Wer in der Schleife current.next.value liest oder bei einer leeren Liste head.next anfasst, bekommt eine NullPointerException. Prüfe vorher, ob head == null ist, und wähle die Bedingung passend: current != null zum Durchlaufen aller Knoten, current.next != null, um beim letzten anzuhalten.

  • Verweis verloren

    Ein Knoten, auf den nichts mehr zeigt, ist für immer weg. Beim Umhängen ist deshalb die Reihenfolge wichtig:

    current.next = previous;      // the rest of the list is lostNode next = current.next;     // too late

    Merke dir current.next bevor du es überschreibst. Und wenn eine Queue mit Knoten leer wird, setze auch tail auf null, sonst hängt das nächste enqueue an einen alten Knoten.

  • Off-by-one beim Umlauf

    Im Ringpuffer ist der letzte gültige Index data.length - 1. Ein selbst gebauter Umlauf mit if geht leicht daneben:

    if (tail == data.length - 1) {    tail = 0;}tail++;   // after the wrap-around, tail becomes 1

    Index 0 wird übersprungen, und die Queue überschreibt belegte Plätze. Sicher ist die Modulo-Form tail = (tail + 1) % data.length.