Implementing a stack data structure in C

Stack is a way we can store information. It follows the simple process of Last In, First Out or LIFO. Adding an item to the top of the stack is called a “push” operation. Removing an item from the top of a stack is called a “pop” operation. Another operation is “top”. Top simply returns the latest item that has been pushed the stack. Depending on the application, sometimes the pop operation can also be used as a top by returning what has been removed to the caller. These operations have a constant time or a time complexity of O(1).

We can implement a stack using arrays or a linked list. In array implementation, you can push a stack only until you reach the size of an array. We can have a situation where we consume the array and we cannot push anymore. This is what we call a stack overflow. There a few ways to avoid a stack overflow:

1. Add a semantic check before you push a new item to the stack

2. We can create a new large array and copy the contents of the older filled up array. The cost of copy is O(n) where n is the size of the filled up array. Simple strategy of deciding the size of the new array is doubling n

Here is a simple example of a stack implementation in C

#include <stdio.h>

#define STACK_CAPACITY 10

//A int stack data Structure
struct Stack {
    int     list[STACK_CAPACITY];
    int     size;
};
typedef struct Stack Stack;


//Initialize stack
void initStack(Stack *s)
{
    s->size = 0;
}

//Return the top of stack
int top(Stack *s)
{
    if (s->size == 0) {
        printf("Error: stack empty\n");
        return -1;
    } 

    return s->list[s->size-1];
}

//Returning the current size of a stack
int size(Stack *s)
{
    return s->size;
}


//Push an item to the stack
void push(Stack *s, int item)
{
    if (s->size < STACK_CAPACITY)
        s->list[s->size++] = item;
    else
        printf("Error: stack full\n");
}

//Pop an item to the stack
void pop(Stack *S)
{
    if (S->size == 0)
        printf("Error: stack empty\n");
    else
        S->size--;
}

int main()
{
  //Create local variables
  int item=-1, currentSize = -1;

  //Create a stack strucuture
  Stack s;
  
  //Initialize stack
  initStack(&s);

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Push three items to a stack
  item = 2;
  push(&s, item);

  item = 1996;
  push(&s, item);

  item = 203;
  push(&s, item);

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Get the current top item of the stack
  item = -1;
  item = top(&s);
  printf("Current top item of the stack %d\n", item);
 
  //Use the pop operations couple of times
  pop(&s); //pop 203
  pop(&s); //pop 1996

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Get the current top item of the stack
  item = -1;
  item = top(&s); //returns 2
  printf("Current top item of the stack %d\n", item);

  item = 0;

  //Try to overlow the stack by push "0" ten times
  for(int i=0; i < STACK_CAPACITY; i++)
  {
      push(&s, item);
  }

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Try to empty the stack
  for(int i=0; i < STACK_CAPACITY; i++)
  {
      pop(&s);
  }

  //Get the current size of a stack
  currentSize = size(&s);
  printf("Current size of a stack %d\n", currentSize);

  //Empty the stack while it is empty
  pop(&s);
  
  return 0;
}

 

Here is an output of our simple C program:

output

Some of the applications of a stack data structure in Computer Science are:

1. Stack Memory Management

2. Text Parsing

3. Expression Evaluation

4. Backtracking Algorithms

For more resources on the applications of the stack data structure see the following: Stack Applications

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>