Implementing Stack Datastructure using arrays.

Stack is a way of accessing data, Last In First Out (LIFO). It has nothing to do with underlying memory structure, whether it is an array or a linked list or a tree or whatever.

If you are accessing the data in LIFO fashion, then it is a stack. Stack is an abstraction, it is a concept of accessing data.

Let us start breaking down Stack one by one.

What do we need to implement stack.

1. The size of that storage area
2. Acquire a storage area.
3. A way to track location in that memory.
4. A way to put data in that storage area
5. A way to get data from that storage area
6. A way to check, if stack is full.
7. A way to check, if stack is empty

Let us start…

#1 :- Fix  a size of storage area. [Depending on the requirement, the size can be decreased or increased, But we don’t cover that here]

Let us assume we need a storage to store 100 items.

private final int MAX_SIZE = 100;

#2 :- Acquire a memory area

private final int stack[] = new int[MAX_SIZE];

#3 :- A way to track location in that memory. We are using it as pointer to last used location. Because, the next empty location is going to be just next to it.

private int top = -1;

#4 :- A way to put data in that storage

public int push(int val) {
    if(stackIsFull()) throw new IllegalStateException("Stack is Full !!!");
    
    return (stack[++top] = val);
}

Let me explain a little bit, stack[++top] = val; – here we increase the value of location tracker i.e ++top, created in #3 requirement, to point to next empty location in that memory. Then we put the value in that location.

#5 :- A way to get data out of that memory

public int pop() {
    if(stackIsEmpty()) throw new IllegalStateException("Stack is empty!!!"); 
    return stack[top--];
}

Here, we decrease the value of location tracker to point to previous location in the memory. As this value has been read by user, then it does not need to be in the memory. Technically, it is still in the memory. And, we use to clean the removed data in production code. We are skipping that part here, to keep the code simple.

#6 :- A way to check, if memory is full.

public boolean stackIsFull() {
    return top == TOP_MAX_SIZE;
}

Here, we are comparing the value of the location tracker with the size of allocated memory. If we have reached the end of memory then that stack is full.

#7 :- A way to check, if stack is empty.

public boolean stackIsEmpty() {
    return top == -1;
}

Here, we are comparing the location tracker i.e top. With -1, as memory count in an array starts from 0. Here, we are using -1 , as a symbol for a memory location before index 0. You can use whatever value you like, you can use Integer.MIN_VALUE. It will work just fine, because index in an array can never be less than zero. 🙂

Let me put the complete working code here.

public class StackUsingArray {
    private final int MAX_SIZE = 100;
    private final int TOP_MAX_SIZE = MAX_SIZE - 1;
    private final int stack[] = new int[MAX_SIZE];
    private int top = -1;

    public boolean stackIsEmpty() {
        return top == -1;
    }

    public boolean stackIsFull() {
        return top == TOP_MAX_SIZE;
    }

    public int push(int val) {
        if(stackIsFull()) throw new IllegalStateException("Stack is Full !!!");
        return (stack[++top] = val);
    }

    public int pop() {
        if(stackIsEmpty()) throw new IllegalStateException("Stack is empty!!!");
        return stack[top--];
    }

    public static void main(String ... args) {
        StackUsingArray stack = new StackUsingArray();

        //Pushing in the stack                                                                                                                                                                 
        System.out.println("Pushing in the stack");
        for(int i = 1; i<=100; ++i) {
            System.out.printf("%d ", stack.push(i));
            if(i%10 == 0) System.out.println();
        }
        System.out.println("Stack is Full " + stack.stackIsFull());
        //popping from the stack                                                                                                                                                               
        System.out.println("Popping from the stack");
        for(int i = 1; i<=100; ++i) {
            System.out.printf("%d ", stack.pop());
            if(i%10 == 0) System.out.println();
        }
        System.out.println("Stack is Empty " + stack.stackIsEmpty());
    }
}

This is the output, I got after running it.

First, the values are pushed from 1 to 100, then the values are popped from 100 to 1. The printed values are in reverse order.

Pushing in the stack

1 2 3 4 5 6 7 8 9 10 
11 12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 49 50 
51 52 53 54 55 56 57 58 59 60 
61 62 63 64 65 66 67 68 69 70 
71 72 73 74 75 76 77 78 79 80 
81 82 83 84 85 86 87 88 89 90 
91 92 93 94 95 96 97 98 99 100 

Stack is Full - true

Popping from the stack

100 99 98 97 96 95 94 93 92 91 
90 89 88 87 86 85 84 83 82 81 
80 79 78 77 76 75 74 73 72 71 
70 69 68 67 66 65 64 63 62 61 
60 59 58 57 56 55 54 53 52 51 
50 49 48 47 46 45 44 43 42 41 
40 39 38 37 36 35 34 33 32 31 
30 29 28 27 26 25 24 23 22 21 
20 19 18 17 16 15 14 13 12 11 
10 9 8 7 6 5 4 3 2 1 

Stack is Empty - true