typedef struct _stack_t
{
    int *  top;  /* Top Of Stack (TOS) pointer                 */
    size_t used; /* number of items on stack                   */
    size_t size; /* maximum number of items that can be stored */
} stack_t;

bool stack_init (stack_t * stack, size_t n)
{
    /* sanity check */
    assert((n > 0) && "Attempting to allocate a zero-sized stack!");
    
    /* safety check */
    if (stack->top != NULL)
    {
        stack_destroy(stack);
    }
    
    /* allocate memory */
    int * ptr = malloc(n * sizeof(*ptr));

    if (ptr != NULL) /* malloc succeeded */
    {
        stack->top = ptr + n; /* point to end of memory */
        stack->used = 0;      /* new stack is empty     */
        stack->size = n;      /* store maximum size     */
        return true;          /* indicate success       */
    }
    else /* malloc failed, so we set the stack to a known invalid state */
    {
        stack->top = NULL; /* invalid stack has NULL TOS pointer        */
        stack->used = 0;   /* invalid stack is empty by definition      */
        stack->size = 0;   /* invalid stack has zero size by definition */
        return false;      /* indicate failure                          */
    }
}

void stack_destroy (stack_t * stack)
{
    /* safety check */
    if (stack->top != NULL)
    {
        /* get pointer to start of memory */
        int * bottom = stack->top - stack->size + stack->used;
        
        /* release memory */
        free(bottom);
        
        stack->top = NULL;
        stack->used = 0;
        stack->size = 0;
    }
}

bool stack_is_empty (stack_t * stack)
{
    /* an invalid stack cannot return true, or somebody might try to push onto it */
    return (stack->used == 0) && (stack->size > 0);
}

bool stack_is_full (stack_t * stack)
{
    return (stack->used == stack->size);
}

void stack_push (stack_t * stack, int i)
{
    /* sanity check */
    assert((stack->used < stack->size) && "Attempting to push onto a full stack!");
    
    --(stack->top);    /* decrement TOS pointer */
    *(stack->top) = i; /* store value           */
    ++(stack->used);   /* increment used count  */
}

int stack_pop (stack_t * stack)
{
    /* sanity check */
    assert((stack->used > 0) && "Attempting to pop from an empty stack!");

    int i = *(stack->top); /* get value from top of stack */
    ++(stack->top);        /* increment TOS pointer       */
    --(stack->used);       /* decrement used count        */
    return i;
}

typedef struct _stack_t
{
    int *  top;  /* Top Of Stack (TOS) pointer                 */
    size_t used; /* number of items on stack                   */
    size_t size; /* maximum number of items that can be stored */
} stack_t;

int stack_init (stack_t * stack, size_t n)
{
    /* sanity check */
    assert((n > 0) && "Attempting to allocate a zero-sized stack!");
    
    /* safety check */
    if (stack->top != NULL)
    {
        stack_destroy(stack);
    }
    
    /* allocate memory */
    int * ptr = malloc(n * sizeof(*ptr));

    if (ptr != NULL) /* malloc succeeded */
    {
        stack->top = ptr + n; /* point to end of memory   */
        stack->used = 0;      /* new stack is empty       */
        stack->size = n;      /* store maximum size       */
        return 1;             /* indicate success somehow */
    }
    else /* malloc failed, so we set the stack to a known invalid state */
    {
        stack->top = NULL; /* invalid stack has NULL TOS pointer        */
        stack->used = 0;   /* invalid stack is empty by definition      */
        stack->size = 0;   /* invalid stack has zero size by definition */
        return 0;          /* indicate failure somehow                  */
    }
}

void stack_destroy (stack_t * stack)
{
    /* safety check */
    if (stack->top != NULL)
    {
        /* get pointer to start of memory */
        int * bottom = stack->top - stack->size + stack->used;
        
        /* release memory */
        free(bottom);
        
        stack->top = NULL;
        stack->used = 0;
        stack->size = 0;
    }
}

int stack_is_empty (stack_t * stack)
{
    /* an invalid stack cannot return true, or somebody might try to push onto it */
    return ((stack->used == 0) && (stack->size > 0)) ? 1 : 0;
}

int stack_is_full (stack_t * stack)
{
    return (stack->used == stack->size) ? 1 : 0;
}

void stack_push (stack_t * stack, int i)
{
    /* sanity check */
    assert((stack->used < stack->size) && "Attempting to push onto a full stack!");
    
    --(stack->top);    /* decrement TOS pointer */
    *(stack->top) = i; /* store value           */
    ++(stack->used);   /* increment used count  */
}

int stack_pop (stack_t * stack)
{
    /* sanity check */
    assert((stack->used > 0) && "Attempting to pop from an empty stack!");

    int i = *(stack->top); /* get value from top of stack */
    ++(stack->top);        /* increment TOS pointer       */
    --(stack->used);       /* decrement used count        */
    return i;
}