Understanding Stack In Data Structure

As we know Data Structure is a way to storing and organize data into memory, there are many different algorithms available that has their own benefits so as per the demand or requirement we choose any way to store data, STACK is one of them.

Please click on the link given below to introduction of Data Structure, advantages, need, types of data structures, and different operations detail.

Introduction of DataStructures

Here we will discuss about stack data structure in detail.

1.

Stack comes in non-primitive category and it is Linear Lists type data structure. Linear list means data comes in sequential order.

2.

Stack works with predefined capacity that is way it’s also comes in static data structure’s category.

3.

In Stack every element store on top that is why it is also known as LIFO-Last in First out.

4.

As the element always go on top so element will remove from top as well, Insertion and deletion of element allow from only one end is TOP.

5.

Stack has two states Overflow – when stack is full and Underflow 
when stack is empty.

Operations Of Stack -

      Let’s discuss about the operations that we perform with Stack

      push ()   

This operation is to insert data element into stack from top.

      pop ()

This operation is to remove data element fromstack from
       top.

      isEmpty ()  

This operation is to check underflow state of stack either

stack is empty or not.

     

      isFull ()

This operation is to check overflow state of stack either stack is full or not.

                peek ()

This operation is to get top element data from stack, it does not remove top of stack.

How Stack Works – Implementation –

As of now we know that stack is the Data Structure that organizes data values in sequential order always push and pop data on top in Last In First Out form.

Next thing comes in mind how actually it works, let’s understand stack functions implementation using pseudo codes.

     push Implementation

We are assuming that we have list of 5 elements and we want to push or store data element into stack, let’s explain by using pseudo codes.

.

1.   Assuming stack capacity or size is of 5 elements, as we know stack push data at end level so top is the end index of  stack or it represents top element index, before pushing any data we must check that stack is full or not, if not full then push data into memory. If stack is full then will show Overflow message to user.

stack_size =5 

If (top = satck_size )

then  “Stack is Overflow, can’t add more element”

2.   If stack is not full then push data into stack, data would be identify  by top, initially top is set as -1 , with every push operation top would increase by 1.

otherwise

top = top + 1

stack [top]= element

     

pop Implementation

We are assuming that we have 5 elements in stack and we want to pop or remove data element from stack, let’s explain by using pseudo codes.

1.   Before removing data from stack, first check stack is empty or not, if stack is empty then will show underflow message to user.
   Top represents index of top element of stack, if top is -1 i.e. there is no element available in stack.

If ( top = -1 )

      then “Stack is underflow, can’t remove element ”

2.   If stack is not empty then 2nd last element would become new top in stack. 

otherwise

top = top-1 //top-1 becomes current top in stack

        

        

    
















     isEmpty Implementation

As the function name suggest, isEmpty() method checks data availability in stack. This is Boolean method i.e. it returns true if stack is empty otherwise returns false.

top         is showing number of elements in stack, initially it set as -1 after every push it is increase by 1 and after every pop it decrease by 1.

   if ( top = -1 )

   then “ Stack is empty ”

     isFull Implementation

As the function name suggest, isFull() method checks storage limit in stack or either stack has reached to its storage limit or not.

stack_size    is showing storage capacity of stack

top          is showing number of elements in stack, initially it set as   -1 after every push it is increase by 1 and after every   pop it decrease by 1.

                 

                  if ( top = stack_size )

                  then “ Stack is full “

peek Implementation

peek() method is to return top element of stack, first checks if stack is not empty then get top of the stack.

 top        is showing last elements of the stack, initially it set as -1 after every push current element becomes top of the stack and after every pop top-1 becomes top of the stack. Push and pop happens from one end i.e. top.

                        if ( top = -1 )

                        then “ Stack is empty “

                        otherwise

                        value = stack [top]

Stack Implementation In Java –

Let’s create a java program for stack data structure implementation, again I mention here that data structure is a way to store and organize data values into memory, there are many data structures are available with their features and benefits, we select them as per our requirement, Stack is one of them.

Let’s assume that we have list of students data and we want to store and organize them in Last-In-First-Out manner, so that every last entry would be on top.

import java.util.ArrayList;

class Student {

      String stud_name;

     

      Integer rollNo;

     

      String grade;

 

  Student (String sName, Integer rNo, String grd) {

   

    stud_name = sName;

   

    rollNo = rNo;

   

    grade = grd;

   

  }

 

} //end of student class

interface stack {

 

  public void push(Object data);

 

  public void pop();

 

  public boolean isEmpty();

 

  public boolean isFull();

 

  public Object peek();

 

} //end of stack interface

class StackImplementation implements stack {

     

      //showing indexing of stack memory

      private static int top = -1; 

     

 

      private  Object[] stackList = null;

      private static int stack_size_limit = 0;

 

      // constructer to set stack size limit

      StackImplementation (int maxStackSize) {

     

      stack_size_limit = maxStackSize;

     

      /* memory allocation for stackSize to store 
       object data */

      stackList = new Object[stack_size_limit];

     

    }

      // Push method to store data element into stack

      public void push(Object data) {

     

      if ( isFull() ) {

System.out.println("Can't push more element.");

      }

      else {      

            top = top + 1;

            stackList[top] = data;   

      }

     

    } //end of push method

      

    //Pop to remove data element from top

     public void pop() {

     

     if (isEmpty()) {   

          System.out.println("Can't remove more" 
          +"element.");   

        }

            else {

            top = top - 1;

        }

     

    } //end of pop method

       

      

     // isEmpty to check stack is empty or not

     public boolean isEmpty() {

     

         if (top == -1) {

         

           System.out.println(" Stack is in underflow(empty)" 
           +"state. ");

         

           return true;

         

        }

     

      return false;

     

    } // end of isEmpty method

 

     

      

    // isFull to check stack memory is full or not

    public boolean isFull() {

     

       if ( top == stack_size_limit - 1 ) {

       

         System.out.println(" Stack is in overflow(full)"
         + "state. ");

       

         return true;

         

        }

     

      return false;

     

    } // end of isFull method

 

     

  // peek method is to get top value from stack

  public Object peek() {

     

    if (isEmpty()) {

         

          System.out.println("Can't get top element.");

     

                  return null;

         

        }

   

      return stackList[top];

    

    } // end of peek method

} // end of implementation class

public class StackExample {

 

  public static void main(String[] args) {

   

    System.out.println("Creating student data ... ");

   

    Student s1 = new Student ("Student1",1,"A");

    Student s2 = new Student ("Student2",2,"B");

    Student s3 = new Student ("Student3",3,"C");

    Student s4 = new Student ("Student4",4,"D");

    Student s5 = new Student ("Student5",5,"E");

   

    System.out.println("Push student data into stack ... ");

   

    StackImplementation stackImpl = 
    new StackImplementation(5);

   

    stackImpl.push(s1);

    stackImpl.push(s2);

    stackImpl.push(s3);

    stackImpl.push(s4);

    stackImpl.push(s5);

   

    System.out.println("Get top of stack ...");

   

    Student studData = (Student) stackImpl.peek();

   

    System.out.println("Student data values :"+
    studData.stud_name+" ,      

    "+studData.rollNo+" , "+studData.grade);

   

    System.out.println("Pop student data from stack ... ");

   

    stackImpl.pop();

   

    System.out.println("Get top of stack ...");

   

    studData = (Student) stackImpl.peek();

   

    System.out.println("Student data values :  "
    +studData.stud_name+" ,      

    "+studData.rollNo+" , "+studData.grade);

   

  } // end of main method

  

} // end of StackExample class


In the given example you can better understand interface layer where stack interface 

that has all stack methods and stackImplementation class that is implementing all the methods. 

Here we are storing student object into stack memory, so we have student class, from main method we pass student object to the methods and all stack methods are dealing with student object.

Stack implementation layer can be used for any object, we can reuse stack data structure implementation for any other object.

Explore Other Useful Links –

Understanding Data Structure Basics