Implementierung einer Queue in C

Hier ist eine Implementierung einer Queue (LILO: Last In, Last Out / FIFO: First In, First Out) in C, die Werte beliebiger Typen speichern kann. Diese Implementierung soll eher als Anregung dienen und zeigen, wie man prinzipiell solch eine Aufgabe lösen kann. Es gehört zu der "Grundausbildung" eines Programmierers dazu, zu wissen, wie Datenstrukturen wie eine Queue oder ein Stack implementiert werden können und wie diese intern arbeiten. Dieses Beispiel zeigt, dass es einfacher ist, den ADT (ADT: Abstrakter DatenTyp) Queue zu implementieren, als man vielleicht anfänglich denken mag.

Header-Datei "queue.h"

int queueAdd(void * value);
void * queueRemove(void);
int queueCount(void);

Hinweise zur Namensgebung der Methoden

Da C keine Namespaces kennt und ich Namens-Konflikte mit anderen evtl. vorhandenen Methoden vermeiden wollte, habe ich die Methoden jeweils mit dem Präfix queue beginnen lassen.

Implementierung "queue.c"

#include <stdlib.h>
#include "queue.h"


typedef struct ELEMENT {
    void * value;
    struct ELEMENT * successor;
} ELEMENT;


static ELEMENT * head;
static int count = 0;


int queueAdd(void * value) {
    ELEMENT * newElement = (ELEMENT *)malloc(sizeof(ELEMENT));
    //
    if (newElement == NULL) {
        return 0;
    }
    //
    newElement->value = value;
    newElement->successor = NULL;
    //
    if (head == NULL) {
        head = newElement;
    } else {
        ELEMENT * predecessor = head;
        //
        while (predecessor->successor != NULL) {
            predecessor = predecessor->successor;
        }
        //
        predecessor->successor = newElement;
    }
    //
    count++;
    //
    return 1;
}

void * queueRemove(void) {
    if (head == NULL) {
        return NULL;
    }
    //
    ELEMENT * newHead = head->successor;
    //
    void * result = head->value;
    //
    free(head);
    //
    head = newHead;
    //
    count--;
    //
    return result;
}

int queueCount(void) {
    return count;
}

Beispiel für die Verwendung der Queue

Hier noch ein kleines Beispiel für die Verwendung der Queue. Hier werden MYSTRUCT-Strukturen verwaltet, um zu zeigen, dass die Queue prinzipiell mit allen "Typen" funktioniert.

#include <stdio.h>
#include "queue.h"

typedef struct MYSTRUCT {
    int valueInt;
    char valueChar;
} MYSTRUCT;

int main(int argc, char **argv) {
    MYSTRUCT s1, s2, s3, s4;
    //
    s1.valueInt = 1;
    s1.valueChar = 'a';
    //
    s2.valueInt = 2;
    s2.valueChar = 'b';
    //
    s3.valueInt = 3;
    s3.valueChar = 'c';
    //
    s4.valueInt = 4;
    s4.valueChar = 'd';
    //
    // Add some values to our queue
    //
    queueAdd(&s3);
    queueAdd(&s4);
    queueAdd(&s1);
    queueAdd(&s2);
    //
    printf("COUNT: %d\n",queueCount());
    //
    // And now remove them.
    // Since we added the elements in the order s3 -> s4 -> s1 -> s2
    // and since we use a QUEUE (LILO), we expect the same order
    // removing the elements
    //
    void * removed;
    MYSTRUCT * removedMYSTRUCT;
    //
    while ((removed = queueRemove()) != NULL) {
        removedMYSTRUCT = (MYSTRUCT *)removed;
        //
        printf("REMOVED: %d | %c, REMAINING: %d\n", removedMYSTRUCT->valueInt, removedMYSTRUCT->valueChar, queueCount());
    }
}

Ausgabe des Beispiel-Programms

Das Beispiel gibt folgendes in der Konsole aus:

COUNT: 4
REMOVED: 3 | c, REMAINING: 3
REMOVED: 4 | d, REMAINING: 2
REMOVED: 1 | a, REMAINING: 1
REMOVED: 2 | b, REMAINING: 0

Kommentare

Das Hinzufügen von Kommentaren wurde vorübergehend deaktiviert.