Beherrschen von Warteschlangen in C: Ein umfassender Leitfaden

Warteschlangen (Queues) sind eine fundamentale Datenstruktur in C, die häufig zum Speichern und Verwalten von Daten verwendet wird. Sie folgen dem Prinzip “First In, First Out” (FIFO), was bedeutet, dass das erste hinzugefügte Element das erste ist, das entfernt wird. Um dies zu veranschaulichen, denken Sie an ein Busticket-Verkaufssystem, bei dem die Tickets nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“ verteilt werden. In diesem Leitfaden werden wir untersuchen, wie Warteschlangen in C funktionieren und die Schritte zur Implementierung mithilfe von Arrays durchgehen.

Wichtige Operationen in einer C-Warteschlange

In C erlaubt eine Warteschlange mehrere Operationen zur Verwaltung ihrer Datenelemente. Diese beinhalten:

• isEmpty(): Prüft, ob die Warteschlange leer ist.
• isFull(): Bestimmt, ob die Warteschlange ihre Kapazität erreicht hat.
• dequeue(): Entfernt das erste Element aus der Warteschlange.
• enqueue(): Fügt ein neues Element am Ende der Warteschlange hinzu.
• Front: Zeigt auf das erste Element der Warteschlange.
• Rear: Zeigt auf das letzte Element der Warteschlange.

Wie eine Warteschlange funktioniert

Die Warteschlange arbeitet nach dem FIFO-Prinzip. Hier ist eine Schritt-für-Schritt-Anleitung zum Funktionsablauf:

1. Initialisieren der Warteschlange: Setzen Sie sowohl den Front als auch den Rear-Zeiger auf -1. Dies zeigt an, dass die Warteschlange leer ist.
2. Enqueue-Operation: Beim Hinzufügen eines neuen Elements überprüfen Sie, ob ein Überlauf vorliegt (d. h. ob die Warteschlange voll ist). Wenn nicht, erhöhen Sie den Rear-Zeiger und fügen das neue Element an dieser Position ein. Beim ersten Element setzen Sie den Front auf 0.
3. Dequeue-Operation: Beim Entfernen eines Elements überprüfen Sie, ob ein Unterlauf vorliegt (d. h. ob die Warteschlange leer ist). Wenn die Warteschlange Elemente enthält, entfernen Sie das Element am Front-Zeiger und erhöhen den Front-Index. Wenn das letzte Element entfernt wird, setzen Sie beide Zeiger auf -1 zurück.

Implementierung einer Warteschlange in C

Warteschlangen in C können mit Arrays implementiert werden. Unten sehen Sie ein Beispiel, wie dies gemacht wird:

#include <stdio.h>
# define SIZE 100

void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;

main() {
    int ch;
    while (1) {
        printf("1.Enqueue Operation\n");
        printf("2.Dequeue Operation\n");
        printf("3.Display the Queue\n");
        printf("4.Exit\n");
        printf("Geben Sie Ihre Wahl der Operationen ein: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1: enqueue(); break;
            case 2: dequeue(); break;
            case 3: show(); break;
            case 4: exit(0);
            default: printf("Falsche Auswahl \n");
        }
    }
}

void enqueue() {
    int insert_item;
    if (Rear == SIZE - 1)
       printf("Überlauf \n");
    else {
        if (Front == - 1) Front = 0;
        printf("Einzufügendes Element in der Warteschlange\n: ");
        scanf("%d", &insert_item);
        Rear = Rear + 1;
        inp_arr[Rear] = insert_item;
    }
}

void dequeue() {
    if (Front == - 1 || Front > Rear) {
        printf("Unterlauf \n");
        return;
    } else {
        printf("Element aus der Warteschlange gelöscht: %d\n", inp_arr[Front]);
        Front = Front + 1;
    }
}

void show() {
    if (Front == - 1) {
        printf("Leere Warteschlange \n");
    } else {
        printf("Warteschlange: \n");
        for (int i = Front; i <= Rear; i++) {
            printf("%d ", inp_arr[i]);
        }
        printf("\n");
    }
}

Implementierung einer Warteschlange mit Stacks

Warteschlangen können auch mit Stacks implementiert werden. Dafür benötigen Sie zwei Stacks (S1 und S2). Die Enqueue- und Dequeue-Operationen können je nach Implementierung entweder kostenintensiv gemacht werden.

Methode 1: Kostenintensive Enqueue-Operation

• Verschieben Sie alle Elemente von S1 nach S2.
• Fügen Sie das neue Element in S1 ein.
• Verschieben Sie alle Elemente von S2 zurück nach S1.
• Dequeue erfolgt durch Poppen von S1.