• 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.

#define TRUE  1
#define FALSE 0

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)--;
}