Stapel und Warteschlange in C#

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: Stack<T> und Queue<T>. 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
{
    private char[] items = new char[4];
    private int size = 0;

    public void Push(char c)
    {
        if (size == items.Length)
        {
            Array.Resize(ref items, size * 2);
        }
        items[size] = c;
        size++;
    }

    public char Pop()
    {
        if (size == 0) throw new InvalidOperationException("leerer Stapel");
        size--;
        return items[size];
    }

    public bool IsEmpty => 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)).

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.

static int FirstError(string text)
{
    var opened = new CharStack();
    for (int i = 0; i < text.Length; i++)
    {
        char c = text[i];
        if ("([{".Contains(c))
        {
            opened.Push(c);
        }
        else if (")]}".Contains(c))
        {
            if (opened.IsEmpty) return i;
            if ("([{".IndexOf(opened.Pop()) != ")]}".IndexOf(c)) return i;
        }
    }
    return opened.IsEmpty ? -1 : text.Length;
}

string[] templates =
[
    "Bestellung {order}: [{items}] (gesamt {total} €)",
    "Bestellung {order}: [{items}) (gesamt {total} €)",
    "Bestellung {order}: [{items}] (gesamt {total} €"
];
foreach (string t in templates)
{
    int at = FirstError(t);
    Console.WriteLine(at < 0 ? "OK" : $"Fehler an Position {at}");
}

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.WriteLine(FirstError("({total)}"));

Antwort

-1

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:

var jobs = new List<string>();
for (int id = 1; id <= 10_000; id++)
{
    jobs.Add("#" + id);
}
int done = 0;
while (jobs.Count > 0)
{
    string job = jobs[0];
    jobs.RemoveAt(0);
    done++;
}
Console.WriteLine($"bearbeitet: {done}");

bearbeitet: 10000

Es sieht harmlos aus, aber jobs.RemoveAt(0) 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
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;

    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }

    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }

    public bool IsEmpty => size == 0;

    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}

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

public override string ToString() =>
    $"[{string.Join(", ", items.Select(s => s ?? "-"))}] head={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
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;

    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }

    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }

    public bool IsEmpty => size == 0;

    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}

Schritt für Schritt, in Worten

Eine Warteschlange für Lieferungen auf einem Array mit 4 Plätzen. head ist der Index der ersten Bestellung, size ist, wie viele warten.
Enqueue: Die neue Bestellung kommt auf (head + size) % 4. Drei Bestellungen belegen die Plätze 0, 1 und 2.
Dequeue nimmt die Bestellung bei head und schiebt head weiter. Sonst bewegt sich nichts: #103 bleibt auf Platz 2.
#104: (2 + 1) % 4 = 3, der letzte Platz des Arrays.
#105: (2 + 2) % 4 = 0. Das Ende des Arrays springt zurück an den Anfang, und die freien Plätze vorne werden wieder benutzt.
#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.
#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.
#107 kommt auf Platz 4. Eine Kopie pro Bestellung beim Wachsen und keine beim Entnehmen von vorne.

var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
Console.WriteLine($"Lieferung: {q.Dequeue()}");
Console.WriteLine($"Lieferung: {q.Dequeue()}");
Console.WriteLine(q);
for (int id = 104; id <= 106; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
q.Enqueue("#107");
Console.WriteLine(q);

[#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?

var q = new JobQueue();
for (int id = 201; id <= 204; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
q.Dequeue();
q.Enqueue("#205");
q.Enqueue("#206");
Console.WriteLine(q);

Antwort

[#204, #205, #206, -] head=0

[-, -, -, #204, #205, #206, -, -] head=3

[#205, #206, -, #204] head=3

Probier es aus

Ergänze

Die neue Bestellung kommt auf den Platz:

int tail = (head + 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:

static long ShiftMoves(int n)
{
    int[] items = new int[4];
    int size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            moves += size;
            Array.Resize(ref items, size * 2);
        }
        items[size++] = job;
    }
    while (size > 0)
    {
        for (int i = 1; i < size; i++)
        {
            items[i - 1] = items[i];
            moves++;
        }
        size--;
    }
    return moves;
}

static long RingMoves(int n)
{
    int[] items = new int[4];
    int head = 0, size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[size * 2];
            for (int 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;
}

foreach (int n in new[] { 1000, 10000 })
{
    Console.WriteLine($"{n}: Liste {ShiftMoves(n)}, Ring {RingMoves(n)}");
}

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)

Algorithmus	n = 10	n = 1.000	n = 10.000	n = 100.000
Liste: an Index 0 entfernen	57	500.520	50.011.380	≈ 5.001.138.000
Ringpuffer	12	1.020	16.380	131.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:

private void Grow()
{
    var bigger = new string?[items.Length * 2];
    for (int i = 0; i < size; i++)
    {
        bigger[i] = items[i];
    }
    items = bigger;
    head = 0;
}

var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
for (int id = 104; id <= 107; id++) q.Enqueue("#" + id);
var order = new List<string>();
while (!q.IsEmpty) order.Add(q.Dequeue());
Console.WriteLine(string.Join(" ", order));

#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 €

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?Weil Zählen langsamer istWeil Zählen bei mehr als 10 Klammern nicht funktioniertWeil die zuletzt geöffnete Klammer als Erste geschlossen werden muss und eine Zahl nicht weiß, welche die letzte war

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?Ungefähr so viele, wie hinter dem Ersten warten: Alle rücken einen Platz nach vornKeineEine

3. Ein Ringpuffer mit 8 Plätzen: head = 6, size = 3. Auf welchen Platz kommt die neue Bestellung?Auf 9Auf 0Auf 1

4. Der Ringpuffer ist voll und muss wachsen. Warum kann grow nicht einfach items[0], items[1] … in das neue Array kopieren?Weil das neue Array kleiner istEs kann: Die Plätze sind dieselbenWeil der Erste in der Schlange bei head steht, nicht bei 0; die Kopie muss in der Reihenfolge der Schlange sein, ab head

Stapel und Warteschlange

Cookies