Zum Inhalt
wannacode

Stapel und Warteschlange

Kurz gesagt: Ein Stapel gibt das zuletzt hinzugefügte Element zurück (LIFO), eine Warteschlange das zuerst hinzugefügte (FIFO); ein Stapel auf einem wachsenden Array und eine Warteschlange als Ringpuffer machen jede Operation O(1), das Hinzufügen im Durchschnitt O(1).

Problem

Die Bestell-E-Mail kommt leer an

Der Shop schickt zu jeder Bestellung eine E-Mail aus einer Vorlage: Bestellung {order}: [{items}] (gesamt {total} €). Die Vorlagen werden von Hand geschrieben, und manchmal ist eine Klammer nicht geschlossen oder mit der falschen geschlossen. Dann füllt das E-Mail-Programm nichts ein, und der Kunde bekommt eine leere E-Mail.

Vor dem Versenden willst du sagen: „Die Vorlage ist in Ordnung“ oder „Fehler an Position 28“. Die Klammern zu zählen reicht nicht: In [{items}) sind zwei geöffnet und zwei geschlossen, und der Fehler steckt genau dort.

In der Lektion „Stack, Queue und verkettete Liste“ waren der Stapel und die Warteschlange fertig: das Array. Hier baust du sie selbst, um zu sehen, was jede Operation kostet und wo die Falle liegt.

Die Idee

Ein Stapel auf einem wachsenden Array

Klammern schließen sich in umgekehrter Reihenfolge: Die zuletzt geöffnete wird als Erste geschlossen. Das ist ein Stapel (Stack): Du legst oben drauf und nimmst von oben.

Innen ist ein Stapel ein Array und ein Zähler size:

  • push schreibt an den Index size und erhöht den Zähler;
  • pop verringert den Zähler und gibt zurück, was dort steht;
  • ist das Array voll, wird es doppelt so groß, wie bei der amortisierten Komplexität.
class CharStack {
  constructor() {
    this.items = new Array(4);
    this.size = 0;
  }


  push(c) {
    if (this.size === this.items.length) {
      const bigger = new Array(this.size * 2);
      for (let i = 0; i < this.size; i++) bigger[i] = this.items[i];
      this.items = bigger;
    }
    this.items[this.size] = c;
    this.size++;
  }


  pop() {
    if (this.size === 0) throw new Error("leerer Stapel");
    this.size--;
    return this.items[this.size];
  }


  isEmpty() {
    return this.size === 0;
  }
}

push und pop arbeiten nur mit dem Ende des Arrays. Nichts wird verschoben, also sind beide O(1) (push ist wegen des Wachsens im Durchschnitt O(1)).

In JavaScript wächst das Array schon von selbst, und push und pop() sind genau push und pop des Stapels. Hier wird das Array von Hand verdoppelt, damit du siehst, was die Engine für dich erledigt.

Sieh es dir an

Die Vorlage prüfen

Du gehst die Vorlage Zeichen für Zeichen durch:

  • eine öffnende Klammer kommt auf den Stapel;
  • eine schließende nimmt das oberste Element vom Stapel und prüft, ob es von derselben Art ist;
  • ist der Stapel bei einer schließenden Klammer leer oder am Ende nicht leer, ist die Vorlage falsch.
function firstError(text) {
  const opened = new CharStack();
  for (let i = 0; i < text.length; i++) {
    const c = text[i];
    if ("([{".includes(c)) {
      opened.push(c);
    } else if (")]}".includes(c)) {
      if (opened.isEmpty()) return i;
      if ("([{".indexOf(opened.pop()) !== ")]}".indexOf(c)) return i;
    }
  }
  return opened.isEmpty() ? -1 : text.length;
}
const templates = [
  "Bestellung {order}: [{items}] (gesamt {total} €)",
  "Bestellung {order}: [{items}) (gesamt {total} €)",
  "Bestellung {order}: [{items}] (gesamt {total} €",
];
for (const t of templates) {
  const at = firstError(t);
  console.log(at < 0 ? "OK" : `Fehler an Position ${at}`);
}
Ausgabe
OK
Fehler an Position 28
Fehler an Position 47

In der zweiten Vorlage kommt ), während [ oben auf dem Stapel liegt: Fehler an Position 28. In der dritten wird ( nie geschlossen, und der Fehler liegt am Ende, an Position 47, der Länge des Textes.

Genauer, für Neugierige

Ein echter JSON-Prüfer überspringt auch Klammern in Text zwischen Anführungszeichen: "[1" öffnet nichts. Dann merkt sich der Stapel zusätzlich „ich bin gerade im Text“. Dasselbe gilt für HTML-Tags: Der Stapel hält die Namen der offenen Tags, und </div> muss oben auf div treffen.

Probier es aus

Sag die Ausgabe voraus

console.log(firstError("({total)}"));
Antwort

Problem

Die Lieferwarteschlange am Morgen

Um 8 Uhr morgens warten 10.000 Lieferanfragen im System. Die Kuriere nehmen sie nacheinander, die älteste zuerst: Das ist eine Warteschlange. Jemand hat sie mit einer gewöhnlichen Liste geschrieben:

const jobs = [];
for (let id = 1; id <= 10_000; id++) {
  jobs.push(`#${id}`);
}
let done = 0;
while (jobs.length > 0) {
  const job = jobs.shift();
  done++;
}
console.log(`bearbeitet: ${done}`);
Ausgabe
bearbeitet: 10000

Es sieht harmlos aus, aber jobs.shift() entfernt bei Index 0 eines Arrays. Alle nach dem Ersten rücken einen Platz nach vorn. Bei 10.000 Wartenden verschiebt die erste Entnahme 9999, die zweite 9998 … Zusammen sind das etwa 50 Millionen Verschiebungen, nur um jede Anfrage einmal zu entnehmen.

Die Idee

Ein Ringpuffer: head wandert, nicht die Bestellungen

Verschiebe nicht die Bestellungen. Verschiebe den Zeiger auf die erste.

  • head ist der Index der ersten Bestellung, und size ist, wie viele warten.
  • Eine Entnahme liest items[head], leert den Platz und schiebt head einen weiter. Sonst bewegt sich nichts.
  • Die neue Bestellung kommt auf tail = (head + size) % Plätze. Der Rest der Division macht aus dem Array einen Kreis: Hinter dem letzten Platz kommt der erste. Die freien Plätze vorn, die durch die Entnahmen frei wurden, werden wieder benutzt.
  • Sind alle Plätze belegt, legt grow ein doppelt so großes Array an und kopiert die Bestellungen in der Reihenfolge der Schlange, ab head. Danach ist head 0.

Ein solches Array, dessen Ende am Anfang weitergeht, heißt Ringpuffer (oder Zirkularpuffer).

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }


  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }


  dequeue() {
    if (this.size === 0) {
      throw new Error("leere Warteschlange");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }


  isEmpty() {
    return this.size === 0;
  }


  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}

Damit du sehen kannst, was drin steckt, hat die Klasse auch eine Methode zum Ausgeben:

toString() {
  const shown = this.items.map((s) => s ?? "-").join(", ");
  return `[${shown}] head=${this.head}`;
}

Sieh es dir an

head, tail und der Rücksprung an den Anfang

Drei Bestellungen kommen herein, zwei gehen, dann kommen drei weitere. Die letzte davon liegt nicht hinter dem Ende des Arrays, sondern an Index 0. Dann ist das Array voll, und die siebte Bestellung lässt es wachsen:

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }


  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }


  dequeue() {
    if (this.size === 0) {
      throw new Error("leere Warteschlange");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }


  isEmpty() {
    return this.size === 0;
  }


  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}
Schritt für Schritt, in Worten
  1. Eine Warteschlange für Lieferungen auf einem Array mit 4 Plätzen. head ist der Index der ersten Bestellung, size ist, wie viele warten.
  2. enqueue: Die neue Bestellung kommt auf (head + size) % 4. Drei Bestellungen belegen die Plätze 0, 1 und 2.
  3. dequeue nimmt die Bestellung bei head und schiebt head weiter. Sonst bewegt sich nichts: #103 bleibt auf Platz 2.
  4. #104: (2 + 1) % 4 = 3, der letzte Platz des Arrays.
  5. #105: (2 + 2) % 4 = 0. Das Ende des Arrays springt zurück an den Anfang, und die freien Plätze vorne werden wieder benutzt.
  6. #106 kommt auf Platz 1. Jetzt sind 4 von 4 belegt: Das Array ist voll, und der Erste in der Schlange steht auf Platz 2.
  7. #107 passt nicht mehr hinein. grow legt 8 Plätze an und kopiert in der Reihenfolge der Schlange, ab head: #103, #104, #105, #106. head wird 0.
  8. #107 kommt auf Platz 4. Eine Kopie pro Bestellung beim Wachsen und keine beim Entnehmen von vorne.
const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
console.log(String(q));
console.log(`Lieferung: ${q.dequeue()}`);
console.log(`Lieferung: ${q.dequeue()}`);
console.log(String(q));
for (let id = 104; id <= 106; id++) q.enqueue(`#${id}`);
console.log(String(q));
q.enqueue("#107");
console.log(String(q));
Ausgabe
[#101, #102, #103, -] head=0
Lieferung: #101
Lieferung: #102
[-, -, #103, -] head=2
[#105, #106, #103, #104] head=2
[#103, #104, #105, #106, #107, -, -, -] head=0

Sieh dir die dritte Zeile der Ausgabe an: [#105, #106, #103, #104] head=2. Der Erste in der Schlange ist #103 an Index 2, und #105 und #106 stehen vorn, weil dort Plätze frei waren. Die Reihenfolge im Array ist nicht die Reihenfolge der Schlange. Darum kopiert grow nicht eins zu eins.

Probier es aus

Wohin kommen #205 und #206?

const q = new JobQueue();
for (let id = 201; id <= 204; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
q.dequeue();
q.enqueue("#205");
q.enqueue("#206");
console.log(String(q));
Antwort

Probier es aus

Ergänze

Die neue Bestellung kommt auf den Platz:

const tail = (this.head + this.size) % ;

Die Idee

Was es kostet

Zähle die Verschiebungen von Anfragen, die schon geschrieben sind: die Kopien beim Wachsen und das Vorrücken bei der Entnahme von Index 0. Beide Warteschlangen beginnen mit 4 Plätzen und verdoppeln sich. 10.000 Anfragen kommen herein, dann gehen alle wieder:

function shiftMoves(n) {
  let items = new Array(4);
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) bigger[i] = items[i];
      moves += size;
      items = bigger;
    }
    items[size++] = job;
  }
  while (size > 0) {
    for (let i = 1; i < size; i++) {
      items[i - 1] = items[i];
      moves++;
    }
    size--;
  }
  return moves;
}


function ringMoves(n) {
  let items = new Array(4);
  let head = 0;
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) {
        bigger[i] = items[(head + i) % items.length];
        moves++;
      }
      items = bigger;
      head = 0;
    }
    items[(head + size) % items.length] = job;
    size++;
  }
  while (size > 0) {
    head = (head + 1) % items.length;
    size--;
  }
  return moves;
}
for (const n of [1000, 10000]) {
  console.log(`${n}: Liste ${shiftMoves(n)}, Ring ${ringMoves(n)}`);
}
Ausgabe
1000: Liste 500520, Ring 1020
10000: Liste 50011380, Ring 16380

Lass es laufen, auch bis 100.000:

  • Liste: an Index 0 entfernen O(n²)
  • Ringpuffer O(n)
Algorithmusn = 10n = 1.000n = 10.000n = 100.000
Liste: an Index 0 entfernen57500.52050.011.380≈ 5.001.138.000
Ringpuffer121.02016.380131.068
Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Bei 10.000 Anfragen macht die Liste 50.011.380 Verschiebungen und der Ring 16.380, alle vom Wachsen. Eine Entnahme von Index 0 ist O(n), also sind n Entnahmen O(n²). Im Ring ist eine Entnahme O(1) und ein Hinzufügen im Durchschnitt O(1), wie beim Stapel.

Genauer, für Neugierige

So ist es in den Sprachen:

  • Java: ArrayDeque ist ein Ringpuffer: ein Array elements und die Indizes head und tail. Ein Platz bleibt immer frei, um „leer“ (head == tail) von „voll“ zu unterscheiden, darum beginnt das Array mit 17 Plätzen für 16 Elemente. Ist es voll, wächst ein kleines Array auf etwas mehr als das Doppelte, ein großes um 50 %.
  • C#: Queue<T> ist ein Ringpuffer mit _array, _head, _tail und _size. Er beginnt mit 4 Plätzen und verdoppelt das Array, wenn es voll ist. Stack<T> ist ein Array, das sich ebenfalls verdoppelt.
  • Python: collections.deque ist kein Ringpuffer, sondern eine verkettete Liste aus Blöcken zu je 64 Plätzen. Darum sind beide Enden O(1). list.pop(0) ist O(n), genau wie im Problem.
  • JavaScript: Es gibt keine eingebaute Warteschlange. shift() verschiebt alle Elemente des Arrays. V8 macht es manchmal schnell, indem es den Anfang des Arrays verschiebt statt der Elemente, aber nicht bei großen Arrays, und es ist nicht zugesichert. Für eine große Warteschlange schreibst du einen Ring wie diesen oder eine Warteschlange aus Knoten.

Manche Ringe halten tail statt size, andere beide. Das ist nur eine andere Schreibweise derselben Sache: tail = (head + size) % Plätze.

Probier es aus

Finde den Fehler

Jemand hat grow kürzer geschrieben. Die Bestellungen vor dem Wachsen kommen in der richtigen Reihenfolge heraus, danach durcheinander:

grow() {
  const n = this.items.length;
  const bigger = new Array(n * 2).fill(null);
  for (let i = 0; i < this.size; i++) {
    bigger[i] = this.items[i];
  }
  this.items = bigger;
  this.head = 0;
}
const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
for (let id = 104; id <= 107; id++) q.enqueue(`#${id}`);
const order = [];
while (!q.isEmpty()) order.push(q.dequeue());
console.log(order.join(" "));
Ausgabe
#105 #106 #103 #104 #107

In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

Übung

Die letzten 5 Zeilen des Logs

Löse die Aufgabe in deinem Editor.

Die letzten 5 Zeilen. Der Server des Shops schreibt zu jeder Aktion eine Zeile ins Log. Bei einem Fehler willst du die letzten 5 Zeilen sehen, nicht das ganze Log. Schreibe LastLines mit einem Ring aus 5 Plätzen, der nie wächst: Solange Platz ist, kommt eine Zeile auf (head + size) % 5; ist er voll, überschreibt die neue Zeile die älteste (bei head), und head rückt vor. Eine Methode lines() gibt die Zeilen von der ältesten zur neuesten zurück. Gib ihr die acht Zeilen:

09:00 Login: maria
09:02 Warenkorb: +2
09:03 Zahlung: 48 €
09:05 Logout: maria
09:07 Login: jonas
09:08 Suche: Kaffee
09:09 Warenkorb: +1
09:11 Zahlung: 12 €
Ausgabe
Die letzten 5:
09:05 Logout: maria
09:07 Login: jonas
09:08 Suche: Kaffee
09:09 Warenkorb: +1
09:11 Zahlung: 12 €

Weitere Aufgaben

  • Klammern und Tags. Erweitere die Prüfung der Vorlage auf die Tags <b>…</b> und <i>…</i>: Der Stapel hält die Namen der offenen Tags.
  • Eine Warteschlange, die schrumpft. Warten nach der Morgenspitze nur noch 10 Anfragen in einer Warteschlange mit 8192 Plätzen, bleibt der Speicher leer. Lass die Warteschlange ihr Array halbieren, wenn sie weniger als zu einem Viertel gefüllt ist. Warum nicht, wenn sie weniger als zur Hälfte gefüllt ist?
  • Ein Stapel aus zwei Warteschlangen. Baue einen Stapel nur aus zwei deiner Warteschlangen. Was kostet pop?

Test

Teste dich

1. Warum prüft ein Stapel die Klammern, statt einfach die öffnenden und die schließenden zu zählen?
2. Eine Warteschlange mit 10.000 Wartenden liegt auf einer gewöhnlichen Liste, und jede Entnahme geschieht bei Index 0. Wie viele Verschiebungen kostet eine Entnahme von vorne?
3. Ein Ringpuffer mit 8 Plätzen: head = 6, size = 3. Auf welchen Platz kommt die neue Bestellung?
4. Der Ringpuffer ist voll und muss wachsen. Warum kann grow nicht einfach items[0], items[1] … in das neue Array kopieren?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·