MINT lernen

Das Prinzip Schlange

Zwei Abituraufgaben zur Schlange — Wartenummern und Druckaufträge.

Dein Fortschritt:
0 / 0 Aufgaben
1

Wartenummern im Bürgeramt

AFB I–II

Im Bürgeramt zieht jede Person eine Wartenummer. Das System speichert die Nummern in einer Queue<Integer> nummern, die zu Beginn leer ist.

  1. Beschreiben Sie das Prinzip, nach dem die Schlange arbeitet, am Beispiel des Bürgeramts.
  2. Ermitteln Sie für die Folge enqueue(101), enqueue(102), dequeue(), enqueue(103), head(), dequeue(), enqueue(104) den Inhalt der Schlange nach jedem Schritt sowie alle Rückgabewerte.

Hinweise

Hinweis zu Aufgabe a)
Wo stellen sich neue Personen an, wer wird aufgerufen?
Hinweis zu Aufgabe b)
head() liefert einen Wert, verändert die Schlange aber nicht.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Neue Wartenummern werden hinten angestellt (enqueue). Aufgerufen wird stets die vorderste, also die am längsten wartende Nummer (dequeue). Die Reihenfolge des Eintreffens bleibt erhalten: First In – First Out.

Erwartungshorizont zu Aufgabe b)

[101] → [101, 102] → [102], liefert 101 → [102, 103] → [102, 103], liefert 102 → [103], liefert 102 → [103, 104] (vorn jeweils links).

2

Druckaufträge im Schulnetz

AFB II–III

Der Schuldrucker verwaltet seine Aufträge in einer Queue<Integer> auftraege; jeder Eintrag ist die Seitenzahl eines Auftrags.

  1. Implementieren Sie die Methode int gesamtSeiten(), die die Summe aller Seiten liefert. Die Schlange muss danach unverändert sein.
  2. Vergleichen Sie Ihre Lösung mit derselben Methode für einen Stapel.
  3. Beurteilen Sie den Vorschlag, Aufträge mit wenigen Seiten grundsätzlich vorzuziehen.

Hinweise

Hinweis zu Aufgabe a)
Eine Schlange hat keine Operation für die Länge. Laden Sie in eine Hilfsschlange um.
Hinweis zu Aufgabe b)
Was passiert jeweils mit der Reihenfolge beim Umladen?
Hinweis zu Aufgabe c)
Kriterien: mittlere Wartezeit, Fairness, Eignung der Schlange.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)
public int gesamtSeiten() {
    Queue<Integer> hilf = new Queue<Integer>();
    int summe = 0;
    while (!auftraege.isEmpty()) {
        int s = auftraege.dequeue();
        summe = summe + s;
        hilf.enqueue(s);
    }
    while (!hilf.isEmpty()) {
        auftraege.enqueue(hilf.dequeue());
    }
    return summe;
}
Erwartungshorizont zu Aufgabe b)

Gemeinsam: Umladen in eine Hilfsstruktur, dabei addieren, danach zurückladen. Unterschied: Bei der Schlange bleibt die Reihenfolge beim Umladen erhalten; beim Stapel wird sie umgedreht und durch das Zurückladen ein zweites Mal gedreht — deshalb stimmt sie am Ende in beiden Fällen.

Erwartungshorizont zu Aufgabe c)

Vorteil: Kurze Aufträge sind schneller fertig, die mittlere Wartezeit sinkt. Nachteil: Große Aufträge können beliebig lange warten, wenn ständig kleine nachkommen; das ist unfair. Außerdem lässt sich Vorziehen mit einer Schlange nicht umsetzen, weil nur hinten angestellt werden kann — man bräuchte eine dynamische Reihung (Einfügen an passender Stelle). Ein begründetes Urteil in beide Richtungen ist möglich.