DEV Community

Cover image for Data structures in C: Stack
José Thomaz
José Thomaz

Posted on

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.

Pile of plates

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:

Animation of a stack working

 

Stack operations

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

Stack operations

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;
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

 

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;
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

 

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

Discussion (7)

Collapse
pauljlucas profile image
Paul J. Lucas • Edited on

Generally, the type of the stack element is void* or, somewhat better, uint64_t. Then you can put any type you like in the stack. If sizeof(T) <= sizeof(uint64_t), then just cast the element types; otherwise dynamically allocated the Ts and store the pointers in the elements.

Also, most implementations aren't of fixed size; instead, each element has a next pointer. Lastly, if you use a singly linked list for the implementation, if you do just a bit more work, make it support full list operations and you get stack operations for free since a stack is a subset of a list.

Collapse
josethz00 profile image
José Thomaz Author • Edited on

Thanks for the feedback, I already used void* but never uint64_t I will research about it.

Collapse
pauljlucas profile image
Paul J. Lucas

The reason for using uint64_t is because it's guaranteed to work on all platforms, specifically 32-bit platforms where sizeof(void*) is 4 — uint64_t guarantees 8.

Collapse
t0nyba11 profile image
Tony B

Why the mixing of pointers and copies of Stack structures?
Shouldn't everything be pointers?

Also, S = NULL in destroy_S() doesn't do anything, right?
You are just setting the local stack variable to NULL.

Collapse
josethz00 profile image
José Thomaz Author

Hi Tony, this mixing is just a pattern that I use which consists in using pointers when you need to change some information and copies when I need to just query some data, but I am considering to use only pointers, thanks for your feedback!

And about S = NULL I am doing this to overwrite the content at this memory cell, just free is not 100% safe because you might have problems with dangling pointers: stackoverflow.com/questions/102558...

Collapse
t0nyba11 profile image
Tony B

I see what you are trying to do there with the Stack vs Stack* but using const is a much better way to do that, so the code doesn't have to copy the entire structure with each call.

With the S = NULL you are only changing the local stack variable, not the original pointer, so that won't achieve what you are trying to do. You would need a pointer to the original pointer. I have a feeling this might be what you intended, because one of your snippets above has destroy_S(&s) the other destroy_S(s) ?

Thanks for making some unused-in-20-years neurons in my brain wake up :)

Thread Thread
josethz00 profile image
José Thomaz Author

I haven't noticed that mistake in the pointer at the code snippets, this was an old code and I forgot to update, thank you, already fixed!