/* List-based implementation of the ADT stack. */
#include "stack.h"
#include <stdlib.h>                           /* for NULL */

typedef struct listnode {                     /* type for items in list */
    struct listnode *next;
    void *item;
} listnode;

typedef struct stacktype {                    /* basic stack type */
    listnode *list;
    int itemcount;
} stacktype;

stack stack_init(int size) {
    stack result;
    result = (stack)malloc(sizeof(stacktype));/* space for stack struct */
    if (result == NULL) {
        return NULL;                          /* no space available */
    }
    result->list = NULL;                      /* No nodes */
    result->itemcount = 0;                    /* so count is 0 */
    return result;
}
void stack_free(stack stk) {
    listnode *p, *q;
    p = stk->list;                            /* set p to first node */
    while (p != NULL) {                       /* while nodes remain */
        q = p->next;                          /* remember next node */
        free(p);                              /* free this one */
        p = q;                                /* set p to next node */
    }
    free(stk);                                /* free stack structure */
}

int stack_push(stack stk, void *item) {
    listnode *p;
    p = (listnode*)malloc(sizeof(listnode));  /* space for list node */
    if (p == NULL) {
        return 0;                             /* no space for node */
    }
    stk->itemcount++;                         /* count extra node */
    p->item = item;                           /* record user data ptr */
    p->next = stk->list;                      /* p precedes current list */
    stk->list = p;                            /* and becomes new head */
    return 1;                                 /* success */
}

int stack_empty(stack stk) {
    return (stk->itemcount == 0);
}

void *stack_pop(stack stk) {
    listnode *p;
    void *result;
    if (stk->list==NULL) {
        return NULL;                          /* No node, so no data! */
    }
    stk->itemcount--;                         /* one fewer items */
    p = stk->list;                            /* address of head node */
    result = p->item;                         /* recover user's data ptr */
    stk->list = p->next;                      /* disconnect head node */
    free(p);                                  /* free discarded node */
    return result;                            /* return user's data ptr */
}

void *stack_top(stack stk) {
    if (stk->list==NULL) {
        return NULL;                          /* No node, so no data! */
    }
    return stk->list->item;                   /* return user's data ptr */
}

int stack_count(stack stk) {
    return stk->itemcount;
}