MindStudy - MindStudy

Question:

Published on: 3 December, 2024

Define the ADT for stack. Show the implementation of the stack data structure using linked list.

Answer:

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.

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