Stack

In diesem Artikel wird es um Stacks und deren Funktionsweise gehen.

Was ist das?

Ein Stack ist ein Datenbereich, in dem Daten gespeichert werden können. Soweit so gut, nichts neues. Interessant dabei ist, wie die Daten organisiert werden.

Man benötigt nur 2 Anweisungen, um Daten in einem Stack zu organisieren: Push und Pop.

  Mit Push legt man Daten auf den Stack, mit Pop holt man sie wieder zurück.

Man legt immer nur Daten auf ein Ende des Stacks. Von dem selben Ende werden auch die Daten wieder gelesen. Deswegen bezeichnet man einen Stack auch als Stapel, bzw. wegen der „Richtung“ (von höheren Adressen zu niedrigeren) Kellerstapel.

Funktionsweise

Theorie

Man kann sich einen Stack wie einen Stapel Teller vorstellen. Zu Beginn ist der Stapel leer, d.h. es existiert noch gar kein Stapel. Legt man dann ein Element (einen Teller) auf den Stapel, dann besteht der Stapel aus einem Element (Teller). Nun kann man das Element wieder von Stapel nehmen. Nach dieser Aktion ist der Stapel wieder leer. Man kann aber auch ein weiteres Element auf den Stapel legen. Dann befinden sich 2 Elemente auf dem Stapel. Holt man dann ein Element vom Stapel, bekommt man nur das „oberste“ (wie bei einem Stapel Teller eben, man kann nur den obersten Teller nehmen).

Das zuletzt auf den Stapel gelegte Element wird also als erstes zurückgegeben. Das Element, dass als erstes auf den Stapel gelegt wurde, wir folglich als letztes vom Stapel genommen.
Dieses Prinzip nennt man FILO, was so viel bedeutet wie „First in, last out“ (Als erstes rein, als letztes raus).

Man kann es natürlich auch LIFO nennen („Last in, first out“ - „Zuletzt rein, zuerst raus“).

Praxis

In der Praxis gibt es einen Zeiger, der sozusagen auf die Spitze unseres Stapels zeigt. Betrachtet man noch einmal kurz den Namen Kellerspeicher, so wird klar (bzw. es ist so^^) dass der Stack nach unten, in den Keller wächst.

Nehmen wir einen Beispielstack. Dieser Stack ist zuallererst natürlich leer (niemand hat etwas darauf gepushed).

leerer Stack Der Stackzeiger (bei 32 BIT- Protected Mode Programmen heißt er esp) zeigt auf das obere Ende des Stacks. Eine Pop-Anweisung sollte hier nicht ausgeführt werden (der Stack ist ja leer).
Stack mit einem Element Eine Push-Anweisung wurde durchgeführt. Als Argument hat man ihr den Wert 1234 gegeben. Zuerst wurde der Stackzeiger verringert (er zeigt nun auf die oberste/erste nutzbare Speicherstelle). Anschließend wurde der Wert in die erste/oberste Speicherstelle geschrieben. Eben in die Stelle, auf die der Stackzeiger nun zeigt. Würde man hiernach eine Pop-Anweisung ausführen, würde sie den Wert 1234 liefern und den Stackzeiger erhöhen.
Stack mit 2 Elementen Es wurde wieder eine Push-Anweisung ausgeführt. Argument war diesmal 5678. Dabei wurde wieder zunächst der Stackzeiger verringert und anschließend der Wert an die Speicherstelle geschrieben, auf die der Stackzeiger nun zeigt. Eine Pop-Anweisung würde hier 5678 liefern. Eine weitere Pop-Anweisung den Wert 1234.
Stack mit 3 Elementen Wieder ein Push. Dabei wurde dieses mal der Wert 9000 übergeben. Was die Pop-Anweisungen (mehr als 3 sollten es nicht sein) nun liefern würden ist klar…
Stack mit 2 Elementen Jetzt mal eine Pop-Anweisung. Es wird der Wert ausgelesen (9000) und danach der Stackzeiger erhöht. Der alte Wert bleibt dabei natürlich im Speicher stehen. Beim nächsten Push…
Stack mit 3 Elementen … wird er aber mit dem neu gepushtem Wert überschrieben. In diesem Fall ist das der Wert 1991.

Beispiel-Implementierung

Ich möchte hier auch eine kleine Beispielimplementierung für einen eigenen Stack geben. Fragen zu dem Code bitte ins Forum.

#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct
{
  unsigned int* esp;
  unsigned int size;
  unsigned int maxSize;
} Stack;
 
 
Stack * CreateStack( unsigned int maxSize );
void Push( Stack * stack, unsigned int value );
unsigned int Pop( Stack * stack );
void DestroyStack( Stack * stack );
int isEmpty (Stack *stack);
int isFull (Stack *stack);
 
 
int main ()
{
 
  Stack *s;
  int i;
 
  s = CreateStack (5);
 
  for (i = 0; i < 10; i++)
    if (!isFull (s))
      Push (s, i);
 
  for (i = 0; i < 10; i++)
    if (!isEmpty (s))
      printf ("Element %d: %u\n", i + 1, Pop (s));
 
  DestroyStack (s);
 
  return 0;
 
}
 
 
Stack * CreateStack( unsigned int maxSize )
{
  if( maxSize <= 0 )
    return 0;
 
  Stack * stack = (Stack*) malloc( sizeof( Stack ) );
  stack->maxSize = maxSize;
  stack->size = 0;
  stack->esp = (unsigned int *) malloc( maxSize * sizeof (unsigned int));
 
  return stack;
}
 
void Push( Stack * stack, unsigned int value )
{
  stack->esp[stack->size] = value;
  stack->size++;
}
 
unsigned int Pop( Stack * stack )
{
  stack->size--;
  return stack->esp[stack->size];
}
 
void DestroyStack( Stack * stack )
{
    free( stack->esp );
    free( stack );
    stack = NULL;
}
 
int isEmpty (Stack * s)
{
  return (s->size == 0);
}
 
int isFull (Stack * s)
{
  return (s->size == s->maxSize);
}