Algorithmen mit Schlangen

Auch eine Schlange hat keinen Index. Man kommt nur vorn an die Elemente — und kann sie hinten wieder anstellen.

• Rotieren:x = q.dequeue() und danach q.enqueue(x) — das vorderste Element wandert nach hinten.
• Ganze Runde:nach n Rotationen steht jedes Element wieder an seinem alten Platz.
• Anzahl:Man kennt n nicht von vornherein — umladen in eine Hilfsschlange und dabei zählen.
• Filtern:n-mal entnehmen und nur die Elemente wieder anstellen, die bleiben sollen; die Reihenfolge bleibt erhalten.

public void entferneNegative(Queue<Integer> q) {
    int n = anzahl(q);               // Hilfsmethode wie beim Stapel
    for (int i = 0; i < n; i++) {
        int x = q.dequeue();
        if (x >= 0) {
            q.enqueue(x);            // behalten: hinten wieder anstellen
        }
    }
}

Ein Prozessor kann immer nur ein Programm gleichzeitig ausführen. Damit trotzdem alle vorankommen, wechselt das Betriebssystem reihum — das Rundlauf-Verfahren (Round Robin).

• Warteschlange:alle rechenbereiten Programme stehen in einer Schlange.
• Zeitscheibe q:das vorderste Programm darf höchstens q Takte rechnen.
• Nicht fertig:es wird mit seiner Restzeit hinten wieder angestellt.
• Fertig:es verlässt die Schlange; seine Fertigstellungszeit wird notiert.

Verändere die Zeitscheibe q und die Rechenzeit von Programm A. Mit ▶ läuft die Zeit Takt für Takt — oben siehst du die Schlange, darunter den Zeitstrahl.

Halte fest: Eine kleine Zeitscheibe verteilt die Rechenzeit gerecht, erzeugt aber viele Wechsel. Eine sehr große Zeitscheibe macht aus dem Rundlauf eine einfache Warteschlange ohne Wechsel.