Stack implementation in java using default integer array with auto resize

Question

So I am trying to create a more time efficient stack implementation in java but I don't know how to make it work faster. Here is my code:

import java.util.Scanner;

public class A {

    public static void main(String[] args) {
        int[] n = new int[0];

        Scanner scan = new Scanner(System.in);
        loop: while(true){
            String stringy = scan.next();
            switch(stringy){
                case "push":
                    int x = scan.nextInt();
                    n = push(x, n);
                    System.out.println("ok");
                    break;
                case "pop":
                    n = pop(n);
                    break;
                case "exit":
                    System.out.println("bye");
                    break loop;
                case "size":
                    System.out.println(n.length);
                    break;
                case "back":
                    back(n);
                    break;
                case "clear":
                    n = clear();
                    System.out.println("ok");
                    break;

            }
        }

    }
    static int[] push(int n, int[] x) {
        int[] z = new int[x.length + 1];
        for (int i = 0; i < x.length; i++){
            z[i] = x[i];
        }
        z[x.length] = n;
        return z;
    }


    static int[] pop(int[] x){
        int z[] = new int[x.length-1];
        for(int i = 0; i < z.length; i++){
            z[i] = x[i];
        }
        System.out.println(x[x.length-1]);
        return z;
    }
    static void back(int[] x){
        System.out.println(x[x.length-1]);
    }
    static int[] clear(){
        int x[] = new int[0];
        return x;
    }
}

Brief explanation: Program takes values from scanner. And depending on a word that was entered, program proceeds with the corresponding instructions like push, pop, back... And it prints out the expected values to console with ok. Everything so far works properly as expected except the performance. As you can see, in methods push and pop, my program creates new arrays and copies the values of the taken array which is x and adds 1 index with a pushed value or removes the popped value. This approach seems rather slow and inefficient. I couldn't find a more efficient way of doing that without picking arraylist or other classes from java library. But I have to use default integer arrays. And are there any other issues worsening the perfomance of the program? How can I make my program work faster?

what you mean by "faster"? how many numbers do you want to push? the only thing/my IDE complains about: "Use System.arraycopy()", for push: System.arraycopy(x, 0, z, 0, x.length); (instead of the for loop), for pop: System.arraycopy(x, 0, z, 0, z.length); (instead of the for loop;) — xerx593
– xerx593, Commented Nov 12, 2021 at 12:17
Every time one element can be pushed into the array. My goal is using generic array, no arraycopy or importing other classes from libraries and making it work faster than it is now — Aitsuken
– Aitsuken, Commented Nov 12, 2021 at 12:29
when using "generic array" you would also have to distinguish at: scan.nextXXX(push) ...but arraycopy works on all types of arrays (and is preferable to a loop).. — xerx593
– xerx593, Commented Nov 12, 2021 at 12:41

Bahij.Mik · Accepted Answer · 2021-11-12 12:46:04Z

You can create member variables outside your method to keep track of the array and what is the size of it (similar to how array lists are implemented), no need to recopy the whole array everytime you need to pop/push.

You will need 2 variables, the array itself and the size (which will expand/shrink based on what you do)

You're better off creating a new class, I am gonna name it CustomStack

public class CustomStack
{
    private int[] elements = new int[10];  // instantiated with a size of 10
    private int size;  // To track how many ints we currently have
....
}

You can now access the array and the size within the methods.

So first you need the push method, but wait there is a trick here, what if I already reached the max size of the array? (i.e: 10 numbers are already inside the array), well you need to cater for this, a known way to tackle this is create a new array with double the size of the current array and then copy all the values to the new array.

private void validateArraySize()
{
    if (size == elements.length)
    {
        int[] temp = new int[elements.length * 2]; //double the size
        System.arraycopy(elements, 0, temp, 0, elements.length);  // copy the array
        elements = temp; //set our member variable array to the new array
    }
}

And the push method:

public void push(int n)
{
     validateArraySize(); // The previos method to check if we can safely insert the value
     elements[size] = n;
     size++;
}

Regarding the pop method, it is very straight forward, you just need to check if there are any integers inside the array:

 public int pop()
 {
     int valueRemoved = 0;
     if (size == 0)
        System.out.println("No elements found to pop");
     else
     {
         valueRemoved = elements[size - 1]; //Get the last value
         elements[size - 1] = 0;  // remove the last value
         size--;
      }
      return valueRemoved; // return removed value
 }

The whole class will look like this:

public class CustomStack
{
    private int[] elements = new int[10];
    private int size;

    public void push(int n)
    {
        validateArraySize();
        elements[size] = n;
        size++;
    }

    private void validateArraySize()
    {
        if (size == elements.length)
        {
            int[] temp = new int[elements.length * 2];
            System.arraycopy(elements, 0, temp, 0, elements.length);
            elements = temp;
        }
    }

    public int pop()
    {
        int valueRemoved = 0;
        if (size == 0)
            System.out.println("No elements found to pop");
        else
        {
            valueRemoved = elements[size - 1];
            elements[size - 1] = 0;
            size--;
        }
        return valueRemoved;
    }

    public int getSize()
    {
        return size;
    }

    public void back()
    {
        if (size == 0)
            System.out.println("No elements found");
        else
            System.out.println(elements[size - 1]);
    }

    public void clear()
    {
        elements = new int[10];
    }
}

Your main method will become:

 public static void main(String[] args) {
        CustomStack customStack = new CustomStack();

        Scanner scan = new Scanner(System.in);
        loop: while(true){
            String stringy = scan.next();
            switch(stringy){
                case "push":
                    int x = scan.nextInt();
                    customStack.push(x);
                    System.out.println("ok");
                    break;
                case "pop":
                    int val = customStack.pop();
                    System.out.println(val + " is popped");
                    break;
                case "exit":
                    System.out.println("bye");
                    break loop;
                case "size":
                    System.out.println(customStack.getSize());
                    break;
                case "back":
                    customStack.back();
                    break;
                case "clear":
                    customStack.clear();
                    System.out.println("ok");
                    break;

            }
        }

@PBP_EnderLord hey man, how are you bench marking this? this will definitely be faster since we are only copying the array when we are required to, meaning the push and pop will most of the time be constant O(1)
That is the problem, I can't see how it benches the program. But the time difference is miniscule, your proposition is slower on average by ~0,001-0,0015 seconds in test cases

Collectives™ on Stack Overflow

Stack implementation in java using default integer array with auto resize

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related