Creating a Stack class with Arrays in Java

Question

I'm trying to create a Stack in Java that uses arrays for its implementation. Below is the pop() method in my self-defined stack class

public E pop()
    {
        if(data.length == 0)
        {
            throw new EmptyStackException();
        }
        E poppedObject = data[0];
        for(int i = 0; i < data.length-1; i++) //Moving all the elements one closer to top
        {
            data[i] = data[i+1];
        }
        return poppedObject;
    }

When all the data has been popped out of the stack and you try to pop something out of it, an EmptyStackException should be thrown. However, data.length does not change as objects are popped out. How is the pop method supposed to tell if a stack is empty or not if it can't tell with data.length?

Answer 1

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    //CREATING A STACK USING ARRAYS
    
    //EXAMPLE
    //CREATE AN ARRAY
    int[] numbers = new int[5];
    
    //Create a variable to find out the current elements position
    int pointer = 0 ; 
    
    //Add elements to the array
    for (int i = 0 ; i < numbers.length ; i++){
        numbers[pointer++] = input.nextInt();
    }
    
    //Last In first Out
    //Create a variable to store the removed element
    int temp;
    for (int i = 0; i < numbers.length; i++) {
        pointer -= 1;
        temp = numbers[pointer];
        numbers[pointer] = 0 ;
        
        System.out.println(temp);
    }
}

Answer 2

Set a counter to tell you the number of elements in the array. Array.length alone will tell you the capacity of your stack, not the number of elements in the stack. For this example, count is my counter

public E pop() throws EmptyStackException {
    if(count <= 0) {
        throw new EmptyStackException();
    }
    E poppedObject = data[0];
    for(int i = 0; i < count; i++) { //Moving all the elements one closer to top
        data[i] = data[i+1];
    }
    count--;
    return poppedObject;
}

Also note that if you implement the stack correctly, the stack will grow bottom up thus excluding the need to move all elements closer to the top. So if you do it this way the pop method should simply be:

public E pop() throws EmptyStackException {
    if(count == 0) {
        throw new EmptyStackException();
    } 
    return data[--count];
}

Answer 3

Below is the user defined Stack code how internally implemented.

class UserDefinedStack< E> {

    private static int defaultCapacity = 5;
    private E[] stack = null;
    int top = -1;

    /**
     * The default constructor will create stack of type with default size 5
     *
     */
    UserDefinedStack() {
        stack = (E[]) new Object[defaultCapacity];

    }

    /**
     * constructs a stack with initial size
     *
     * @param defaultSize is the size of the stack
     */
    UserDefinedStack(int defaultCapacity) {
        this.defaultCapacity = defaultCapacity;
        stack = (E[]) new Object[defaultCapacity];
    }

    public void push(E element) {
        top = top + 1;
        if (defaultCapacity == top) {
            //System.err.println("Stack is Full!...");
            // System.out.println("re-creating new resizable Array!..");
            stack = constructsResizableArray(stack, defaultCapacity);
            //throw new RuntimeException("Statck Full!...");
        }
        stack[top] = element;

    }

    /**
     * This method will remove the top of the element and return
     *
     * @return <tt>E</tt> returns top of the element
     *
     */
    public E pop() {

        if (top == -1) {
            System.out.println("Stack is Empty!...");
            throw new RuntimeException("Statck Empty!...");
        }
        E e = stack[top];
        stack[top] = null;
        top--;
        return e;
    }

    /**
     * This method will return top of the element and without remove
     *
     * @param <E> the type of element to insert
     * @return <tt>E</tt> returns top of the element
     *
     */
    public E peek() {

        if (top == -1) {
            System.out.println("Stack is Empty!...");
            throw new RuntimeException("Statck Empty!...");
        }
        E e = stack[top];
        return e;
    }

    public E[] constructsResizableArray(E[] stack, int defaultCapacity) {
        UserDefinedStack.defaultCapacity = defaultCapacity * 2;
        E[] newstack = (E[]) new Object[UserDefinedStack.defaultCapacity];
        int i = 0;
        for (E e : stack) {
            newstack[i] = e;
            i++;
        }
        stack = null;
        //System.out.println("New Array returned back");
        return newstack;
    }

    /**
     * Iterate the stack over the elements
     *
     */
    public void iterateStack() {
        for (E e : stack) {
            System.out.print("::" + e);
        }
    }

    public long size() {
        return top + 1;
    }

    public long capacity() {
        return this.stack.length;
    }
}

StackIntTest

import java.util.ArrayList;
import java.util.Date;
import java.util.Stack;

/**
 *
 * @author rajasekhar.burepalli
 */
public class StackIntTest {

    public static void main(String[] args) {
        System.out.println("Using Customized Stack!...............");
        Date startDate = new Date();
        System.out.println("StartTime:::" + startDate);
        UserDefinedStack< Integer> is = new UserDefinedStack<>();
        for (int i = 1; i < 1212121; i++) {
            is.push(i);
        }
        System.out.println("Size::::::" + is.size() + "---Capacity:::" + is.capacity());
        System.out.println("end Time::" + new Date());

        System.out.println("Using java.util.Stack!...............");

        System.out.println("StartTime:::" + startDate);
        Stack< Integer> is1 = new Stack<>();
        for (int i = 1; i < 1212121; i++) {
            is1.push(i);
        }
        System.out.println("end Time::" + new Date());
        System.out.println("Size::::::" + is1.size() + "---Capacity:::" + is1.capacity());

        System.out.println("Using java.util.ArrayList!...............");
        System.out.println("StartTime:::" + startDate);
        ArrayList< Integer> al = new ArrayList<>();
        for (int i = 1; i < 1212121; i++) {
            al.add(i);
        }
        System.out.println("end Time::" + new Date());
        System.out.println("Size::::::" + al.size());

    }
}

Answer 4

I suggest you look at how the Stack class is implemented already. It also uses an array, but has a size field which keep stack of the size.

The array only needs to change if the size grows larger than the length of the array.

From Stack.pop();

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

BTW In a stack you should never need to rearrange the elements. You should just add/remove from the end.

In your case you could write.

public int size() { return size; }

public void push(E e) {
    if (size == data.length) growArray();
    data[size++] = e;
}

public E pop() {
    if (size == 0) throw new EmptyStackException();
    return data[--size];
}