Leave a comment

What is stack? How to implement it?

Most of us already know that Stack is a data structure which allow us to process data in a particular manner called Last in First out, which means that the data stored last will be processed first. For an example if we have to store data 1 2 3 4 5, 1 will be in bottom of stack and 5 will be on top of stack. Stack does not have any operation which allow us to read data which is not on top of stack. At any point of time we have access to the data stored at top.
We can think of an array which allow us to access the data stored at highest index at any moment.

Basically, concept of stack came into picture because of post decision kind of problem. Huhh !!! What is this Post Decision problems? Let say you have boxes from 1 to 20. Each box has 2 numbers hidden in it. Once you jump to a box, numbers will be displayed to you. Displayed numbers are the numbers of those boxes on which you can jump next. If you are on a box and hidden numbers are 11 and 14, so either you can jump to 11 or 14 number box. Now the problem is, you will be placed randomly at any box and you need to find out the minimum number of jumps required to reach at last box which is 20.
So, how will you do that? Of course you will have to try all possible solution to find the solution. But, the question is how will you try all the combination? Let’s start thinking, at very first box you have two another options 11 and 14 where you can jump, and for finding the minimum jumps you should know the minimum jumps required from both of the next boxes which are 11 and 14. Same will be true if you are on box 14 or 11. Once you calculate the minimum number of jumps for 14 and 11, whichever will be the minimum, you will choose that and add 1, that will be your final solution.
You can see that to calculate the minimum number of jumps, you must know the minimum number of jumps required from next boxes first. Which means you have to postpone your calculation until you find the next solution because your final solution depends upon that. This is called post decision problems. In post decision problem, solution of the given problem depends upon sub problems and solution of the sub problem depends upon sub sub problems. Normally you see recursive solution of problems like finding a fibonacci number or factorial of number, you have to go deeper and reach till a termination condition.

Algorithm to find factorial of a number is:
factorial(number){
    if(number == 1 || number ==2)
        return number;
        return number*factorial(number-1);
}

To calculate factorial of five you have to calculate factorial of 4 and to calculate factorial of 4 u need to calculate factorial of 3 and so on. You must be wondering where is stack gone. Here the stack comes into picture. Whatever programming language you use, it will use stack internally to hold the call to the same method. Internally it will be like this:

fibonacci

We have reached to a termination condition, this call will be removed from top of stack and result will be sent back to next top which is factorial(3).

Stack is the best data structure for this kind of problems as it maintains a history kind of your calculation. You can store the current state of your calculation and jump to the next calculation. Once you are done with a calculation, you can return the result to calculation stored at top of stack and once that calculation is completed, remove it from top and return the result to next top. It is something like this:

Oh I am stuck with my calculation because I don’t know what is the result of this sub problem. Let’s store this calculation somewhere and find the result for sub problem first. Does it make sense?

Stack comes up with 3 operation:

  1. peek(): will read and return whatever is on top of stack
  2. pop(): will remove the top of stack and return
  3. push(): will place the input on top of stack.

Here you go for implementation. I have implemented a stack which will deal with integers. This is just a very simple and basic implementation for understanding.


public class Stack {
    private int top = -1;
    private int[] elements;
    private int length;
    public Stack(int size){
        length = size;
        elements = new int[size];
    }
    public Integer peek(){
        if(top == -1) {//stack is empty - stackunderflow
            System.out.println("Stack is empty. Nothing to return.");
            return null;
        }
        return elements[top];
    }
    public Integer pop(){
        if(top == -1) {//stack is empty
            System.out.println("Stack is empty. Nothing to return.");
            return null;
        }
        Integer item = elements[top];
        top--;
        return item;
    }
    public void push(int num){
        if(top == length-1){ //stack is already full - stackoverflow
            System.out.println("Stack is already full.");
            return;
        }
        top++;
        elements[top] = num;
    }
}

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: