Algorithmen und Datenstrukturen in C/ Warteschlange

Eine Warteschlange (oder Queue) ist eine spezielle Datenstruktur, mit der beliebige Daten verwaltet werden können.

Funktionsweise der grundlegenden Warteschlangenoperationen dequeue und enqueue.

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.

Implementation

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 1

typedef 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

Zunächst soll eine Implementation besprochen werden, die auf einer einfach verketteten Liste basiert. Diese Implementation hat den Vorteil, dass die Größe der Warteschlange stets mit der Anzahl der Elemente, die in der Warteschlange liegen, übereinstimmt. Nachteilig ist, dass der Speicherverbrauch hoch ist, 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

Außerdem soll eine Implementation besprochen werden, die ein Feld für die Datenspeicherung verwendet. Dieses hat im Gegensatz zu der oben besprochenen Implementation 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 setzen allerdings 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 der Verwaltungsstrukturen des Betriebssystems) nur dann geringer, wenn die Anzahl der Elemente in der Warteschlange mindestens die Hälfte der möglichen Elemente ist (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

Als Anwendungsbeispiel sei hier eine iterative Breitensuche in einem Binärbaum behandelt (siehe dort fü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.