Eine Warteschlange (oder Queue) ist eine spezielle Datenstruktur, mit der beliebige Daten verwaltet werden können.
Auf einer Warteschlange sind zwei Operationen definiert:
- dequeue
- Einen Wert aus der Warteschlange entfernen.
- enqueue
- Einen Wert in die Warteschlange einfügen.
Daten werden immer am Ende eingefügt und am Anfang entnommen, daher ist die Warteschlange ein sogenannter FIFO-Speicher (First In First Out). Dies ist in der nebenstehenden Abbildung dargestellt.
Inhaltsverzeichnis
- 1 Implementation
- 1.1 Implementation mit Verkettung
- 1.2 Implementation mit einem Feld
- 2 Anwendungsbeispiel
Implementation
Bearbeiten
Eine Warteschlange kann auf verschiedene Arten implementiert werden, von denen im Folgenden zwei besprochen werden sollen.
Hierfür sei zunächst die folgende Schnittstelle vereinbart:
#define SUCCESS 0#define ERR_INVAL 1#define ERR_NOMEM 2#define FALSE 0#define TRUE 1typedef struct queue_s queue_t;int queue_destroy(queue_t *queue);int queue_empty(queue_t *queue);queue_t *queue_new(void);void *queue_dequeue(queue_t *queue);int queue_enqueue(queue_t *queue, void *data);
Implementation mit Verkettung
Bearbeiten
Zunächst soll eine Implementation besprochen werden, die auf einer einfach verketteten Liste basiert. Diese Implementation hat den Vorteil, dass die Größeder Warteschlange stets mit der Anzahl der Elemente, die in der Warteschlange liegen, übereinstimmt. Nachteilig ist, dass der Speicherverbrauch hochist, da für jedes einzelne Element eine Struktur benötigt wird, die neben dem Zeiger auf die Daten auch einen Zeiger auf das nächste Element speichert. Außerdem ist das Einfügen und Auslesen von Elementen nicht in konstanter Zeit möglich, da hierbei stets Speicheroperationen ausgeführt werden.
Diese Implementation verwendet die folgenden Datenstrukturen:
struct queue_node_s { struct queue_node_s *next; void *data;};struct queue_s { struct queue_node_s *front; struct queue_node_s *back;};
Damit lassen sich die Funktionen folgendermaßen implementieren:
int queue_destroy(queue_t *queue) { if (queue == NULL) { return ERR_INVAL; } while (queue->front != NULL) { struct queue_node_s *node = queue->front; queue->front = node->next; free(node); } free(queue); return SUCCESS;}int queue_empty(queue_t *queue) { if (queue == NULL || queue->front == NULL) { return TRUE; } else { return FALSE; }}queue_t *queue_new(void) { queue_t *queue = malloc(sizeof(*queue)); if (queue == NULL) { return NULL; } queue->front = queue->back = NULL; return queue;}void *queue_dequeue(queue_t *queue) { if (queue == NULL || queue->front == NULL) { return NULL; } struct queue_node_s *node = queue->front; void *data = node->data; queue->front = node->next; if (queue->front == NULL) { queue->back = NULL; } free(node); return data;}int queue_enqueue(queue_t *queue, void *data) { if (queue == NULL) { return ERR_INVAL; } struct queue_node_s *node = malloc(sizeof(*node)); if (node == NULL) { return ERR_NOMEM; } node->data = data; node->next = NULL; if (queue->back == NULL) { queue->front = queue->back = node; } else { queue->back->next = node; queue->back = node; } return SUCCESS;}
Implementation mit einem Feld
Bearbeiten
Außerdem soll eine Implementation besprochen werden, die ein Feld für die Datenspeicherung verwendet. Dieses hat im Gegensatz zu der oben besprochenenImplementation den Vorteil, dass der Speicherverbrauch für ein einzelnes Element geringer ist, da kein Zeiger auf das nachfolgende Element notwendig ist.Außerdem ist der Zugriff auf die Elemente in konstanter Zeit möglich, solange keine Speicheroperationen durchgeführt werden müssen. Diese Vorteile setzenallerdings voraus, dass die Parameter
- QUEUE_GROW_SIZE
- Anzahl von Speicherplätzen, um die die Warteschlange bei Größenänderung wachsen soll. Die Implementation ist so angelegt, dass beim Verkleinern der Warteschlange die Anzahl der verfügbaren Speicherplätze ein ganzzahliges Vielfaches dieser Größe ist.
- QUEUE_INIT_SIZE
- Initiale Anzahl von Speicherplätzen.
- QUEUE_SHRINK_AT
- Die Anzahl freier Speicherplätze, die mindestens vorhanden sein müssen, um die Warteschlange zu verkleinern.
für das Problem geeignet gewählt werden, insbesondere ist bei der vorliegenden Implementation der Speicherverbrauch (ohne Berücksichtigung derVerwaltungsstrukturen des Betriebssystems) nur dann geringer, wenn die Anzahl der Elemente in der Warteschlange mindestens die Hälfte der möglichen Elementeist (d.h. bei einer Warteschlange, der zehn Elemente ohne Speicheroperationen aufnehmen kann, müssen mindestens fünf Elemente in der Warteschlange liegen).
Diese Implementation verwendet die folgenden Datenstrukturen:
struct queue_s { void **data; size_t front; size_t back; size_t size;};
Damit lassen sich die Funktionen folgendermaßen implementieren:
int queue_destroy(queue_t *queue) { if (queue == NULL) { return ERR_INVAL; } free(queue->data); free(queue); return SUCCESS;}int queue_empty(queue_t *queue) { if (queue == NULL || queue->front == queue->back) { return TRUE; } else { return FALSE; }}queue_t *queue_new(void) { queue_t *queue = malloc(sizeof(*queue)); if (queue == NULL) { return NULL; } if ((queue->data = malloc(QUEUE_INIT_SIZE*sizeof(*(queue->data)))) == NULL) { free(queue); return NULL; } queue->front = queue->back = 0; queue->size = QUEUE_INIT_SIZE; return queue;}void *queue_dequeue(queue_t *queue) { if (queue == NULL || queue->front == queue->back) { return NULL; } void *data = queue->data[queue->front]; queue->front = (queue->front + 1)%queue->size; size_t len = ((queue->back<queue->front)?(queue->back+queue->size):queue->back)-queue->front; if (queue->size > QUEUE_SHRINK_AT && len <= queue->size - QUEUE_SHRINK_AT) { size_t new_size = len+((len + QUEUE_GROW_SIZE)%QUEUE_GROW_SIZE); if (queue->front < queue->back) { if (queue->back > new_size) {size_t off = queue->back - new_size;memcpy(queue->data, queue->data+new_size, off*sizeof(*(queue->data)));if (queue->front > new_size) { queue->front = off - len;}queue->back = off; } else if (queue->back == new_size) {queue->back = 0; } } else { size_t off = queue->size - queue->front; memmove(queue->data+(new_size - off), queue->data+queue->front, off*sizeof(*(queue->data))); queue->front = new_size - off; } queue->data = realloc(queue->data, new_size*sizeof(*(queue->data))); queue->size = new_size; } return data;}int queue_enqueue(queue_t *queue, void *data) { if (queue == NULL) { return ERR_INVAL; } queue->data[queue->back] = data; queue->back = (queue->back + 1)%queue->size; if (queue->back == queue->front) { size_t new_size = queue->size + QUEUE_GROW_SIZE; void **new_data = realloc(queue->data, new_size*sizeof(*(queue->data))); if (new_data == NULL) { queue->back = (queue->size + queue->back - 1) % queue->size; return ERR_NOMEM; } if (queue->back != 0) { if (queue->back < QUEUE_GROW_SIZE) {memcpy(queue->data+queue->size, queue->data, queue->back*sizeof(*(queue->data)));queue->back += queue->size-1; } else {size_t rem = queue->back - QUEUE_GROW_SIZE;memcpy(queue->data+queue->size, queue->data, QUEUE_GROW_SIZE*sizeof(*(queue->data)));memcpy(queue->data, queue->data+QUEUE_GROW_SIZE, rem*sizeof(*(queue->data)));queue->back = rem; } } else { queue->back = queue->size; } queue->data = new_data; queue->size = new_size; } return SUCCESS;}
Anwendungsbeispiel
Bearbeiten
Als Anwendungsbeispiel sei hier eine iterative Breitensuche in einem Binärbaum behandelt (siehe dortfür die Definition von knoten):
void bfs(knoten *tree, void (*f)(int, void *), void *user) { if (tree == NULL) { return; } queue_t *queue = queue_new(); queue_enqueue(queue, tree); while (!queue_empty(queue)) { knoten *k = queue_dequeue(queue); if (k->links != NULL) { queue_enqueue(queue, k->links); } if (k->rechts != NULL) { queue_enqueue(queue, k->rechts); } (*f)(k->wert, user); } queue_destroy(queue);}
Hierbei ist f eine Funktion, die auf jedem Knoten ausgeführt werden soll, z.B.
void print(int n, void *user) { if (*((int *)user)) { *((int *)user) = 0; } else { printf(", "); } printf("%d", n);}
um die Knotenwerte auszugeben.
