Stapel (Stack)

Ein Stack ist ebenfalls eine lineare Datenstruktur, bei der jedoch die Operationen nur auf ein Ende arbeiten, den Top Of Stack. Man stellt es sich wie einen Stapel Karten vor, man kann nur oben auflegen, oder oben abnehmen, nicht jedoch an die Mitte kommen.

Operationen sind klassischerweise push (ein Objekt drauflegen), pop (ein Objekt abheben) und möglicherweise peek (schauen was oben aufliegt, ohne es abzuheben).

Hier tut eine einfach verkettete Liste auch alles nötige, sinnvoll ist es am Anfang anzuhängen, also irgendwie so:

int push_stack(struct stack *s, struct item *i)
{
    i->next = s->data;
    s->data = i;
    s->count++;
}

struct item *pop_stack(struct stack *s)
{
    struct item *ret = NULL;

    if (s->count)
    {
        ret = s->data;
        s->data = s->data->next;
        s->count--;
    }

    return ret;
}

struct item *peek_stack(struct stack *s)
{
    if (s->count)
        return s->data;
    else
        return NULL;
}
    

Je nach Grad an Paranoia kann man (auch bei der Liste) die Struktur vorher kopieren und eine Kopie mit geNULLten Zeigern zurückgeben, damit der Benutzer nicht an die next-Zeiger kommt, aber wenn ein Aufrufer von Funktionen ein Programm kaputt machen will, dann kriegt er das erfahrungsgemäß auch hin, egal wie viele Steine man in den Weg legt. ;-)