CodeUtility
Mach dir das Coderleben leicht!
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++.

Einführung

Eine Warteschlange (queue) folgt dem Prinzip zuerst hinein, zuerst heraus (FIFO). Mit einem normalen Array müsste man bei jeder Entnahme die übrigen Elemente nachrücken lassen. Ein Ringpuffer (circular buffer) löst das, indem die Indizes wieder von vorn beginnen und frei gewordene Plätze wiederverwendet werden.

Wichtige Punkte

  • Lege fest, welche Bedingungen in der Datenstruktur immer gelten müssen (Invarianten), bevor du die Operationen schreibst.
  • Behandle die Fälle leer, voll und fehlgeschlagene Speicherreservierung vollständig.
  • Bewerte bei jeder Operation Komplexität und Speicherverwaltung gemeinsam.

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);
}
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();
}
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.

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