Stack in Data Structures

The word stack is commonly used in general English to address a pile of objects placed vertically. Let us take a few examples, like a pile of coins, a pile of books, or even plates. This pile of objects has the first added things first and the last added things at the end, basically also known as first in, first out. This arrangement is helpful to easily insert objects and pick one.

In this blog, the reader will understand further how stack is related to data structures and its various applications in real life.

What Is a Stack?

Stack is a linear type of data structure that is based on the principle FILO (First In, Last Out). The elements can be added and deleted from one end of the stack. A stack is an abstract data type (ADT) that refers to the set of data values and associated operations, which are specified accurately and are independent of its implementation. Stack ADT tells us how to do a particular task and gives a blueprint of the problem. The stack consists of functions like PUSH (inserting elements), POP (deleting elements), and PEEK.

Now, we shall look into how these functions are used in the stack.

Stack Operations

In general, as discussed before, we have two main operations in the stack, i.e., Push and Pop.

Push

In a push operation, we can insert elements into the stack from one end. We should assign a variable called top. The top variable always points to -1 initially. There are two conditions for pushing an element into the stack.

Firstly, if the stack is full or the variable top contains the value maximum size of the stack -1, then the stack is said to be overflow, and no more elements can be added to it.

Secondly, if the stack is empty or the variable contains the value -1, then we can add elements to the stack. The top value changes to top +1 whenever we add an element.

Let's take a look at the pseudo-code of the push operation,

void push(){
    //declare a varaibale to store element
    if(top == MAXSIZE - 1)
       // stack is overflow!
    else {
       // store the element
       top = top +1;
    }
}

Pop

Pop is an operation used to delete elements from the stack. Let the top variable point to -1 initially. There are, again, two conditions for deleting elements from a stack.

Firstly, if the stack is empty or the variable top contains value -1, then the stack is considered underflow, and there are no elements to delete.    

Secondly, if the stack is not empty, then the top decreases by 1.        

top = top-1

Pseudo code to implement pop operation in the stack can be understood from below.

void pop() {
     if(top == -1)
       //stack is underflow.
     else
       top = top -1;
}

Implementation of stack program using c:

#include <stdio.h>

int top =-1,n,stack[10];
void push();
void pop();
void show();
void main(){
    int choice;
    printf("Enter number of elements\n");
    scanf("%d", &n);
    printf("Stack operation\n");

    while(choice !=4){
      printf("choose one option \n");
      printf("\n1.push\n2.pop\n3.show\n4.exit");
      scanf("%d", &choice);

    switch(choice)
    {
        case 1:
            push();
            break;
        case 2:
            pop();
            break;
        case 3:
            show();
            break;
        case 4:
            printf("Exiting...\n");
            break;
        default:
        printf("Invalid choices\n");
    }
  }
}
    void push()
    {
        int val;
        if(top == n-1)
            printf("overflow");
        else {
            printf("enter number\n");
            scanf("%d", &val);
            top = top +1;
            stack[top] = val;
        }
    }
   void pop()
    {
        if(top == -1)
            printf("underflow\n");
        else
            top = top -1;
    }

    void show()
    {
      if(top == -1)
         printf("empty stack");
      else{
        for(int i=top;i>=0;i--)
          printf("%d", stack[i]);
      }

      
    }

Once we run the above code, the output is as follows:

Applications of the Stack

We already know that stack is important in data structures, but how do we use it? 

The commonly known applications:

• Expression Evaluation
• Expression Conversion
• Backtracking
• Function Call
• Parentheses Checking
• String Reversal
• UNDO 

Conclusion

The concept stack is very useful in data structures. Hope this blog has given you a clear picture of the stack. Do leave a comment below giving feedback.

Thank you.