The abstract data type Stack - Part 1

The ADT Stack is specified by

* one constructor, namely,
- stack *create_stack(void)
+ that constructs a data structure of type stack, empty for the moment,
and returns a pointer to it,
* two access functions, namely,
- boolean stack_is_empty(stack *s)
+ that, given a pointer s to a stack,
returns TRUE if the stack is empty and returns FALSE otherwise,
- stack_object *top_of_stack(stack *s)
+ that, given a pointer s to a nonempty stack,
returns a pointer to the object on the top of the stack,
* two manipulator functions, namely,
- void push_on_stack(stack *s, stack_object *object);
+ that, given a pointer s to a stack and given a pointer object to an object,
pushes the object on the top of the stack,
- void pop_stack(stack *s);
+ that, given a pointer s to a nonempty stack,
pops the stack.

The data type stack_object is provided by the ADT user; the data type stack is chosen by the designer of the data structure that implements the ADT. In C, the data type boolean is not provided explicitly, but may be created by the definitions

#define TRUE 1
#define FALSE 0

and the declaration

typedef char boolean;
=======================================================================================
Implementing Stack as a linked list

typedef struct stack_item
{
stack_object content;
struct stack_item *next;
} stack_item;

typedef stack_item *stack;

stack *create_stack(void)
{
stack *s;
s = (stack *) malloc(sizeof(stack));
if(s==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

*s = NULL;
return s;
}

boolean stack_is_empty(stack *s)
{
return( (*s==NULL) ? TRUE : FALSE );
}

stack_object *top_of_stack(stack *s)
{
if(stack_is_empty(s)==TRUE)
{
printf("TRIED TO FIND THE TOP OF AN EMPTY STACK!\n");
exit(1);
}

return &((*s)->content);
}

void push_on_stack(stack *s, stack_object *object)
{
stack_item *new_item;
new_item = (stack_item *) malloc(sizeof(stack_item));
if(new_item==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

new_item->content=*object;
new_item->next=*s;
*s=new_item;
}

void pop_stack(stack *s)
{
stack_item *memo;

if(stack_is_empty(s)==TRUE)
{
printf("TRIED TO POP AN EMPTY STACK!\n");
exit(1);
}

memo=*s;
*s=memo->next;
free(memo);
}
=======================================================================================
Implementing Stack as an array

typedef struct stack
{
stack_object *array;
int capacity;
int count;
} stack;

stack *create_stack(void)
{
stack *s;
stack_object *object;

s = (stack *) malloc(sizeof(stack));
if(s==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

object = (stack_object *) malloc(sizeof(stack_object));
if(object==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}

s->array = object;
s->count = 0;
s->capacity = 1;
return s;
}

boolean stack_is_empty(stack *s)
{
return( (s->count==0) ? TRUE : FALSE );
}

stack_object *top_of_stack(stack *s)
{
if(stack_is_empty(s)==TRUE)
{
printf("TRIED TO FIND THE TOP OF AN EMPTY STACK!\n");
exit(1);
}

return (s->array)+((s->count)-1);
}

void push_on_stack(stack *s, stack_object *object)
{
stack_object *newarray;

if(s->count == s->capacity)
/*DOUBLE THE LENGTH OF THE ARRAY */
{
(s->capacity)*=2;
newarray = (stack_object *)
realloc(s->array, (s->capacity)*sizeof(stack_object));
if(newarray==NULL)
{
printf("OUT OF MEMORY!\n");
exit(1);
}
s->array = newarray;
}

(s->array)[s->count]=*object;
(s->count)++;
}

void pop_stack(stack *s)
{
if(stack_is_empty(s)==TRUE)
{
printf("TRIED TO POP AN EMPTY STACK!\n");
exit(1);
}

(s->count)--;
}
=======================================================================================]
Reference:
Reallocating Memory Blocks
Calloc and Realloc
Memory Allocation
Dynamic Memory Allocation and Dynamic Structures
Pointers and Arrays
Arrays and Pointers
Pointers and Arrays; Pointer Arithmetic

http://vi.wikipedia.org/wiki/Th%E1%BA%A3o_lu%E1%BA%ADn:Ng%C4%83n_x%E1%BA%BFp#.E1.BB.A8ng_d.E1.BB.A5ng_c.E1.BB.A7a_Stack
http://www.research.rutgers.edu/~chvatal/notes/stack.html