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
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.
queue->head📍 Die Markierung am ältesten Auftrag(queue->head + queue->size) % 4➕ Das nächste freie Fach, im Kreis herumpop(&queue, &value)🖨️ Den ältesten Auftrag nehmen: 7queue->size == 4🚫 Alle vier Fächer sind belegtEine 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
headist der Index des vorderen Elements, undsizeist die Anzahl gespeicherter Elemente.pushschreibt an(queue->head + queue->size) % 4und springt nach Index 3 auf 0.popliest an der Stelleheadund rückt ihn mit% 4weiter, also kommt 7 zuerst heraus.- In C++ bietet
std::queuedie Funktionenpush,frontundpop, 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++
#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);
}
7
#include <iostream>
#include <queue>
int main() {
std::queue<int> values;
values.push(7);
values.push(9);
std::cout << values.front() << '\n';
values.pop();
}
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.
Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.
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.
int tail = queue->head + queue->size;
int tail = (queue->head + queue->size) % 4;
Beim Entfernen alle Elemente verschieben
Verschieben macht jedes Entfernen langsam. Schieb stattdessen head weiter.
for (int i = 1; i < size; i++) data[i - 1] = data[i];
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