Stack Data Structure

The stack is a linear data structure which follows the last in first out (LIFO) principle.

Stack application in the browser

Let’s search “what is stack” in google and visit any of the link listed in the google search.

Suppose the link we have clicked is not we expected, then we will come back to the home page by pressing the browser back button.

What is the purpose of that back button?

It will locate us on the last visited page.

Example

First page: www.google.com

Second page: www.somepage.com/stack

If we press the back button on the second page, we will again go back to www.google.com result page.

Browser back button uses the Last In First Out (LIFO) principle.

Using stack data structure, we can track the last inserted data.

Let's implement stack data structure

Requirements

Array

int arr[size];

To point the index of a last inserted data.

int top;

isStackFull()

This function will return true(1) if the stack is full.

Otherwise, it will return false(0).

int isStackFull();

push(data)

push function will insert the data on top of the stack.

Let's take an integer data.

void push(int);

isStackEmpty()

This function will return true(1) if the stack is empty.

Otherwise, it will return false(0).

int isStackEmpty();

pop()

It will retrieve the last inserted data.

void pop();

Let's Initialize the variables

we are going to initialize top as -1.

top = -1 indicates the empty stack.

Let's assume the array size as 5.

push

To push data into the stack,

Check if the stack is full.

If its full

we can't insert data.

Otherwise

increment the top variable by 1 and push the data.

Example

i) push 10

ii) push 13

iii) push 5

iv) push 26

v) push 100

vi) push 78

push function

int isStackFull()
{
    if(top == size - 1)
        return 1;
    return 0;
}

void push(int val)
{
    //check if the stack is full
    if(isStackFull())
        printf("Unable to push %d as the Stack Is Full\n",val);
    else
    {
        //increment top by 1 
        ++top;
        //push the element into stack 
        arr[top]=val;
    }

}

pop

To pop the data from the stack,

Check if the stack is empty

if it's empty

We can't pop an element from the empty stack. So if top == -1, we should not do anything.

Otherwise

Pop the element and decrement the top value by 1.

Example

i)pop

ii)pop

pop function

int isStackEmpty()
{
    if(top == -1)
        return 1;
    return 0;
}

void pop()
{
    //check if the stack is empty
    if(isStackEmpty())
        printf("Stack Is Empty\n");
    else
    {
        //print the popped element
        printf("Popped element = %d\n",arr[top]);
        //decrement top by 1
        top--;
    }

}

Let's push one more element to stack and make it clear.

push 250

Implementation of the stack data structure using array

Example

  /*
   * Program :Stack data structure using array
   * Language : C
   */

  #include<stdio.h>

  #define size 5

  int arr[size];
  int top = -1;         //-1 indicates empty stack

  int isStackFull()
  {
      if(top == size - 1)
          return 1;
      return 0;
  }

  void push(int val)
  {
      //check if the stack is full
      if(isStackFull())
          printf("Unable to push %d as the Stack Is Full\n",val);
      else
      {
          //increment top by 1 
          ++top;
          //push the element into stack 
          arr[top]=val;
      }

  }

  int isStackEmpty()
  {
      if(top == -1)
          return 1;
      return 0;
  }

  void pop()
  {
      //check if the stack is empty
      if(isStackEmpty())
          printf("Stack Is Empty\n");
      else
      {
          //print the popped element
          printf("Popped element = %d\n",arr[top]);
          //decrement top by 1
          top--;
      }

  }

  int main()
  {
       push(10);
       push(13);
       push(5);
       push(26);
       push(100);
       push(78);       //we can't push 78 as the stack is full
       pop();          //100
       pop();          //26
       pop();          //5
       pop();          //13
       pop();          //10
       pop();          //unable to pop as the stack is empty
       return 0;
  }

Real life applications of Stack Data Structure

1.Undo and Redo in games & text editors

2.Browser back button

3.Recursion