Datenstrukturen in C/C++

Zirkuläre Queue

Ein Ringpuffer verwendet frei gewordene Arraypositionen erneut, ohne Elemente zu verschieben.

Was ist Zirkuläre Queue?

Ein Ringpuffer verwendet frei gewordene Arraypositionen erneut, ohne Elemente zu verschieben.

Implementiere First-in-first-out-Verarbeitung.

Wichtige Punkte

Definiere Invarianten vor den Operationen.
Behandle leere, volle und fehlgeschlagene Allokationen.
Bewerte Laufzeit und Speicherbesitz gemeinsam.

Codebeispiele in C und 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);
}

Erwartete Ausgabe

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

Erwartete Ausgabe

Vergleich zwischen C und C++

C verfolgt Kopf und Größe und verwendet Modulo; std::queue stellt front, push und pop bereit.

Strukturen und Operationen sind getrennt; Allokation ist explizit.

C++

Klassen und Container schützen Invarianten und verwalten Ressourcen.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Teste leere und volle Zustände.
Implementiere Cleanup und prüfe auf Leaks.
Vergleiche mit einem Standardcontainer.