Grundlagen der Datenstrukturen: Arrays, Stacks, Queues, Bäume und Hashtabellen

Dieser Beitrag ist als Lehrmaterial gedacht. Die Beispiele sind absichtlich klein. In echtem C++ sollte zunächst ein passender Standardcontainer verwendet werden, solange keine gemessene Anforderung eine eigene Implementierung rechtfertigt.

Beim Lernen von Datenstrukturen scheint es oft um Namen wie push, pop und Listenknoten zu gehen. Die eigentliche Fähigkeit besteht darin, Daten so anzuordnen, dass die häufigsten Operationen eines Programms einfach, günstig und vorhersehbar werden.

Dieselben zehn Werte gehören bei häufigem Indexzugriff in ein Array, für Undo in einen Stack, bei Verarbeitung nach Ankunft in eine Queue und für Schlüsselzugriff in eine Hashtabelle.

Datenstruktur und abstrakter Datentyp

Ein Stack definiert die Regel, dass das zuletzt eingefügte Element zuerst entfernt wird. Er kann intern ein zusammenhängendes Array oder eine verkettete Liste verwenden. Sichtbare Operationen und Regeln bilden den abstrakten Datentyp; die konkrete Speicherung ist seine Implementierung.

• push fügt oben ein.
• pop entfernt das oberste Element.
• top oder peek liest es ohne Entfernung.
• empty prüft auf Leerheit.
• size liefert die Anzahl.

std::stack ist in C++ ein Containeradapter und verwendet standardmäßig std::deque.

Minimales Vokabular der Komplexität

Zusätzlich zählen Speicherbedarf, Cache-Lokalität, Allokationen, ungültige Iteratoren und Implementierungsaufwand.

Arrays liegen zusammenhängend im Speicher

int scores[5] = { 10, 20, 30, 40, 50 };

Aus Basisadresse und Elementgröße lässt sich die Adresse von Index i direkt berechnen.

address(i) = base + i × sizeof(element)

Indexzugriff ist O(1), und lineares Durchlaufen ist oft cachefreundlich. Einfügen in der Mitte verschiebt spätere Elemente und kostet im schlechtesten Fall O(N). Für feste Größen stellt C++ std::array bereit.

Dynamische Arrays und std::vector

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

Ein vector verwaltet zusammenhängenden Speicher, seine size und die verfügbare capacity. Solange Platz vorhanden ist, ist Anhängen konstant. Bei Platzmangel werden ein größerer Block angelegt und Elemente verschoben. Eine Reallokation ist O(N), eine lange Folge von push_back jedoch amortisiert O(1) pro Einfügung.

reserve reduziert Reallokationen, wenn die ungefähre Anzahl bekannt ist. Nach einer Reallokation können alte Zeiger, Referenzen und Iteratoren ungültig sein.

Verkettete Listen

struct Node
{
    int value;
    Node* next;
};

Ist ein Knoten bereits bekannt, benötigt das Einfügen direkt dahinter nur wenige Linkänderungen und ist O(1). Der hundertste Knoten muss trotzdem von vorn erreicht werden; wahlfreier Zugriff ist O(N).

Listen benötigen zusätzlichen Zeigerspeicher, besitzen oft schwächere Cache-Lokalität und erschweren bei eigener Implementierung den Besitz. Viele Einfügungen allein machen eine Liste nicht schneller als einen vector; auch das Finden der Position kostet Zeit.

Stacks entfernen das neueste Element zuerst

Ein Stack folgt LIFO, Last In First Out.

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

top ist 30, danach bleiben 10 und 20.

pop gibt keinen Wert zurück

std::stack::pop() entfernt nur und hat den Rückgabetyp void. Der Wert muss zuerst gelesen werden.

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

top und pop dürfen nicht auf einem leeren Stack aufgerufen werden.

Ein kleiner Stack auf vector-Basis

template <typename T>
class SimpleStack
{
public:
    void push(const T& value) { values_.push_back(value); }

    void pop()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        return values_.back();
    }

    bool empty() const { return values_.empty(); }

private:
    std::vector<T> values_;
};

Stacks eignen sich für Funktionsaufrufe, Undo-Verläufe, Klammerprüfung, Tiefensuche, Postfix-Auswertung und iterative Varianten rekursiver Verfahren.

Queues entfernen das älteste Element zuerst

Eine Queue folgt FIFO, First In First Out.

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

first ist 101. Queues passen zu Scheduling, Nachrichten, Druckaufträgen, Breitensuche und Paketpuffern.

Ringpuffer

Statt beim Entfernen des ersten Arrayelements alles zu verschieben, werden getrennte Head- und Tail-Indizes verwaltet. Am physischen Ende beginnt ein Index mittels Modulo wieder bei null.

tail = (tail + 1) % Capacity;
head = (head + 1) % Capacity;

Ein fester Ringpuffer eignet sich für Audio, Spielereignisse und begrenzte Producer-Consumer-Pipelines. Mehrere Threads benötigen trotzdem Synchronisation oder eine geeignete concurrent queue.

Deque und Priority Queue

std::deque erlaubt Einfügen und Entfernen an beiden Enden. Das passt zu Work Stealing, Sliding Windows und beidseitigen Warteschlangen. Der gesamte Speicher ist nicht wie beim vector garantiert zusammenhängend.

Eine Priority Queue liefert nicht das älteste, sondern das höchstpriorisierte Element.

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);
int highest = scores.top();
scores.pop();

Sie basiert meist auf einem Heap. Das oberste Element wird in O(1) gelesen; Einfügen und Entfernen kosten O(log N).

Hashtabellen

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

Eine Hashfunktion wählt anhand des Schlüssels einen Bucket. Bei guter Verteilung und passendem Load Factor sind Suche, Einfügen und Löschen durchschnittlich O(1). Kollisionen sind unvermeidbar, und der schlechteste Fall kann O(N) erreichen.

Bei eigenen Schlüsseln müssen Gleichheit und Hash zusammenpassen: Gleiche Schlüssel müssen denselben Hash besitzen.

Bäume und binäre Suchbäume

Bäume stellen Dateisysteme, UI, Scene Graphs und Dokumenthierarchien dar. Die Root hat keinen Parent, ein Leaf keine Children. Depth misst den Abstand zur Root, Height den Abstand zum tiefsten Leaf.

Ein binärer Suchbaum hat höchstens zwei Kinder. Üblicherweise liegen kleinere Schlüssel links und größere rechts. Ausbalanciert sind Suche, Einfügen und Löschen O(log N). Sortierte Eingaben können einen einfachen Baum zu einer Kette und damit zu O(N) machen.

std::map erhält die Schlüsselordnung mit O(log N). Wenn keine Ordnung nötig ist und durchschnittlich konstante Suche wichtiger ist, kommt std::unordered_map infrage.

Heaps

In einem Max-Heap ist jeder Parent mindestens so groß wie seine Children, in einem Min-Heap umgekehrt. Die gesamte Sammlung ist nicht vollständig sortiert.

Ein vollständiger Binärbaum lässt sich effizient in einem Array speichern. Für den nullbasierten Index i gilt:

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

Heaps eignen sich zum wiederholten Entnehmen eines Minimums oder Maximums. Die Suche nach einem beliebigen Wert bleibt im Allgemeinen O(N).

Tries und Graphen

Ein Trie verwendet Zeichen oder Bits eines Schlüssels als Pfad und teilt Präfixe. Eine Suche wird häufig mit O(L) für Schlüssellänge L beschrieben. Einsatzgebiete sind Autovervollständigung, Wörterbücher und Routing.

Ein Graph besteht aus Vertices und Edges. Eine Adjazenzmatrix prüft eine Kante in O(1), braucht aber O(V²) Speicher. Eine Adjazenzliste benötigt ungefähr O(V + E) und eignet sich für dünne Graphen.

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

BFS verwendet eine Queue, DFS den Aufrufstack oder einen ausdrücklichen Stack.

Repräsentative Komplexitäten

Auswahl und typische Fehler

Zu prüfen sind häufigste Operation, notwendige Reihenfolge, Indexzugriff, Schlüsselsuche oder Extremwert, maximale Anzahl, Zeigerstabilität, zusammenhängender Speicher für externe APIs und Threadzugriff. Für eine normale Wertfolge ist std::vector ein guter Ausgangspunkt.

Häufige Fehler sind Zugriffe auf leere Stacks oder Queues, die Annahme eines Rückgabewerts von pop, alte vector-Zeiger nach Reallokation, das Ignorieren der Positionssuche bei Listen, garantiertes O(1) bei Hashing, unbegrenzte Rekursion und unklare Besitzverhältnisse bei Rohzeigern.

Zusammenfassung

Arrays und vectors bieten schnellen Indexzugriff und gute Lokalität. Listen ändern Links an bekannter Position günstig, bezahlen aber für Traversierung und verteilten Speicher. Stack, Queue, Deque und Priority Queue bestimmen unterschiedliche Entnahmereihenfolgen. Hashtabellen bieten schnelle durchschnittliche Schlüsselsuche, balancierte Bäume Ordnung, Heaps Extremwerte und Graphen allgemeine Beziehungen.

Die beste Datenstruktur ist nicht die komplizierteste, sondern diejenige, die die wirklichen Operationen des Programms klar und vorhersehbar macht.