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

Top comments (7)

Collapse
 
pauljlucas profile image
Paul J. Lucas • Edited

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 • Edited

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
 
josethz00 profile image
José Thomaz

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...

 
josethz00 profile image
José Thomaz

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!