2
\$\begingroup\$

I implemented a fixed-length stack in Java for use in my fractal generator program, an RPN calculator and my esolang interpreter. This is a generic stack, and goes over and above the call of duty in places to supply my esolang interpreter with some essential methods (the initStack(),dumpStack() and ...N() methods, as well duplication and reversal.

This works fine when I use it for the fractal generator (I haven't tested the interpreter with the stack very much).

Here's the code. Please suggest any improvements, lexical/syntactic or algorithmic, and especially about any bugs, if they arise.

Note:

I purposely throw a custom StackOverflowException subclassing java.lang.IndexOutOfBoundsException rather than a java.lang.StackOverflowError as the latter indicates an overflow of the JVM internal stack specifically.

package in.tamchow.fractal.math;

import java.io.Serializable;
import java.util.EmptyStackException;

/**
 * A generic fixed-length stack
 */
public class FixedStack<E> implements Serializable {
    /**Array of elements*/
    E[] elements;
    /**Stack top pointer*/
    int top;

    /**
     * Parameterized constructor. No default constructor.
     * @param capacity The maximum size  (capacity) of the stack
     * @see FixedStack#setSize(int)
     * @see FixedStack#resetTop(boolean)
     */
    @SuppressWarnings("unchecked")
    public FixedStack(int capacity) {
        setSize(capacity);
        resetTop(false);
    }

    /**
     * Resets the stack top pointer depending on whether the stack is empty or full
     * @param notEmpty Whether or not the stack is empty
     */
    public void resetTop(boolean notEmpty) {
        top = notEmpty ? 0 : elements.length;
    }

    /**
     * Note: Setting the size <b>WILL CLEAR THE STACK</b>.
     * @param size The size of the newly-initialized stack
     * @see FixedStack#resetTop(boolean)
     */
    @SuppressWarnings("unchecked")
    public void setSize(int size){
        this.elements = (E[]) new Object[size];
        resetTop(false);
    }

    /**
     * Has the same effect as {@link FixedStack#setSize(int)},
     * but does not reinitialize the elements array
     * @see FixedStack#setSize(int)
     * @see FixedStack#resetTop(boolean)
     */
    public void erase() {
        for (int i = 0; i < elements.length; ++i) {
            elements[i] = null;
        }
        resetTop(false);
    }

    /**
     * Pushes a set of values onto the stack
     * @param values The values to push
     */
    public void pushN(E[] values) {
        for (E value : values) {
            push(value);
        }
    }

    /**
     * Pushes a value onto the stack
     * @param value The value to push
     */
    public void push(E value) {
        if (isFull()) throw new IndexOutOfBoundsException("Overflow Exception");
        elements[--top] = value;
    }

    /**
     * Checks whether the stack is full
     * @return Whether the stack is full or not
     */
    public boolean isFull() {
        return (top == 0);
    }

    /**
     * Pops a set of values from the stack
     * @return The popped values
     */
    @SuppressWarnings("unchecked")
    public E[] popN(int n) {
        E[] values = (E[]) new Object[n];
        for (int i = 0; i < n; i++) {
            values[i] = pop();
        }
        return values;
    }

    /**
     * Pops a value from the stack
     * @return The popped value
     */
    public E pop() {
        if (isEmpty()) throw new EmptyStackException();
        E value = elements[top];
        elements[top++] = null;
        return value;
    }

    /**
     * Checks whether the stack is empty
     * @return Whether the stack is empty or not
     */
    public boolean isEmpty() {
        return (top == elements.length);
    }

    /**
     * Peeks at a set of values on the stack
     * @param n The number of values to peek at
     * @return The peeked-at values
     */
    @SuppressWarnings("unchecked")
    public E[] peekN(int n) {
        E[] values = (E[]) new Object[n];
        for (int i = 0; i < n; i++) {
            values[i] = peek(i);
        }
        return values;
    }

    /**
     * Peeks at a value on the stack at a particular index
     * @param n The relative index of the value to peek at
     * @return The peeked-at value
     */
    private E peek(int n) {
        if (isEmpty()) throw new EmptyStackException();
        return elements[top - n];
    }

    /**
     * Duplicates the n topmost elements of the stack, top-down.
     * @param n The number of elements to duplicate
     */
    public void duplicateN(int n) {
        for (int i = 0; i < n; i++) {
            duplicate();
        }
    }

    /**
     * Duplicates the topmost element of the stack
     */
    public void duplicate() {
        push(peek());
    }

    /**
     * Peeks at a value on the stack
     * @return The peeked-at value
     */
    public E peek() {
        if (isEmpty()) throw new EmptyStackException();
        return elements[top];
    }

    /**
     * Reverses the stack
     * @see FixedStack#initStack(Object[])
     */
    @SuppressWarnings("unchecked")
    public void reverse() {
        E[] reversed = (E[]) new Object[elements.length];
        for (int i = 0, j = reversed.length - 1; i < elements.length && j >= 0; i++, j--) {
            reversed[j] = elements[i];
        }
        initStack(reversed);
    }

    /**
     * Initializes the stack with the supplied set of values
     * @param elements The set of initial values
     * @see FixedStack#pushN(Object[])
     * @see FixedStack#setSize(int)
     */
    @SuppressWarnings("unchecked")
    public void initStack(E[] elements) {
        setSize(elements.length);
        pushN(elements);
    }

    /**
     * Dumps the stack elements to the caller
     * @return The set of elements currently on the stack
     */
    public E[] dumpStack() {
        return elements;
    }

    /**
     * Provides the current number of elements on the stack
     * @return The size of the stack
     */
    public int size() {
        return elements.length - top;
    }

    /**
     * More conventional stack size calculation.
     * Use not recommended.
     * @return The size of the stack
     * @see FixedStack#size()
     */
    public int sizeN() {
        int size = 0;
        for (E i : elements) {
            if (i != null) size++;
        }
        return size;
    }

    /**
     * Alias for {@link FixedStack#erase()}
     * @see FixedStack#erase()
     */
    @SuppressWarnings("unchecked")
    public void clear() {
        erase();
    }
}
   /**
    * Custom Stack Overflow Exception class
    */
    public class StackOverflowException extends IndexOutOfBoundsException{
        /**
         * Constructs the exception with a default message
         */
        public StackOverflowException(){
            this("Stack Overflow");
        }

        /**
         * Constructs the exception with a custom message
         * @param message The custom message
         */
        public StackOverflowException(String message){
            super(message);
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Formatting issues happened during the paste from IDEA to Chrome. Please don't mind them. \$\endgroup\$ – Tamoghna Chowdhury Mar 26 '16 at 6:52
  • \$\begingroup\$ Why was this downvoted? \$\endgroup\$ – Tamoghna Chowdhury Mar 26 '16 at 18:24
4
\$\begingroup\$

1

You should declare the fields elements and top as private. Also, since you do not expand the storage array (elements), you can declare it final as well.

2

It's kind of funny that your stack grows from larger indices towards smaller ones. I suggest you rename top to size, and make your stack grow towards larger indices. That way, the value of size will be the storage array index at which the next pushed element would be placed.

3

In the constructor, you call erase that sets all the storage array components to null. Don't do this, JVM initializes all object array components to null by default.

\$\endgroup\$
  • \$\begingroup\$ Why do you bold the code block things? \$\endgroup\$ – Nic Hartley Mar 26 '16 at 14:52
  • \$\begingroup\$ I think it is more readable. \$\endgroup\$ – coderodde Mar 26 '16 at 14:53
  • 1
    \$\begingroup\$ Personal style, then. Fair enough. Good answer! \$\endgroup\$ – Nic Hartley Mar 26 '16 at 14:54
3
\$\begingroup\$

Suppressing warnings

It's recommended to suppress the smallest possible unit. For example here:

@SuppressWarnings("unchecked")
public void setSize(int size){
    this.elements = (E[]) new Object[size];
    resetTop(false);
}

Instead of suppressing the unchecked warning in the entire method, it would be better to do it for the one offending statement, like this:

public void setSize(int size){
    @SuppressWarnings("unchecked")
    this.elements = (E[]) new Object[size];
    resetTop(false);
}

In some methods you suppress unnecessarily, for example here:

@SuppressWarnings("unchecked")
public FixedStack(int capacity) {
    setSize(capacity);
    resetTop(false);
}

I'm going to take a wild guess that in a previous version there was indeed an offending statement in this method. You suppressed the warning at the method level, then refactored the code, the offending statement got moved somewhere else, and you forgot to remove the suppression. This mistake would not have happened if you had suppressed at the statement level, you see?

Encapsulation

I'm wondering if you really intended for some of the methods to be public. For example setSize and resetTop. These methods manipulate the internal state of the stack, which is not common in stack implementations. I think these should be private, to hide from users.

On a related note, it would be better to extract the interface of the fixed stack, which would make it perfectly clear whih methods are intentionally exposed.

Avoid confusion by better names

I purposely throw a custom StackOverflowException subclassing java.lang.IndexOutOfBoundsException rather than a java.lang.StackOverflowError as the latter indicates an overflow of the JVM internal stack specifically.

To avoid confusion, I propose the name FixedStackOverflowException for your custom exception class.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.