Algorithmen und Datenstrukturen in C/ Stapelspeicher

Ein Stapelspeicher (oder Stack) ist eine spezielle Datenstruktur, mit der beliebige Daten verwaltet werden können.

Wikipedia hat einen Artikel zum Thema:

Stapelspeicher

Auf einem Stack sind zwei Operationen definiert:

pop: Einen Wert vom Stapelspeicher entfernen.
push: Einen Wert auf den Stapelspeicher legen.

Diese Operationen wirken sich immer auf die Spitze des Stapelspeichers aus, daher ist der Stapel ein sogenannter LIFO-Speicher (Last In First Out). Dies ist in der nebenstehenden Abbildung dargestellt.

Implementation

Ein Stapelspeicher kann auf verschiedene Weisen implementiert werden, im Folgenden sollen zwei Möglichkeiten besprochen werden.

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 stack_s stack_t;

int stack_destroy(stack_t *stack);
int stack_empty(stack_t *stack);
stack_t *stack_new(void);
void *stack_pop(stack_t *stack);
int stack_push(stack_t *stack, 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 des Stapelspeichers stets mit der Anzahl der Elemente, die auf dem Stapelspeicher 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 stack_frame_s {
  struct stack_frame_s *next;
  void *data;
};

struct stack_s {
  struct stack_frame_s *top;
};

Damit lassen sich die Funktionen folgendermaßen implementieren:

int stack_destroy(stack_t *stack) {
  if (stack == NULL) {
    return ERR_INVAL;
  }
  while (stack->top != NULL) {
    struct stack_frame_s *frame = stack->top;
    stack->top = frame->next;
    free(frame);
  }
  free(stack);
  return SUCCESS;
}

int stack_empty(stack_t *stack) {
  if (stack == NULL || stack->top == NULL) {
    return TRUE;
  } else {
    return FALSE;
  }
}

stack_t *stack_new(void) {
  stack_t *stack = malloc(sizeof(*stack));
  if (stack == NULL) {
    return NULL;
  }
  stack->top = NULL;
  return stack;
}

void *stack_pop(stack_t *stack) {
  if (stack == NULL || stack->top == NULL) {
    return NULL;
  }
  struct stack_frame_s *frame = stack->top;
  void *data = frame->data;
  stack->top = frame->next;
  free(frame);
  return data;
}

int stack_push(stack_t *stack, void *data) {
  if (stack == NULL) {
    return ERR_INVAL;
  }
  struct stack_frame_s *frame = malloc(sizeof(*frame));
  if (frame == NULL) {
    return ERR_NOMEM;
  }
  frame->data = data;
  frame->next = stack->top;
  stack->top = frame;
  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

STACK_GROW_SIZE: Anzahl von Speicherplätzen, um die der Stapelspeicher bei Größenänderung wachsen soll. Die Implementation ist so angelegt, dass beim Verkleinern des Stapelspeichers die Anzahl der verfügbaren Speicherplätze ein ganzzahliges Vielfaches dieser Größe ist.
STACK_INIT_SIZE: Initiale Anzahl von Speicherplätzen.
STACK_SHRINK_AT: Die Anzahl freier Speicherplätze, die mindestens vorhanden sein müssen, um den Stapelspeicher 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 auf dem Stapelspeicher mindestens die Hälfte der möglichen Elemente ist (d.h. bei einem Stapelspeicher, der zehn Elemente ohne Speicheroperationen aufnehmen kann, müssen mindestens fünf Elemente auf dem Stapelspeicher liegen).

Diese Implementation verwendet die folgenden Datenstrukturen:

struct stack_s {
  void **bottom;
  size_t len;
  size_t size;
};

Damit lassen sich die Funktionen folgendermaßen implementieren:

int stack_destroy(stack_t *stack) {
  if (stack == NULL) {
    return ERR_INVAL;
  }
  free(stack->bottom);
  free(stack);
  return SUCCESS;
}

int stack_empty(stack_t *stack) {
  if (stack == NULL || stack->len == 0) {
    return TRUE;
  } else {
    return FALSE;
  }
}

stack_t *stack_new(void) {
  stack_t *stack = malloc(sizeof(*stack));
  if (stack == NULL) {
    return NULL;
  }
  if ((stack->bottom = malloc(STACK_INIT_SIZE*sizeof(*(stack->bottom)))) == NULL) {
    free(stack);
    return 0;
  }
  stack->size = STACK_INIT_SIZE;
  stack->len = 0;
  return stack;
}

void *stack_pop(stack_t *stack) {
  if (stack == NULL || stack->len == 0) {
    return NULL;
  }
  void *data = stack->bottom[--(stack->len)];
  if ((stack->size - stack->len) >= STACK_SHRINK_AT) {
    size_t new_size = stack->len + (stack->len + STACK_GROW_SIZE) % STACK_GROW_SIZE;
    stack->bottom = realloc(stack->bottom, new_size*sizeof(*(stack->bottom)));
    stack->size = new_size;
  }
  return data;
}

int stack_push(stack_t *stack, void *data) {
  if (stack == NULL) {
    return ERR_INVAL;
  }
  if (stack->len == stack->size) {
    size_t new_size = stack->size + STACK_GROW_SIZE;
    void **new_bottom = realloc(stack->bottom, new_size*sizeof(*(stack->bottom)));
    if (new_bottom == NULL) {
      return ERR_NOMEM;
    }
    stack->bottom = new_bottom;
    stack->size = new_size;
  }
  stack->bottom[(stack->len)++] = data;
  return SUCCESS;
}

Anwendungsbeispiel

Als Anwendungsbeispiel sei hier eine iterative Tiefensuche in einem Binärbaum behandelt (siehe dort für die Definition von knoten):

void dfs(knoten *tree, void (*f)(int, void *), void *user) {
  if (tree == NULL) {
    return;
  }
  stack_t *stack = stack_new();
  stack_push(stack, tree);
  while (!stack_empty(stack)) {
    knoten *k = stack_pop(stack);
    if (k->rechts != NULL) {
      stack_push(stack, k->rechts);
    }
    if (k->links != NULL) {
      stack_push(stack, k->links);
    }
    (*f)(k->wert, user);
  }
  stack_destroy(stack);
}

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.