#include <stdlib.h>

/*	Stack ADT Type Defintions 
	Written by: G & F
	Modified by Peter Brusilovsky
	
*/
	typedef struct node 
		{
		 int data ;
		 struct node *link ;
		} STACK_NODE;

	typedef struct
		{
		 int count ; 
		 STACK_NODE *top ; 
		} STACK;

/*	=============== createStack ==============	*/
/*	This algorithm creates an empty stack.
	Pre		Nothing
	Post	Returns pointer to a null stack
			-or- NULL if overflow.
*/
static STACK  *createStack (int par)
{
	STACK  *stack ;

	stack = (STACK *) malloc( sizeof (STACK) ) ;
	if (stack)
		{
		 stack->top   = NULL ;
		 stack->count = 0;
		} /* if */

	return stack ;
}	/* createStack */

/*	=============== pushStack ============== */
/*	This function pushes an item onto the stack.
	Pre		stack is a pointer to the stack
			dataPtr is a pointer to the data to be inserted
	Post		Returns 1 if success; 0 if heap overflow
*/
static int pushStack(STACK *stack, int dataIn)
{
	STACK_NODE *newPtr;

	newPtr = (STACK_NODE *) malloc(sizeof( STACK_NODE));
	if (newPtr == NULL)
		return 0; /* no more space */
		
	newPtr->data = dataIn; 

	newPtr->link = stack->top; 
	stack->top = newPtr; 

	( stack->count )++; 

	return 1;
}	/* pushStack */

/*	=============== popStack ============== */
/*	This function pops the item on the top of the stack.
	Pre		stack is a pointer to the stack
	Post		Returns 1 if success; 0 if underflow
				dataPtr is a pointer to the data popped

*/
static int popStack (STACK *stack, int *dataOutPtr) 
{
	STACK_NODE *dltPtr;

	if (stack->count == 0)
		return 0;
	else
		{
		 dltPtr = stack->top;
		 *dataOutPtr = (stack->top)->data;
		 stack->top = (stack->top)->link;
		 free (dltPtr);
		 (stack->count)--;
		} /* else */
	return 1;
}	/* popStack */

/*	=============== stackTop ============== */
/*	This function retrieves the data from the top of the 
	stack without changing the stack.
	Pre		stack is a pointer to the stack
	Post		Returns 1 if success; 0 if underflow
				dataPtr is a pointer to the data on the top
*/
static int stackTop (STACK *stack, int *dataOutPtr) 
{
	if (stack->count > 0) {
		*dataOutPtr = (stack->top)->data;
	    return 1;
	} else
	    return 0;
}	/* stackTop */

/*	=============== emptyStack ============== */
/*	This function determines if a stack is empty 
	Pre		stack is a pointer to the stack
	Post		returns 1 if empty; 0 if data are in the stack 
*/
static int emptyStack (STACK *stack) 
{
	return (stack->count == 0);

}	/* emptyStack */

/*	=============== fullStack ============== */
/* 	This function determines if a stack is full.
	Full is defined as heap full
	Pre		stack is a pointer to a stack head node
	Post		returns 1 if heap is full; 0 if heap has room 
*/
static int fullStack (STACK *stack) 
{
STACK_NODE *temp;

	if ( (temp = (STACK_NODE *)malloc (sizeof (STACK_NODE))) )
		{
		 free ( temp );
		 return 0;
		} /* if */

	/* malloc failed */
	return 1;
}	/* fullStack */

/*	=============== stackCount ============== */
/*	This function returns the number of elements in the stack.
	Pre		stack is a pointer to the stack
	Post		count returned
*/
static int stackCount(STACK *stack) 
{

	return stack->count;
	
}	/* stackCount */

/*	=============== destroyStack ============== */
/* 	This function releases all nodes to the heap.
	Pre		A stack
	Post		returns null pointer.
*/
static STACK *destroyStack ( STACK *stack ) 
{
	STACK_NODE *deletePtr;

	if (stack)
		{
		 /* Delete all nodes in stack */
		 while ( stack->top != NULL )  {
			  deletePtr = stack->top ;
			  stack->top = stack->top->link; 
			  free ( deletePtr ); 
			} /* while */
			
		/* Stack now empty. Destroy stack head node. */
		free (stack);
		} /* if stack */

	return NULL;
}	/* destroyStack */