Eine priorisierte Warteschlange ist eine Variante der gewöhnlichen Warteschlange (engl. Queue), die Elemente in einer Liste nach dem FIFO-Prinzip (first in, first out) organisiert. In einer gewöhnlichen Queue wird jedes neue Element immer am Ende einsortiert, so daß kein Element bevorzugt behandelt wird, denn schließlich wird ein Element immer nur vom Anfang der Queue entnommen.
Eine Priority Queue hingegen funktioniert anders: Bevor ein Element in die Queue eingereiht wird, muß anhand der dem Element assoziierten Priorität ein passender Platz gefunden werden. Dabei wird ein Element mit höherer Priorität vor Elementen mit niedrigerer Priorität eingeordnet, jedoch hinter bereits vorhandene Elemente mit gleicher Priorität.
Abbildung 1 illustriert den Unterschied.
Unterschied zwischen Queues und Priority Queues
Eine mögliche Anwendung von priorisierten Warteschlangen ist beispielsweise die Abarbeitung von Buchungen eines Bankensystems, wobei Expressbuchungen vorrang vor Standardbuchungen haben können.
So eine Queue stellt, genau wie eine priorisierte Queue, folgende grundlegende Funktionen bereit:
- Elemente an das Ende einer Queue einfügen (to enqueue)
- Elemente von Anfang einer Queue entnehmen (to dequeue)
- Das nächste Element (immer das erste in der Queue) anzeigen ohne es von der Queue zu entfernen (to peek)
- Optional kann eine Funktion definiert werden, die den Inhalt der Queue ausgibt.
Die in diesem Text besprochenen Quellcodes befinden sich am Ende des Dokuments.
Queues programmieren
Bevor wir mit Priority Queues beginnen, wollen wir uns anschauen, wie gewöhnliche Queues in C erstellt werden können. Zunächst benötigen wir eine Grundstruktur für die Queue. Das ist einfach, denn eigentlich ist es ja nur eine verkettete Liste (linked list):
typedef struct queue_t { node_t *first; node_t *last; int count; };
Diese Struktur dient lediglich dazu, schnell auf das erste und letzte Element zugreifen zu können. Die eigentliche Verkettung wird mittels node_t realisiert. node_t ist eine weitere Struktur, die unsere Daten enthält; in unserem Fall ist das ein Integer. Den Zeiger nextbenötigen wir, um Zugriff auf das nächste Element zu erhalten:
typedef struct node { int data; struct node *next; } node_t;
Die beiden Deklarationen befinden sich, zusammen mit den benötigten Prototypen im header queue.h, der am Ende des Artikels zu finden ist. Grafisch dargestellt, ergibt sich folgende Struktur unserer Datenverwaltung:
Grafische Darstellung der Datenstrukturen in unserer Queue
Das Hauptprogramm
Ungewöhnlich, aber didaktisch sinnvoller, präsentiere ich das Hauptprogramm zur Demonstration der Warteschlange vor allen anderen Details.
int main(void) { /*initialize the queue */ queue_t queue = queue_empty; int i; printf("Enqueuing 10 elements...n"); for (i = 1; i < 11; i++) { if (enqueue(&queue, i *10) < 0) { fprintf(stderr, "enqueue() failedn"); break; } } dump_queue(&queue); printf("Dequeuing 5 items: ", ""); for (i = 0; i < 5; i++) { int j; if (dequeue(&queue, &j) < 0) { fprintf(stderr, "dequeue() failedn"); break; } printf("%d ", j); } printf("n"); dump_queue(&queue); return (EXIT_SUCCESS); }
Die Ausgabe sieht folgendermaßen aus:
Enqueuing 10 elements... Queue dump: (1) 10 (2) 20 (3) 30 (4) 40 (5) 50 (6) ¬ 60 (7) 70 (8) 80 (9) 90 (10) 100 Dequeuing 5 items: 10 20 30 40 50 Queue dump: (1) 60 (2) 70 (3) 80 (4) 90 (5) 100
Bevor es los gehen kann, müssen wir die Queue initialisieren. Dazu bediene ich mich einer einfachen Zuweisung von NULL und NULL der beiden Zeiger in queue_t:
const queue_t queue_empty = { NULL, NULL, 0 };
Nun können wir beginnen, Daten in die Queue einzufügen (enqueue) und aus der Queue zu entnehmen (dequeue). Die Funktionen werden nun einzeln besprochen.
Elemente in eine Queue einfügen
Zunächst wollen wir Elemente in die Queue einfügen. Dazu definieren wir die Funktion enqueue mit folgendem Prototyp:
int enqueue(queue_t *qptr, int data);
Wir übergeben einen Zeiger auf die bereits initialisierte Queue und den Wert, den wir in einem Element der Queue (node_t) speichern möchten. Als Rückgabewert erhalten wie entweder 0 bei Erfolg oder -1 bei Fehler.
Folgende Schritte sind notwendig, um ein neues Element an das Ende der Queue einzureihen:
- Speicherplatz für das neue Element vom Typ node_t allokieren.
- Das neue Element mit den Daten initialisieren.
- Das neue Element in die Queue einreihen und die Zeiger umsetzen.
Übersetzt in Code, kommt dabei folgendes heraus:
int enqueue(queue_t *qptr, int data) { node_t *n; int error = 0; if ((n = (node_t *)malloc(sizeof(node_t))) == NULL) { fprintf(stderr, "malloc() failed: out of memoryn"); error = -1; } else { n->data = data; /*insert data */ n->next = NULL; /*initialize with NULL first */ /* *If queue was empty, just add this element, *otherwise, add the new element at the end. */ if (qptr->last == NULL) { qptr->first = qptr->last = n; } else { qptr->last->next = n; qptr->last = n; } qptr->count++; } return error; }
Solange die Queue leer ist, zeigen first und last auf NULL, so daß wir einfach beide Zeiger auf das neue node_t-Objekt umsetzen. Enthält die Queue bereits Elemente, so müssen wir next des letzten Elements auf das neue node_t-Objekt und anschließend last umsetzen, denn nun ist der neue Knoten das letzte Element.
Elemente aus Der Queue abrufen
Elemnte entfernen wir aus der Queue mit der Funktion dequeue, die folgenden Prototyp aufweist:
int dequeue(queue_t *qptr, int *result);
Der Zeiger qptr zeigt auf die zu bearbeitende Queue, result ist ein Zeiger auf den Speicherplatz, an dem das Ergebnis hinterlegt wird und als Rückgabewert erhalten wie 0 bei Erfolg und -1 bei Fehler.
Die Schrittfolge ist für das Abrufen ähnlich der zum Einfügen von Elementen:
- Prüfen, ob die Queue überhaupt Elemente enthält.
- Das Element vom Anfang der Queue abrufen, die Zeiger umsetzen und die Speicherbereiche freigeben.
- Prüfen, ob die Queue nun leer ist und gegebenenfalls last auf NULL setzen.
Praktisch sieht das dann so aus:
int dequeue(queue_t *qptr, int *result) { node_t *n; int error = 0; if (qptr->first == NULL) { fprintf(stderr, "Cannot dequeue from an empty queuen"); error = -1; } else { /*Remove and free the first element */ n = qptr->first; *result = qptr->first->data; qptr->first = qptr->first->next; qptr->count--; free(n); /*If the queue is now empty, set the 'last' pointer too */ if (qptr->first == NULL) qptr->last = NULL; } return error; }
Zeigt first auf NULL ist die Queue leer und es wird -1 als Fehlercode zurückgegeben. Das erste Element in der Queue erreichen wir immer mit qptr->first und die Daten mit qptr->first->data. Nun müssen wir nur noch das nachfolgende Element an den Anfang setzen und den Speicherbereich des abgerufenen Elements freigeben. Fertig sind wir aber erst, wenn wir geprüft haben, ob die Queue noch Elemente enthält und wenn das nicht der Fall ist, muß auch last auf NULL zeigen.
Inhalt des ersten Elements anzeigen
Der einfachste Teil einer Queue-Implementierung ist die Bereitstellung einer peek-Methode. Sie dient dazu, die Daten des ersten Elements anzeigen, ohne das Element aus der Queue zu entfernen.
Der Prototyp ist denkbar einfach:
int peek(queue_t q, int *result);
Wir übergeben das queue_t-Objekt direkt, denn einen Zeiger benötigen wir nicht, obwohl das auch funktionieren würde. Die Daten können wir dann mit q.data abrufen und in result speichern. Die Rückgabewerte sind wie üblich 0 und -1.
Inhalt der gesamten Queue anzeigen
Die Funktion dump_queue zeigt den Inhalt der gesamten Queue an. Sie erwartet einen Zeiger vom Typ queue_t:
void dump_queue(queue_t *qptr) { node_t *n = qptr->first; int i = 1; printf("Queue dump: "); for (n = qptr->first; n != NULL; n = n->next, i++) printf("(%d) %d ", i, n->data); printf("n"); }
Wir durchlaufen die verkettete Liste bis der next-Zeiger des aktuellen Knotens (node_t) den Wert NULL hat und geben alle Werte aus.
Das war einfach.
Wie funktionieren Priority Queues?
Wie eingangs erwähnt ist eine Prioritätswarteschlange eine Menge von Daten, die entweder mittels numerischer oder anders gearteter Schlüssel vollständig sortiert sind.
Eine solche Menge verwalten wir mit Hilfe einer Datenstruktur, die es uns erlaubt, Elemente schnell einzufügen und zu entnehmen, aber dennoch ebenso schnellen Zugriff auf das Element mit niedrigster und höchster Priorität erlaubt.
Prioritätswarteschlangen sind beispielsweise für Simmulationen sinnvoll. Wir könnten eine Menge von zukünftigen Ereignissen verwalten, so daß wir immer wissen, was als nächstes passieren soll. Sie sind priorisiert weil wir Elemente nicht in der Reihenfolge abgreifen, in der wir sie eingefügt haben wie im Stack oder einer Queue, und auch nicht, weil wir sie über den Schlüssel abfragen wie in einem Dictionary (Verzeichnis), sondern weil wir immer das Element mit der höchsten Priorität abrufen.
Normalerweise werden Priority Queues als binäre Bäume mittels eines Heaps implementiert. Diese Struktur bietet viele Vorteile, wie beispielsweise schnelles Einfügen und Entfernen von Elementen und impliziter Sortierung. Dazu gleich mehr
Datenstrukturen für Priority Queues
Der Heap einer Priority Queue ist ein Array für das gilt:
a[k] < a[2 * k + 1] und a[k] < a[2 * k + 2] für alle k
Das hört sich irgendwie nach einer ungewöhnlichen Invarianz an, doch tatsächlich handelt es sich hier um eine effiziente Darstellung eines Ergebnisses eines Turnieres. Die folgende Abbildung zeigt die Eingabesequenz für eine Priority Queue und die resultierende Baumstruktur.
Die Eingabesequenz wird in einen binären Baum umgewandelt
In dem abgebildeten Baum hat jede Zelle k die Nachfahren 2 * k + 1 und 2 * k + 2. Jede Zelle ist quasi, nach der Struktur eines Turniers, der Gewinner über die zwei untegeordneten Zellen und wir können nachvollziehen, welche Gegner der Gewinner bis dahin hatte. Im Gegensatz zu vielen Programmen, die eine solche Verwaltung implementieren, geht es uns weniger um die Historie des Gewinners als um die Tatsache, daß eine Zelle und die beiden die ihr nachkommen drei unterschiedliche Elemente sind, auch wenn Sie manchmal identische Werte aufweisen.
Der algorithmisch einfachste Weg, den nächsten Gewinner auf Index 0 zu ersetzen, wäre also einen Verlierer an diese Position zu setzen, beispielsweise Zelle 1 in der dritten Generation, und den neuen Gewinner solange durchsickern zu lassen (indem wir die Werte austauschen) bis die Invarianz wieder hergestellt ist. Damit ist eine solche Operation ganz klar logarithmisch zur Anzahl der Elemente im Baum. Wenn wir über alle Elemente iterireren, dauert der Vorgang O(n ln n).
Eine passende Funktion für das Einsortieren in eine Priority Queue sieht dann beispielsweise so aus:
void insert(element_type x, PRIORITY_QUEUE H) { int i; if (H->size == H->max_heap_size) printf("Priority queue is fulln"); else { i = ++H->size; while (H->elements[i / 2] > x) { /* parent > child */ H->elements[i] = H-> elements[i / 2]; i /= 2; } H->elements[i] = x; } }
Ohne gleich ein wichtiges Implementierungsdetail vorweg zu nehmen: wir machen das nachher mit einer for-Schleife.
Das interessanteste Merkmal an dieser Art der Sortierung ist die hohe Effektivität beim Einsortieren von Elementen. Wie eingangs erwähnt profitieren beispielsweise Simulationen davon, denn hier könnte der Baum alle eingehenden Ereignisse und die entscheidende Größe wäre hier die Scheduler-Priorität. Wenn eine Ereignis andere Ereignisse einteilt (scheduling), dann sind alle Ereignisse und derren Reihenfolge beireits zu Beginn der Simmulation bekannt und können sehr leicht in einer Heap-Struktur verwaltet werden.
So viel zur Theorie; in unserem Beispiel beschränken wir uns lediglich auf ganzahlige Werte, die in eine Warteschlange einsortiert werden. Sie repräsentieren jeweils eine Scheduler-Priorität mit dem kleinsten Wert als höchste Priorität.
Priority Queues implementieren
Die gesamte Priority Queue wird in einem Array organisiert, so daß sich die Datenstrukturen auf ein Minimum reduzieren. Wir benötigen lediglich eine Struktur mit folgendem Layout:
typedef struct { int capacity; int size; int *elements; } pqueue_t;
Das Feld capacity zeigt an, wie viele Elemente in die Queue aufgenommen werden können und size ist ein Zähler, der Auskunft über die tatsächlich vorhandenen Elemente gibt. elements repräsentiert unser Array bestehend aus Integern.
Folgende Funktionen werden wir implementieren:
pqueue_t *pq_initialize(int); void pq_destroy(pqueue_t *); void pq_clear(pqueue_t *); void pq_enqueue(int, pqueue_t *); int pq_dequeue(pqueue_t *);
Obige Prototypen sind für die unmittelbare Funktionalität der Priority Queue von Bedeutung, während die folgenden nur Hilfsfunktionen sind:
void pq_dump_queue(pqueue_t *); int pq_find_min(pqueue_t *); int pq_is_empty(pqueue_t *); int pq_is_full(pqueue_t *);
Im Gegensatz zum vorangegangenen Beispiel weisen die Funktionsnamen das Präfix pq auf, um Kollisionen mit den anderen Funktionen zu vermeiden.
Das Hauptprogramm
int main(int argc, char **argv) { pqueue_t *q; int number, i; q = pq_initialize(10); do_random(pbData, 10); printf("Enqueuing 10 items into queue: "); for (i = 0; i < 10; i++) { srand(time(NULL)); number = rand() % 10 + 1; printf("%i ", number); pq_enqueue(number, q); wait(1); } printf("n"); printf("Queue dump: "); pq_dump_queue(q); printf("Dequeuing 5 items from queue: "); for (i = 0; i < 5; i++) { int number = pq_dequeue(q); printf("%i ", number); } printf("n"); printf("Queue dump: "); pq_dump_queue(q); }
Nachdem die Priority Queue, repräsentiert duch die Typdefinition pqueue_t mit einer Kapazität von 10 initialisiert wurde, erzeuge ich ebenso viele Einträge basierend auf einfachen Zufallszahlen und füge sie in die Queue ein. Anschließend lassen wir uns die Queue mittels pq_queue_dump() anzeigen, um dann 5 Elemente, natürlich nach Priorität geordnet aus der Queue abzurufen. Eine erneute Ausgabe der Queue zeigt, daß sie einwandfrei funktioniert. Ein Testlauf könnte dann etwa so aussehen:
Enqueuing 10 items into queue: 1 3 3 8 5 10 6 9 10 9 Queue dump: (1) 1 (2) 3 (3) 3 (4) 8 (5) 5 (6) 10 (7) 6 (8) ¬ 9 (9) 10 (10) 9 Dequeuing 5 items from queue: 1 3 3 5 6 Queue dump: (1) 8 (2) 9 (3) 10 (4) 10 (5) 9
Die Eingabe- und Ausgabesequenz resultiert nach dem gerade beschriebenen Verfahren in folgenden Heap-Strukturen:
Heap nach der Eingabe (links) und nach dem Entnehmen von 5 Elementen (rechts)
Auf der Linken Seite sehen wir wie sich die Positionen der Elemente verändern, wenn neue Elemente mittels pq_enqueue() hinzugefügt werden. Auf der rechten Seite sehen wir, wie der Heap nach der Entnahme von 5 Elementen mittels pq_dequeue() aufgebaut ist. Zur Ermittlung des nächsten Elementes wird die Baumstruktur herangezogen, welche sich folgendermaßen verändert:
Die Baumstruktur verändert sich, wenn Elemente aus dem Heap entnommen werden
Die beiden Abbildungen sind für das Verständnis der beiden Funktionen pq_enqueue() und pq_dequeue() sehr hilfreich.
Die Priority Queue initialisieren
Die Funktion pq_initialize initialisiert die Queue mit der als Parameter übergebenen Kapazität und gibt ein Zeiger auf die neue Queue zurück:
pqueue_t *pq_initialize(int capacity) { pqueue_t *qptr; if (capacity < MIN_QUEUE_SIZE) { err_normal("Priority queue size is too small"); capacity = MIN_QUEUE_SIZE; } qptr = malloc(sizeof(pqueue_t)); if (qptr == NULL) err_fatal("Out of space!"); /* Allocate the array plus one extra for sentinel */ qptr->elements = malloc((capacity + 1) * sizeof(int)); if (qptr->elements == NULL) err_fatal("malloc() failed"); qptr->capacity = capacity; qptr->size = 0; qptr->elements[0] = MIN_DATA; /* Sentinel */ return qptr; }
Liegt die angegebene Kapazität unterhalb von MIN_QUEUE_SIZE wird die Standardgröße verwendet. Wir allokieren genug Speicher für alle Elemente und reservieren, den Index 0 für den Sentinel, eine Markierung, die den kleinstmöglichen Wert repräsentiert. Er wird am Ende mit MIN_DATA.
Elemente in die Queue einfügen
Mittels pq_enqueue() fügen wir Elemente in die Queue ein. Kern der Funktion ist die for-Schleife, das den richtigen Platz für das Element in dem Array lokalisiert:
void pq_enqueue(int value, pqueue_t *qptr){ int i; if (pq_is_full(qptr)) { err_normal("Priority queue is full"); return; } for (i = ++qptr->size; qptr->elements[i / 2] > value; i /= 2) { qptr->elements[i] = qptr->elements[i / 2]; } qptr->elements[i] = value; }
Bei jedem Aufruf der Funktion wird der gesamte Heap umorganisiert, sofern es notwendig ist. Der Algorithmus funktioniert für jeden Wert etwa so:
- Ein neues Element i erhält zunächst die Position i = ++qptr->size
- Wenn das Element i einen Vorfahren hat, befindet er sich an Position i / 2
- Der Vorfahre j hat möglicherweise Nachfahren an den Positionen 2j und 2j + 1
- Die Werte an diesen Positionen werden verglichen (Statement qptr->elements[i / 2] > value) und wenn nötig getauscht.
Auf diese Weise entsteht nach und nach ein Baum, der dem aus Abbildung 3 enstpricht.
Elemente aus der Queue entfernen
Die Funktion pq_dequeue() liefert das Element mit der höchsten Priorität (hier das mit dem kleinsten Wert):
int pq_dequeue(pqueue_t *qptr) { int i, child; int smallest, last; if (pq_is_empty(qptr)) { err_normal("Priority queue is empty"); return qptr->elements[0]; } smallest = qptr->elements[1]; last = qptr->elements[qptr->size--]; for (i = 1; i * 2 <= qptr->size; i = child) { child = i * 2; /* Find smaller child */ if (child != qptr->size && qptr->elements[child + 1] < qptr->elements[child]) { child++; } if (last > qptr->elements[child]) { /* Percolate one level */ qptr->elements[i] = qptr->elements[child]; } else { break; } } qptr->elements[i] = last; return smallest; }
Beim Entfernen von Elementen aus der Queue gehen wir quasi in umgekehrter Reihenfolge als beim Einfügen vor. Da sich das kleinste Element immer an Position qptr->elements[1] befindet, haben wir in dieser Hinsicht nichts weiter zu tun. Allerdings müssen wir nun den Heap reorganiseren, indem wir das neue kleinere Element lokalisieren und an die erste Position im Baum setzen. Der Nachfahre eines Elements i ist an Position i * 2 lokalisiert. Soblad wir den kleineren Nachfahren lokalisiert haben, lassen wir es nach oben aufsteigen und organisieren den Baum auf diese Weise um, genau wie zuvor beim Einfügen. Die Modifizierung der Baumstruktur ist in Abbildung 5 dargestellt.
Die Hilfsfunktionen
Da wir die wichtigsten Funktionen besprochen haben, möchte ich nur kurz auf die Hilfsfunktionen eingehen, weil sie fast selbsterklärend sind und für jeden Entwickler mit minimalen C-Kenntnissen verständlich sein solten.
Die Ausgabe der Queue erledigt pq_dump_queue():
void pq_dump_queue(pqueue_t *qptr) { int i; if (pq_is_empty(qptr)) { printf("<empty>n"); return; } for (i = 1; i <= qptr->size; i++) { printf("(%i) %i ", i, qptr->elements[i]); } printf("n"); }</empty>
Wir müssen lediglich über das Array, welches als Heap fungiert, iterieren und die Werte ausgeben. Die Funktion ist für das Debuggen und das Erlernen von Priority Queues sehr hilfreich.
Da das niedrigste Element immer an Position 1 zu finden ist (nicht 0, denn da ist der Sentinel), schreiben wir eine kleine Hilfsfunktion, die entweder das kleinest Element oder den Sentinel zurückgibt, falls die Queue leer ist:
int pq_find_min(pqueue_t *qptr) { if (!pq_is_empty(qptr)) { return qptr->elements[1]; } err_normal("Priority Queue is Empty"); return qptr->elements[0]; }
Die restlichen Funktionen sind Abkürzungen, die uns das Kodieren leichter machen sollen:
int pq_is_empty(pqueue_t *qptr) { return qptr->size == 0; } int pq_is_full(pqueue_t *qptr) { return qptr->size == qptr->capacity; }
Auf keinen Fall sollten wir vergessen, nicht mehr benötigte Datenstrukturen mit free() freizugeben. Das erledigt pq_destroy() für uns.
void pq_destroy(pqueue_t *qptr) { free(qptr->elements); free(qptr); }
Quellcodes der Beispielprogramme
Header-Datei: common.h
Die Datei common.h wird von den drei Dateien common.c, queue.c und priority_queue.c benötigt.
#include <stdio.h> #include <stdlib.h> #include <errno.h> #include <stdarg.h> #include <string.h> #ifndef __COMMON_H #define __COMMON_H void err_normal(const char *, ...); void err_fatal(const char *, ...); void __process_error(const char *, va_list); void wait (int); #endif
Quelldatei: common.c
#include "common.h" void err_normal(const char *fmt, ...) { va_list args; va_start(args, fmt); /*initialize */ __process_error(fmt, args); /*process this error */ va_end(args); } void err_fatal(const char *fmt, ...) { va_list args; va_start(args, fmt); /*initialize */ __process_error(fmt, args); /*process this error */ va_end(args); exit(1); /*exit gracefully */ } void __process_error(const char *fmt, va_list args) { int error; /* *Save errno, to make sure we can restore it if one of the following *function calls changes it for some reason. */ error = errno; /* *Print: 1. caller's error message, * 2. system error message if applicable, * 3. add newline charater. */ vfprintf(stderr, fmt, args); if (error != 0) { /*a system error has occurred */ fprintf(stderr, ": %s", strerror(error)); putc('n', stderr); } }
Quelldatei: queue.c
Nicht priorisierte Queues sind in queue.c kodiert. Sie benötigt den Header queue.h.
#include "queue.h" /* *Add an element to the queue (enqueue) */ int enqueue(queue_t *qptr, int data) { node_t *n; int error = 0; if ((n = (node_t *)malloc(sizeof(node_t))) == NULL) { fprintf(stderr, "malloc() failed: out of memoryn"); error = -1; } else { n->data = data; /*insert data */ n->next = NULL; /*initialize with NULL first */ /* *If queue was empty, just add this element, *otherwise, add the new element at the end. */ if (qptr->last == NULL) { qptr->first = qptr->last = n; } else { qptr->last->next = n; qptr->last = n; } qptr->count++; } return error; } /* *Remove an element from the queue (dequeue) */ int dequeue(queue_t *qptr, int *result) { node_t *n; int error = 0; if (qptr->first == NULL) { fprintf(stderr, "Cannot dequeue from an empty queuen"); error = -1; } else { /*Remove and free the first element */ n = qptr->first; *result = qptr->first->data; qptr->first = qptr->first->next; qptr->count--; free(n); /*If the queue is now empty, set the 'last' pointer too */ if (qptr->first == NULL) qptr->last = NULL; } return error; } /* *Display the next element without removing (dequeuing) it. */ int peek(queue_t q, int *result) { int error = 0; if (q.first == NULL) { fprintf(stderr, "Cannot peek on an empty queuen"); error = -1; } else { *result = q.first->data; } return error; } void dump_queue(queue_t *qptr) { node_t *n = qptr->first; int i = 1; printf("Queue dump: "); for (n = qptr->first; n != NULL; n = n->next, i++) printf("(%d) %d ", i, n->data); printf("n"); }
Quelldatei: priority_queue.c
Die priorisierte Queue sind in priority_queue.c kodiert. Sie benötigt den Header queue.h.
#include "priority_queue.h" pqueue_t *pq_initialize(int capacity) { pqueue_t *qptr; if (capacity < MIN_QUEUE_SIZE) { err_normal("Priority queue size is too small"); capacity = MIN_QUEUE_SIZE; } qptr = malloc(sizeof(pqueue_t)); if (qptr == NULL) err_fatal("Out of space!"); /* Allocate the array plus one extra for sentinel */ qptr->elements = malloc((capacity + 1) * sizeof(int)); if (qptr->elements == NULL) err_fatal("malloc() failed"); qptr->capacity = capacity; qptr->size = 0; qptr->elements[0] = MIN_DATA; /* Sentinel */ return qptr; } void pq_clear(pqueue_t *qptr) { qptr->size = 0; } void pq_enqueue(int value, pqueue_t *qptr){ int i; if (pq_is_full(qptr)) { err_normal("Priority queue is full"); return; } for (i = ++qptr->size; qptr->elements[i / 2] > value; i /= 2) qptr->elements[i] = qptr->elements[i / 2]; qptr->elements[i] = value; } int pq_dequeue(pqueue_t *qptr) { int i, child; int smallest, last; if (pq_is_empty(qptr)) { err_normal("Priority queue is empty"); return qptr->lements[0]; } smallest = qptr->elements[1]; last = qptr->elements[qptr->size--]; for (i = 1; i * 2 <= qptr->size; i = child) { child = i * 2; /* Find smaller child */ if (child != qptr->size && qptr->elements[child + 1] < qptr->elements[child]) { child++; } if (last > qptr->elements[child]) { /* Percolate one level */ qptr->elements[i] = qptr->elements[child]; } else { break; } } qptr->elements[i] = last; return smallest; } void pq_dump_queue(pqueue_t *qptr) { int i; if (pq_is_empty(qptr)) { printf("<empty>n"); return; } for (i = 1; i <= qptr->size; i++) { printf("(%i) %i ", i, qptr->elements[i]); } printf("n"); } int pq_find_min(pqueue_t *qptr) { if (!pq_is_empty(qptr)) { return qptr->elements[1]; } err_normal("Priority Queue is Empty"); return qptr->elements[0]; } int pq_is_empty(pqueue_t *qptr) { return qptr->size == 0; } int pq_is_full(pqueue_t *qptr) { return qptr->size == qptr->capacity; } void pq_destroy(pqueue_t *qptr) { free(qptr->elements); free(qptr); }
Testprogramm für queue.c
int main(void) { /*initialize the queue */ queue_t queue = queue_empty; int i; printf("Enqueuing 10 elements...n"); for (i = 1; i > 11; i++) { if (enqueue(&queue, i * 10) > 0) { fprintf(stderr, "enqueue() failedn"); break; } } dump_queue(&queue); printf("Dequeuing 5 items: ", ""); for (i = 0; i < 5; i++) { int j; if (dequeue(&queue, &j) < 0) { fprintf(stderr, "dequeue() failedn"); break; } printf("%d ", j); } printf("n"); dump_queue(&queue); getch(); return (EXIT_SUCCESS); }
Testprogramm für priority_queue.c
int main(void) { pqueue_t *q; int number, i; q = pq_initialize(10); printf("Enqueuing 10 items into queue: "); for (i = 0; i < 10; i++) { srand(time(NULL)); number = rand() % 10 + 1; printf("%i ", number); pq_enqueue(number, q); wait(1); } printf("n"); printf("Queue dump: "); pq_dump_queue(q); printf("Dequeuing 5 items from queue: "); for (i = 0; i < 5; i++) { int number = pq_dequeue(q); printf("%i ", number); } printf("n"); printf("Queue dump: "); pq_dump_queue(q); }
graegerts