Stack – Implementation

Introduction

Stack is a very common data structures which will return in the element stored in a Last In First Out fashion.

Applications

  • Expression Evaluation
    • Post fix /In fix
  • Backtracking
    • Finding Paths
    • Game Playing
  • Exhaustive search
  • Memory Management
  • Depth First Search traversal

Here we will see how to implement a stack using Array and Linked List

Array Implementation

1

We can implement array with fixed capacity(bounded) or with dynamically allocating the memory for storing the elements(unbounded). If the size reaches the maximum element the size is doubled and the elements are copied to a new array

class ArrayStack{
    
    int size; // size of the array
    int[] array;
    int head; // head pointer
    int max; //max capacity
 
//initialize size, max and the internal array
  public ArrayStack(int max){
      this.array = new int[max];
      this.head = 0;
      this.size = 0;
      this.max = max;
  }
  
//return the current size
  public int getSize(){
      return size;
  }

//return true if the size == 0
  public boolean isEmpty(){
      return size == 0;
  }

//return the head of the stack
    public int peek(){
      return head;
  }  

//check for empty
//if not then update the head with the last array element that was inserted
//set the array element to 0 (reset)
//return the head
  public int pop(){
      if(!isEmpty()){
          head = array[--size];
          array[size] = 0;
          return head;
      }
          System.out.println("No Element");
          return -1;

  }

//set the array to the value inserted if the size is not equal to max
/set the head to last inserted element
//increment the size
  public void push(int val){
      if(size != max){
          array[size] = val;
          head = array[size];
          size++;
      }
      else
          System.out.println("Reached max element");
          //------------------Dynamic Allocation Code - START----------------
          //max = (max * 2) + 1; //simply doubling the size (dynamic allocation)
          //int[] tempArray = new int[max];
          //for(int i=0;i<size;i++){
          //  tempArray[i] = array[i];
          //}
          //array = tempArray;
          //array[size] = val;
          //head = array[size];
          //size++;
          //------------------Dynamic Allocation Code - END----------------
  }
}

public class ArrayStackLimitedImpl {
    public static void main(String[] args) {
       ArrayStack s = new ArrayStack(3);
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(4);
       s.push(4);
       s.push(4);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
    }
}

Linked List Implementation

1

class ListNode{
  ListNode next;
  int val;
  
  ListNode(int val){
    this.val = val;  
  }
  
}

class LinkedListStack{
    ListNode tail;
    int size;
   
//get the current size of the stack 
    public int getSize(){
      return size;
    }

//return true if size == 0
  public boolean isEmpty(){
    return size == 0;
  }

//return the top element  
  public int peek(){
    return tail.val;
  }

//pop the last inserted element if not empty
//store the top element by peek
//top will be pointing to the next element
//decrement the size
//return the top value  
  public int pop(){
    if(!isEmpty()){
      int val = peek();
      tail = tail.next;
      size--;
      return val;
    }
      System.out.println("No Element");
      return -1;

  }

//push the new element
//set the new node's next element as the previous top element
//set current top element as the new node
//increment the size
  public void push(int val){
    ListNode newNode = new  ListNode(val);
    newNode.next = tail;
    tail = newNode;
    size++;
  }
}

public class YourClassNameHere {
    public static void main(String[] args) {
       LinkedListStack s = new LinkedListStack();
       s.push(1);
       s.push(2);
       s.push(3);
       s.push(4);
       System.out.println(s.pop());
       s.push(7);
       s.push(8);
       s.push(9);
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       s.push(54);
       System.out.println(s.peek());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
       System.out.println(s.pop());
      
    }
}

Test cases

  • Cannot pop if the stack is empty
  • In bounded stack if the size of the stack reaches max then it will not allow pushing further elements to the stack
  • peek should not pop the element

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: