Mastering Stacks: A Step-by-Step Guide to Data Structure Learning

In this blog post, we will be learning, implementing, and having a thorough introduction to stacks data structure using the C programming language.

Before understanding the stacks data structure, you should have a good understanding of arrays and linked lists because only with the help of these two data structures can we implement stacks.

In general, for implementing any data structure, whether it is stacks, queues, trees, etc., we have to use either arrays or a linked list.

If you can predict the size of the data structure (how much memory it will need) then you can use an array, otherwise, you can dynamically allocate the memory using linked lists.

Concept of Stacks Data structure

Consider a stack as a series of plates kept one above the other, vertically, from bottom to top.

Let’s say there are five plates, P1, P2, P3, P4, and P5, and you want to organize them in the form of a stack (i.e. putting them one above the other), then how would you do it?

Obviously, you will take the first plate, P1, and on top of it, you will put the plate P2, and then the next plate, and so on, until you put the last plate on, i.e. P5.

This whole thing forms a stack of plates which is illustrated by the following diagram.

And, whenever you want to access or take out a particular plate, you have to first see if the plate you want to access is at the top or not.

A stacks data structure is also known as last-in-first-out (LIFO) meaning the element which is inserted last into the stack will be removed first from the stack.

Operations on the Stack

Push: To insert an element on to the stack.
Pop: To delete an element from the stack.

Implementation of a Stack

There are two ways in which we can implement the stacks data structure.

Using an array

In this representation, we will be implementing the stack using an array whose index starts with 0.

Before inserting or deleting an element, there are two conditions that we have to check, the first is the overflow condition and the second is the underflow condition.

The overflow condition simply checks whether the stack is full or not. If it is already full, then you can’t insert a new element on to the stack.

The underflow condition checks whether the stack is empty or not because if the stack is already empty and if we are trying to delete an element that does not even exist as the stack is already empty, we will definitely get an error.

These are some corner case conditions that we have to check to make sure that our program works perfectly in any situation without any errors.

// Checking the Overflow condition & pushing the element onto the stack 
void push (int item) {

    // MAX – 1 represents the top of the stack
    // Checks if stack full or not    
    if (top == MAX - 1) {
        printf(“Overflow! The Stack is already full.”);
    }
    else {
        top = top + 1;
        Stack[top] = item;
    }
}


// Checking the Underflow condition & deleting the elements from the stack
int pop () {
    int temp;

    // Checks if stack is empty or not
    if (top == -1) {
        printf(“Underflow! The stack is already empty.”);
        return -1;
    }
else {
    temp = stack[top]; // Storing current value of stack in temp
    top = top – 1; // Decrementing the pointer
    }  
return temp;
}

In the stack, when we pop an element, we are not actually deleting the element from the stack as we do in a linked list. Here, we are only decrementing the top pointer and the value inside that particular stack block will still be there.

The time complexity for both insertion and deletion of an element in an array takes O(1), i.e. constant time.

Using the linked list

In this representation, we will be implementing the stack data structure using a linked list.

As we know, the linked list consists of various nodes and each node has two things. One is the data and the other is the pointer that points to the next node.

But, before inserting an element, we first have to create a new node and then add that node to a linked list. Here, also, we have to check the overflow and underflow conditions.

// Struct of a single node in a linked list 
struct node { 
  int i; 
  struct node *link; 
}; 

// Inserting an element 
void push (int item) {

  //Creating a single node 
  struct node *p = (struct node *) malloc(sizeOf(struct node)); 

  // Checking for Overflow condition 
  if (p == NULL) { 
    printf("Error of malloc."); 
    return; 
  }

  p -> data = item; 
  p -> link = head; 
  head = p; 
} 

// Deleting an element 
void pop () { 
  int item; 
  struct node *p; 

  // Checking the Underflow condition 
  if (head == NULL) { 
    printf("Underflow"); 
    return -1; 
  }

  item = head -> i; 
  p = head; 
  head = head -> next; 
  free(p); 
}