Data structures in C: Stack

Introduction

Stack is a linear data structure that puts its elements one over the other in sequential order. Think about a pile of plates, is the same thing as a stack, you put one plate over the other and if you use it correctly the first item you pop out of the pile is the last item that you have putten into it.

When you have a data structure that the last element is the first to go out, we call it LIFO, which means Last In - First Out. So the first element inserted into the stack will be the last to go out and the last element inserted will be the first to go out.

Here is an animated illustration of a stack:

Stack operations

Now let's start diving into the details of this data structure by defining the operations that it should do.

stack(int m)

Creates and returns an empty stack, with maximum capacity m.

push_S(char x, Stack * S)

Insert the item x on top of the stack.

pop_S(Stack * S)

Removes and returns the item on top of the stack.

top_S(Stack S)

Accesses and returns the item on top of the stack without removing it.

destroy_S(Stack * S)

Destroys the stack received by the parameter in the function by freeing its memory space.

is_empty_S(Stack S)

Return true (stdbool.h) if the stack S is empty, otherwise , returns false(stdbool.h).

is_empty_S(Stack S)

Return true (stdbool.h) if the stack S is full, otherwise , returns false(stdbool.h).

Stack implementation (struct)

We can define a stack of char like this:

typedef char TmpT;

typedef struct stack {
  int max;
  int top;
  TmpT * item;
} Stack;

First we define a type called TmpT as the primitive type char. This was made because if we decide to modify our stack to work with integers, floats or any other data type, we just need to change de TmpT declaration, and the stack struct itself remains intact. After that, the Stack is defined with 3 properties/fields, they are: max, top and item.

The max property is the max number of elements that the stack comports. The top is the index of the last item in the stack (the last in). The item property is a pointer to a data type, in this case a char pointer, so it will have all the items of the stack, all the characters.

Stack implementation (methods)

Stack *stack(int m) {
  Stack *S = (Stack *)malloc(sizeof(struct stack));
  S->max = m;
  S->top = -1;
  S->item = (TmpT *)malloc(m * sizeof(TmpT));
  return S;
}

int is_empty_S(Stack S) {
  return (S.top == -1);
}

int is_full_S(Stack S) {
  return (S.top == S.max - 1);
}

void push_S(TmpT x, Stack *S) {
  if (is_full_S(*S)) {
    puts("Stack full!");
    abort();
  }
  S->top++;
  S->item[S->top] = x;
}

TmpT pop_S(Stack *S) {
  if (is_empty_S(*S)) {
    puts("Stack empty!");
    abort();
  }
  TmpT x = S->item[S->top];
  S->top--;
  return x;
}

TmpT top_S(Stack S) {
  if (is_empty_S(S)) {
    puts("Stack empty!");
    abort();
  }
  return S.item[S.top];
}

void destroy_S(Stack *S) {
  free(S->item);
  free(S);
  S = NULL;
}

Examples

Now that we already defined and implemented our stack data structure, let's do some practical exercises with this. The first exercise is to reverse a chain of characters, here's the code:

#include <stdio.h>
#include <stdlib.h>
#define STACK_LENGTH 513

int main(void) {
  char c[STACK_LENGTH];
  // initialize the stack
  Stack * s = stack(STACK_LENGTH);

  printf("Type a chain of characters: ");
  fgets(c, STACK_LENGTH, stdin);

  // foreach char of the string c received at fgets, pushes it to the stack
  for (int i = 0; c[i]; i++) {
    push_S(c[i], s);
  }

  printf("Reversed chain: ");

  // while the stack is not empty, pops the last element of the stack. 
  // By the end of this loop there will be printed the reversed string
  while (!is_empty_S(*s)) {
    printf("%c", pop_S(s));
  }
  puts("\n");

  destroy_S(s);

  return 0;
}

Another exercise that we can do with stacks is decimal to binary number conversion, in this case we can use the stack as a "storage" to the digits of the binary number. For this exercise don't forget to change the TmpT type to int. The final code is:

#include <stdio.h>
#include <stdlib.h>

int main(void) {
  int n;
  Stack s = stack(8);

  printf("Enter a decimal number: ");
  scanf("%d", &n);

  do {
    push_S(n % 2, &s);
    n /= 2;
  } while (n > 0);

  printf("The binary representation of %d is: ", n);

  while (!is_empty_S(s)) {
    printf("%d", pop_S(&s));
  }
  puts("\n");

  destroy_S(&s);

  return 0;
}

Conclusion

We have reached the end of this article and here we were able to understand what a stack is, how it works, how to implement it in the C language and we also discussed some of its applications.

Sources

Blogpost: Stack Data Structure (Introduction and Program)

Blogpost: Stack in C Programming

Book: Estruturas de dados em C: Uma abordagem didática - Silvio do Lago Pereira