MindStudy - MindStudy

Question:

Published on: 21 January, 2025

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

Subjects

C Programming and Practices Database Management System Data Structures & Algorithm Software Engineering Design and Analysis of Algorithm Mobile computing

Trending

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

21 January, 2025

Find the postfix notation of

( a + b * x) / ( a ! – d ) s – c * y ( show all steps ).

21 January, 2025

What is the benefit of using arrays of pointers instead of several pointer variables?

23 January, 2022

a) Sort the following list using the Radix Sort :