Stack

Stack Implementation

Pinterest LinkedIn Tumblr

Data structure Description

A stack is a basic data structure that insert and remove the items using last in first out (LIFO) strategy. The stack is a very powerful data structure. The stack can used when add or remove the element using last in first out order.

Algorithm Explanation

Stack supports push and pop operations.
Push operation adds the item to the array.
Pop operation removes the item from an array.
Push and pop operation use index to move positions.
The stack data structure can implement using an array and linked list.

Source Code

package com.dsacode.DataStructre.stack;
import java.util.Arrays;
import java.util.Stack;
  
public class StockSpanProblem {
     static void calculateSpan(int price[], int n, Integer[] s)
    {
       Stack < Integer > st = new  Stack< Integer >();
       st.push(0);
      
       s[0] = 1;
      
 
       for (int i = 1; i < n; i++)
       {
       
           while (!st.empty() && price[st.peek()] < price[i])
             st.pop();
      
          s[i] = (st.empty())? (i + 1) : (i - st.peek());
      
          st.push(i);
       }
    }
      
    static void printArray(Integer[] s, int n)
    {
        for (int i = 0; i < n; i++)
            if(i==n-1)
                System.out.print(s[i] +"]");
            else
                System.out.print(s[i] +", ");
    }
     
    public static void main(String[] args) {
 
        int price[] = {100, 80, 60, 70, 60, 75, 85};
        System.out.println("7 days prices of stack:" + Arrays.toString(price) );
         
         Integer []S = new Integer[price.length];
          
         calculateSpan(price, price.length, S );
          
         System.out.print("Print the calculated span values:[");
            printArray(S , price.length);
 
    }
 
}
 

Output

Push :12
Push :9
Push :24
Pop :24
Pop :9
Pop :12

Source Explanation

The constructor initializes the stack Array and capacity.
Push operation adds element to the stack. If the stack capacity reaches maximum stack size, It double the size.
Push operation removes the element from the stack.
Pop operation checks the size. If it is empty, it does not remove anything. Otherwise, it remove the last Position and returns the element.
Peek returns the top position without remove the element in stack array.

Complexity

OperationsBest CaseAverage Caseworst Case
SearchO(n)O(n)
InsertionO(1)O(1)
DeletionO(1)O(1)

Real Applications

  1. When recursive function execute
  2. Balance the symbol
  3. Infix to Postfix
  4. Infix to Prefix
  5. Reverse Polish notation
  6. Take filled items from refrigerator

Reference

  1. https://www.cs.auckland.ac.nz/software/AlgAnim/stacks.html
  2. http://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html
  3. http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Write A Comment