Datenstruktur - Warteschlange

Eine Warteschlange ist eine lineare Datenstruktur, die dem First-In-First-Out-Prinzip (FIFO) folgt. Sie lässt sich mit dem realen Szenario des Anstehens beim Ticketkauf vergleichen — die Person, die zuerst ansteht, wird zuerst bedient.

Konzept und Prinzip der Warteschlange

Warteschlange — Veranschaulichung des FIFO-Prinzips

Vorne
front

→

Hinten
rear

← dequeueenqueue →

enqueue: am hinteren Ende einfügen | dequeue: am vorderen Ende löschen | Komplexität O(1)

FIFO-Überprüfung: enqueue 10→20→30, dequeue 10→20→30 (First In First Out)

Eine Warteschlange erlaubt nur das Einfügen an einem Ende (hinten) und das Löschen am anderen Ende (vorne).

Dies ist genau das Gegenteil des LIFO-Prinzips des Stapels.

Array-Implementierung der Warteschlange

Beispiel

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

struct Queue {
int items[MAX];
int front; /* Front-Zeiger: zeigt auf das erste Element */
int rear; /* Rear-Zeiger: zeigt auf die nächste Einfügeposition */
};

void initQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}

bool isEmpty(struct Queue* q) {
return q->front == q->rear;
}

bool isFull(struct Queue* q) {
return q->rear == MAX;
}

/* enqueue: Element am hinteren Ende hinzufügen */
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("Warteschlange ist voll!\n");
return;
}
q->items[q->rear++] = value; /* an rear schreiben, dann rear zurückbewegen */
printf("enqueue: %d\n", value);
}

/* dequeue: Element von front entfernen */
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Warteschlange ist leer!\n");
return -1;
}
return q->items[q->front++]; /* Element an front zurückgeben, dann front zurückbewegen */
}

int main() {
struct Queue q;
initQueue(&q);

enqueue(&q, 10); /* enqueue: 10 */
enqueue(&q, 20); /* enqueue: 20 */
enqueue(&q, 30); /* enqueue: 30 */

printf("dequeue: %d\n", dequeue(&q)); /* Ausgabe: dequeue: 10 (FIFO) */
printf("dequeue: %d\n", dequeue(&q)); /* Ausgabe: dequeue: 20 */
printf("dequeue: %d\n", dequeue(&q)); /* Ausgabe: dequeue: 30 */
return 0;
}

Eine mit einem normalen Array implementierte Warteschlange hat ein Problem mit "falschem Überlauf": Wenn enqueue und dequeue fortgesetzt werden, bewegen sich front und rear weiter zum Ende des Arrays, und selbst wenn am Anfang des Arrays reichlich leere Plätze vorhanden sind, können sie nicht wiederverwendet werden. Die Lösung besteht darin, einenRingpuffer。

Ringpuffer

Ringpuffer — Modulo-Operation für den Zeigerumlauf

Wichtige Formeln für Ringpuffer

enqueue: items[rear] = value; rear = (rear + 1) % MAX;

dequeue: value = items[front]; front = (front + 1) % MAX;

Leerprüfung: front == rear | Vollprüfung: (rear + 1) % MAX == front

Laufendes Beispiel (Kapazität=5, max. 4 Elemente): enqueue 10→20→30→40, dequeue 10→20, enqueue 50→60 → 60 wird an Index 0 gespeichert (Wraparound), wodurch freigegebener Speicher perfekt wiederverwendet wird.

Eine zirkuläre Warteschlange behandelt das Array logisch als Ringstruktur, bei der Kopf und Ende verbunden sind, und implementiert den Zeiger-Wraparound mittels Modulo-Arithmetik.

Beispiel

#include <stdio.h>
#include <stdbool.h>

#define MAX 5 /* absichtlich eine kleine Kapazität festgelegt, um den Kreiseffekt leichter beobachten zu können */

struct CircularQueue {
int items[MAX];
int front; /* vorderer Index */
int rear; /* hinterer Index (nächste Einfügeposition) */
};

void initQueue(struct CircularQueue* q) {
q->front = 0;
q->rear = 0;
}

/* Leerprüfung: front und rear fallen zusammen */
bool isEmpty(struct CircularQueue* q) {
return q->front == q->rear;
}

/* Vollprüfung: (rear + 1) % MAX == front Hinweis: Die zirkuläre Warteschlange lässt absichtlich eine Position leer, um leer von voll zu unterscheiden */
/* enqueue: an rear schreiben, dann rear kreisförmig vorrücken */
bool isFull(struct CircularQueue* q) {
return (q->rear + 1) % MAX == q->front;
}

"Zirkuläre Warteschlange ist voll!"
void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf(/* Modulo für den Umlauf */\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % MAX; "enqueue: %d (rear=%d)
printf(/* dequeue: Element bei front zurückgeben, dann front zyklisch weiterbewegen */\n", value, q->rear);
}

/* Dequeue: Element bei front zurückgeben, dann front zyklisch weiterbewegen */
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("Zirkuläre Warteschlange ist leer!\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % MAX; /* Modulo-Operation implementiert den Umlauf */
return value;
}

int main() {
struct CircularQueue q;
initQueue(&q);

enqueue(&q, 10); /* Einfügen: 10 (rear=1) */
enqueue(&q, 20); /* Einfügen: 20 (rear=2) */
enqueue(&q, 30); /* Einfügen: 30 (rear=3) */
enqueue(&q, 40); /* Einfügen: 40 (rear=4) — Kapazität 5, maximal 4 Elemente */

printf("Entfernen: %d\n", dequeue(&q)); /* Entfernen: 10 (front=1) */
printf("Entfernen: %d\n", dequeue(&q)); /* Entfernen: 20 (front=2) */

enqueue(&q, 50); /* Einfügen: 50 (rear=0 — springt an den Anfang zurück!) */
enqueue(&q, 60); /* Einfügen: 60 (rear=1) */

printf("Verbleibende Elemente: ");
while (!isEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n"); /* Ausgabe: Verbleibende Elemente: 30 40 50 60 */
return 0;
}

Anwendungsszenarien einer Warteschlange

Anwendungsszenarien	Beschreibung
Breitensuche (BFS)	Graphknoten Ebene für Ebene durchlaufen; eine Warteschlange wird benötigt, um die "noch zu besuchenden" Knoten zu speichern
Aufgabenplanung im Betriebssystem	Die CPU weist Zeitscheiben in der Reihenfolge zu, in der Aufgaben eintreffen
Druckaufgaben-Warteschlange	Mehrere Computer teilen sich einen Drucker; Druckaufträge werden in der Reihenfolge ihrer Übermittlung in eine Warteschlange eingereiht und verarbeitet
Nachrichtenwarteschlange	In verteilten Systemen werden von Produzenten erzeugte Nachrichten über eine Warteschlange an Konsumenten weitergegeben

Andere Erweiterungen