Datenstrukturen in C/C++

Ringpuffer-Warteschlange (circular queue) in C und C++

In dieser Lektion implementierst du eine Warteschlange nach dem Prinzip zuerst hinein, zuerst heraus, mit einem Ringpuffer in C und std::queue in C++.

  • Fortgeschritten
  • 5 Min. Lesezeit
  • 2 ausführbare Beispiele

Einführung

Das Problem

Druckaufträge, Support-Tickets und Netzwerkpakete sollen in der Reihenfolge ihres Eintreffens bearbeitet werden. Eine Queue hält diese Reihenfolge ein, und ein Ringpuffer schafft das in einem festen Array, ohne nach jedem Entfernen Elemente zu verschieben.

Stell es dir so vor

Eine Ringpuffer-Queue ist wie ein Ring aus 4 nummerierten Fächern, in denen wartende Druckaufträge liegen. Eine Markierung zeigt auf den ältesten Auftrag, und neue Aufträge kommen ins nächste freie Fach. Nach Fach 3 geht es für beide wieder bei Fach 0 weiter, sodass nie etwas verschoben werden muss.

Vom Ring aus Fächern zum Code
queue->head📍 Die Markierung am ältesten Auftrag
(queue->head + queue->size) % 4➕ Das nächste freie Fach, im Kreis herum
pop(&queue, &value)🖨️ Den ältesten Auftrag nehmen: 7
queue->size == 4🚫 Alle vier Fächer sind belegt
Wer zuerst kommt, geht zuerst raus, und die Positionen laufen im Kreis.
In einem Satz

Eine Queue ist eine Sammlung nach dem Prinzip first-in, first-out (FIFO). Eine ringförmige Queue speichert die Elemente in einem festen Array und lässt die Positionen mit dem Modulo-Operator umlaufen.

Wichtige Punkte

  1. head ist der Index des vorderen Elements, und size ist die Anzahl gespeicherter Elemente.
  2. push schreibt an (queue->head + queue->size) % 4 und springt nach Index 3 auf 0.
  3. pop liest an der Stelle head und rückt ihn mit % 4 weiter, also kommt 7 zuerst heraus.
  4. In C++ bietet std::queue die Funktionen push, front und pop, ohne dass du Indizes verwalten musst.

Wann du es brauchst

  • Aufgaben- und Nachrichten-Queues, die in der Reihenfolge des Eintreffens abgearbeitet werden.
  • Puffer fester Größe für Audio, Netzwerkdaten oder Logs.
  • Breitensuche.

Wann du es nicht brauchst

  • Das neueste Element soll zuerst heraus: Nimm einen Stack.
  • Elemente haben Prioritäten: Nimm eine Priority Queue (std::priority_queue).

So funktioniert es

Mit enqueue und dequeue siehst du, dass die Elemente in derselben Reihenfolge gehen, in der sie gekommen sind.

Codebeispiele in C und C++

C
Code ausführen →
main.c
#include <stdio.h>

typedef struct {
    int data[4];
    int head;
    int size;
} Queue;

int push(Queue *queue, int value) {
    if (queue->size == 4) return 0;
    int tail = (queue->head + queue->size) % 4;
    queue->data[tail] = value;
    ++queue->size;
    return 1;
}

int pop(Queue *queue, int *value) {
    if (queue->size == 0) return 0;
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % 4;
    --queue->size;
    return 1;
}

int main(void) {
    Queue queue = {{0}, 0, 0};
    int value;
    push(&queue, 7);
    push(&queue, 9);
    pop(&queue, &value);
    printf("%d\n", value);
}
Run-Button für dieses Beispiel erstellen Ergebnis der Ausführung
7
C++
Code ausführen →
main.cpp
#include <iostream>
#include <queue>

int main() {
    std::queue<int> values;
    values.push(7);
    values.push(9);
    std::cout << values.front() << '\n';
    values.pop();
}
Run-Button für dieses Beispiel erstellen Ergebnis der Ausführung
7

C und C++ im Vergleich

Die Warteschlange in C speichert die Position des Anfangs head und die Anzahl der Elemente size. Die Position eines neuen Elements wird mit dem Rest der Division (head + size) % 4 berechnet, deshalb springt der Index am Ende des Arrays automatisch zum Anfang zurück. In C++ ist std::queue ein Container-Adapter (container adapter), der die Operationen front, push und pop bereits mitbringt.

C

Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.

C++

Klassen und Container schützen die Korrektheit der Daten und verwalten ihre Ressourcen selbst.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

  • Ergänze Tests für den leeren Zustand und für das Erreichen der Kapazitätsgrenze.
  • Schreibe die Speicherfreigabe und prüfe auf Speicherlecks.
  • Vergleiche die Komplexität mit dem entsprechenden Container der Standardbibliothek.

Häufige Fehler

Index nicht umlaufen lassen

Ohne % 4 läuft das Ende über das Array hinaus.

Problem
int tail = queue->head + queue->size;
Lösung
int tail = (queue->head + queue->size) % 4;

Beim Entfernen alle Elemente verschieben

Verschieben macht jedes Entfernen langsam. Schieb stattdessen head weiter.

Problem
for (int i = 1; i < size; i++) data[i - 1] = data[i];
Lösung
queue->head = (queue->head + 1) % 4;

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges