STACKS - CODE

JAVA PYTHON GO KOTLIN C# RUBY C++ Java Script

Implementing Stack in Java using Arrays

Although 'Stack' Data Structure is already defined in java's 'java.util package'. But for the sake of learning, we will define our own Stack class and define all the methods there.

Example :

public class ArrStack {

    public static final int SIZE = 10;

    private int stackArray[];
    private int tp = -1;



    public ArrStack(int size) {

        stackArray = new int[size];
    }

    public boolean push(int i) {

        if (size() == SIZE) {
            System.out.println("Stack Overflow");
            return false;
        }
        else {
            stackArray[++tp] = i;
            return true;
        }
    }

    public int pop() {
        int element;
        if (isEmpty()) {

            System.out.println("Stack is Empty");
            return -1;
        }
        else {
            element = stackArray[tp];
            stackArray[tp--] = 0;
            System.out.println("The element "+element+" is popped out of the Stack");
            return element;
        }
    }

    public int top() {

        if (isEmpty()) {
            System.out.println("Stack is Empty");
            return -1;
        } else {
            System.out.println("The top element is "+stackArray[tp]);
            return stackArray[tp];
        }
    }

    public int size() {

        return (tp+1);
    }

    public boolean isEmpty() {

        return (tp<0);
    }

    public static void main(String args[]) {

        ArrStack arrStack = new ArrStack(SIZE);

        arrStack.push(10);
        arrStack.push(20);
        arrStack.push(30);

        arrStack.top();

        arrStack.pop();
        arrStack.pop();
        arrStack.pop();
    }
}

Output :

The top element is 30
The element 30 is popped out of the Stack
The element 20 is popped out of the Stack
The element 10 is popped out of the Stack

Code Explanation for Stack

As we know the most important operations/methods of Stack are Push and Pop. However, there are other methods that we will be using here.

So, we have the below methods :

boolean push(int element)

The 'push(..)' method puts an element into the Stack.
int pop()

The 'pop()' method takes an element out of the Stack.
int top()

The 'top()' method returns the topmost element of the Stack.
int size()

The 'size()' method returns the size of the Stack.
boolean isEmpty()

The 'isEmpty()' method returns true if an array is empty and returns false if the array is not empty.

So, at first, we define the array where we will be storing the elements of the Stack.

private int stackArray[];

Also, we have defined a constant called 'SIZE' where we have defined the size of the array.

public static final int SIZE = 10;

And, then we have initialised the variable 'tp' with '-1'.

private int tp = -1;

The variable 'tp' always points to the top element. Initially 'tp' is '-1' because it is not pointing to any element yet. When it becomes '0', it should be pointing to the 0th element.

Now, let us go to the 'main(..)' method and see the Stack in action.

So, we have represented the Stack as an Array,

int stackArray[];

And initialised the Array in the Constructor.

public ArrStack(int size) {

    stackArray = new int[size];
}

So, initially we have an empty Stack.

Then we try to push the element 10 into the Stack

arrStack.push(10);

So, the 'push()' method is called,

public boolean push(int i) {

    if (size() == SIZE) {
        System.out.println("Stack Overflow");
        return false;
    }
    else {
        stackArray[++tp] = i;
        return true;
    }
}

Now, the 'push()' method calls the 'size()' method to check the size of the Array.

public int size() {

    return (tp+1);
}

The 'size()' method returns 'tp+1'.

And if we see the value of variable 'tp', it is '-1' initially.

So, 'size()' method returns 'tp+1', i.e. -1+1 = 0.

So, we are back in the 'push()' method with the value '0' returned from 'size()' method.

Now, in the 'if' statement, we find the condition,

if (size() == SIZE)

But in this case 'size()' returned '0' and 'SIZE' is initialised with '10'.

So, we come to the 'else' part,

else {
    stackArray[++tp] = i;
    return true;
}

And in the else part we increment the value of the variable 'tp' first. As 'tp' points to the top element.

So, 'tp' is '-1' initially. After incrementing it becomes '0'.

Now, the below line,

stackArray[++tp] = i;

Inserts the element '10'(As 'i' is 10) to the 0th location of the Array 'stackArray'.

Then we try inserting the element 20 using the 'push(...)' method again.

arrStack.push(20);

Similarly, 'push(...)' method is called,

public boolean push(int i) {

    if (size() == SIZE) {
        System.out.println("Stack Overflow");
        return false;
    }
    else {
        stackArray[++tp] = i;
        return true;
    }
}

Now the value of 'i' is 20.

Same way as above, the 'if' condition checks, if the total number of elements in the array (Determined by the 'size()' method) is equal to the size of the array.

In this case the total number of elements in the array is just one i.e. 10(And we are going to insert 20). And the size of the array is 10.

So, we come to the else part.

else {
    stackArray[++tp] = i;
    return true;
}

The line in the else part,

stackArray[++tp] = i;

Increments the variable 'tp' first.

The current value of 'tp' is '0'. As 'tp' is pointing to the first element.

After incrementing 'tp', it becomes '1'. And in 'stackArray[1]', we insert 20.

And just remember 20 is the top element now. So, 'tp' would be pointing to it.

After that, we try inserting the element 30 using the 'push(...)' method again.

arrStack.push(30);

And, as usual, 'push(...)' method is called and the element '30' is inserted into the Stack.

Next, we try getting the top element of the stack by calling the 'top(..)' method.

arrStack.top();

And as we know the variable 'tp' always points to the top element. So, if we could get the value of the variable 'tp', we could get the top element.

And exactly, the same thing is done in the 'top()' method.

public int top() {

    if (isEmpty()) {
        System.out.println("Stack is Empty");
        return -1;
    } else {
        System.out.println("The top element is "+stackArray[tp]);
        return stackArray[tp];
    }
}

In the 'top()' method, we check if the array is empty or not.

if (isEmpty()) {
    System.out.println("Stack is Empty");
    return -1;
}

And if the array is not empty, we come to the 'else' part. Where the value of the top position is returned.

return stackArray[tp];

Say, for example, the value of 'tp' is 2 currently. So, 'stackArray[tp]' would return '30' as the top element.

Next, we try popping the elements from the Stack. One at a time.

So, when we run the first 'pop()' method.

arrStack.pop();

The 'pop()' method is called.

public int pop() {
    int element;
    if (isEmpty()) {

        System.out.println("Stack is Empty");
        return -1;
    }
    else {
        element = stackArray[tp];
        stackArray[tp--] = 0;
        System.out.println("The element "+element+" is popped out of the Stack");
        return element;
    }
}

So, as usual we check if the array is empty or not.

if (isEmpty()) {

    System.out.println("Stack is Empty");
    return -1;
}

Now, if the array is not empty, we come to the else part.

else {
    element = stackArray[tp];
    stackArray[tp--] = 0;
    System.out.println("The element "+element+" is popped out of the Stack");
    return element;
}

The operation is quite simple,

We take the current top element in the 'element' variable.

element = stackArray[tp];

i.e.

 element = 30.

Then we replace the current top element with 0. And at the same time, reduce the value of 'tp' by 1. So that 'tp' points to the second element.

Similarly, after running 'pop()' method twice,

arrStack.pop();
arrStack.pop();

Both the elements 20 and 10 are popped out of the Stack.

❮❮ PREV NEXT ❯❯