img
Question:
Published on: 27 May, 2022

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

 

Random questions