Stacks und Queues in C

Stacks und Queues sind lineare Datenstrukturen zum Speichern und Verwalten von Daten.

In dieser Lektion lernen Sie:

• Wie Stacks funktionieren (LIFO – zuletzt hinein, zuerst heraus).
• Wie Queues funktionieren (FIFO – zuerst hinein, zuerst heraus).
• Wie Sie Stacks und Queues in C implementieren.

Was ist ein Stack?

Ein Stack folgt dem Prinzip Last In, First Out (LIFO).

Operationen:

• Push - Fügt ein Element oben hinzu.
• Pop - Entfernt das oberste Element.
• Peek - Zeigt das oberste Element an, ohne es zu entfernen.

Beispiel: Einen Stack implementieren

Dieses Programm zeigt Stack-Operationen mithilfe eines Arrays.

#include <stdio.h>
#define MAX 5

int stack[MAX], top = -1;

void push(int value) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = value;
    }
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    } else {
        return stack[top--];
    }
}

int main() {
    push(10);
    push(20);
    printf("Popped: %d\n", pop());
    return 0;
}

Was ist eine Queue?

Eine Queue folgt dem Prinzip First In, First Out (FIFO).

Operationen:

• Enqueue - Fügt ein Element am Ende hinzu.
• Dequeue - Entfernt ein Element am Anfang.
• Peek - Zeigt das vorderste Element an, ohne es zu entfernen.

Beispiel: Eine Queue implementieren

Dieses Programm zeigt Queue-Operationen mithilfe eines Arrays.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        queue[++rear] = value;
    }
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
        return -1;
    } else {
        return queue[front++];
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

Ringpuffer-Queue

Eine Ringpuffer-Queue überwindet die Einschränkungen einer normalen Queue, indem sie leere Speicherplätze wiederverwendet.

Die Operationen bleiben gleich, laufen aber im Array am Ende wieder zum Anfang zurück.

Beispiel: Ringpuffer-Queue

Dieses Programm zeigt die Implementierung einer Ringpuffer-Queue.

#include <stdio.h>
#define MAX 5

int queue[MAX], front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0;
        rear = (rear + 1) % MAX;
        queue[rear] = value;
    }
}

int dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return -1;
    }
    int data = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return data;
}

int main() {
    enqueue(10);
    enqueue(20);
    printf("Dequeued: %d\n", dequeue());
    return 0;
}

Anwendungen von Stacks und Queues

Stacks werden verwendet für:

• Die Verwaltung von Funktionsaufrufen (Rekursion).
• Rückgängig- und Wiederholen-Operationen.
• Die Auswertung von Ausdrücken.

Queues werden verwendet für:

• Die Planung von Aufgaben in Betriebssystemen.
• Die Verwaltung von Anfragen in Webservern.
• Die Datenübertragung in Netzwerken.

Zusammenfassung

In dieser Lektion haben Sie Folgendes gelernt:

• Wie Stacks und Queues funktionieren.
• Wie Sie Stack- und Queue-Operationen implementieren.
• Welche Anwendungen Stacks und Queues haben.

Als Nächstes sehen wir uns Bäume und Graphen in C an.