0

I'm trying to implement a drop out stack in Java and it's currently giving me a run for my money! Haha

I've gotten this far, and as far as I can tell, my logic is sound, but it's not compiling. I keep getting a java.lang.ArrayIndexOutOfBoundsException...

So here's the down and dirty of what I'm trying to do: I'm pushing and popping a series of elements in a stack, and would like the bottom element to drop out when a new element is added to the top of the stack. Any suggestions?

My Code:

    import java.util.Arrays;

public class Base_A05Q2
{
/**
 * Program entry point for drop-out stack testing.
 * @param args Argument list.
 */    
public static void main(String[] args)
{
    ArrayDropOutStack<Integer> stack = new ArrayDropOutStack<Integer>(4);

    System.out.println("DROP-OUT STACK TESTING");

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);       
    stack.push(5);               

    System.out.println("The size of the stack is: " + stack.size());        
    if(!stack.isEmpty())            
        System.out.println("The stack contains:\n" + stack.toString());

    stack.pop();        
    stack.push(7);
    stack.push(8);      

    System.out.println("The size of the stack is: " + stack.size());                
    if(!stack.isEmpty())            
        System.out.println("The stack contains:\n" + stack.toString());
}

public static class ArrayDropOutStack<T> implements StackADT<T>
{   
    private final static int DEFAULT_CAPACITY = 100;

    private int top;
    private int bottomElem = 0;
    private T[] stack;

    /**
     * Creates an empty stack using the default capacity.
     */
    public ArrayDropOutStack()
    {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Creates an empty stack using the specified capacity.
     * @param initialCapacity the initial size of the array 
     */
    @SuppressWarnings("unchecked")
    public ArrayDropOutStack(int initialCapacity)
    {
        top = -1;
        stack = (T[])(new Object[initialCapacity]);
    }

    /**
     * Adds the specified element to the top of this stack, expanding
     * the capacity of the array if necessary.
     * @param element generic element to be pushed onto stack
     */
    public void push(T element)
    {
        if (size() == stack.length) 
            top = 0;

        stack[top] = element;
        top++;
    }

    /**
     * Removes the element at the top of this stack and returns a
     * reference to it. 
     * @return element removed from top of stack
     * @throws EmptyCollectionException if stack is empty 
     */
    public T pop() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        T result = stack[top];
        stack[top] = null;

        if (top == 0)
            top = size()-1;
        top--;

        return result;
    }

    /**
     * Returns a reference to the element at the top of this stack.
     * The element is not removed from the stack. 
     * @return element on top of stack
     * @throws EmptyCollectionException if stack is empty
     */
    public T peek() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");

        return stack[top];
    }

    /**
     * Returns true if this stack is empty and false otherwise. 
     * @return true if this stack is empty
     */
    public boolean isEmpty()
    {
        if(stack.length == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    /**
     * Returns the number of elements in this stack.
     * @return the number of elements in the stack
     */
    public int size()
    {
        int counter = 0;
        for (int i = 0; i < stack.length; i++)
        {
            if (stack[i] != null)
            {
                //counter ++;
            }
        }
        return counter;
    }

    /**
     * Returns a string representation of this stack. The string has the
     * form of each element printed on its own line, with the top most
     * element displayed first, and the bottom most element displayed last.
     * If the list is empty, returns the word "empty".
     * @return a string representation of the stack
     */
    public String toString()
       {
           String result = "";
           for (int scan = top-1; scan >= 0; scan--)
           result = result + stack[scan].toString() + "\n";
           return result;
        }
   }
}

I think the problem is in this block, but I can't pin down the problem. Any help is greatly appreciated!

public void push(T element)
    {
        if (size() == stack.length) 
            top = 0;

        stack[top] = element;
        top++;
    }
9
  • I'm not sure I understand what you're trying to do. "...would like the bottom element to drop out when a new element is added to the top of the stack" sounds like you have a one element stack. What determines when it drops out? Your comments say the array will resize itself if necessary. Commented Apr 17, 2016 at 23:05
  • A few blocks of the code I have here were pulled over from another (successful) attempt I made to create a different stack. I carried a lot of the code over not knowing if I would need it or not. That also might be part of my problem, but I can't quite figured what needs to be left and what needs to be taken out. But to answer your first question, I'm trying to have an array that is dynamic (of course the array is sized statically, but it should copy over the data from the old array to a new, larger array once the first array has reached capacity. I want to initialize a stack with 5 elements, Commented Apr 17, 2016 at 23:16
  • add a new element to the top, and pop the lowest element Commented Apr 17, 2016 at 23:17
  • That's what I thought, but I'm having a problem resolving the issue of having an element removed when another's added. I don't see how you could have more than one element (if that) in this stack. Further, if I somehow have one of these stacks with n elements and add another (now n + 1) but then drop one (now n + 1 - 1; aka n), why would it need to be resized? Wouldn't that be a fixed-size stack? Sorry if I'm just not getting it. Commented Apr 17, 2016 at 23:21
  • Also! I didn't fully clarify something. The reason that the array needs to copy over to a new array when it reaches capacity is that (if I'm right, and I'm not so sure about that) as a new element is added to the top, and the bottom element is removed, the array will have 1 higher index value than before as well as 1 fewer at the bottom of the stack. So a new array is needed to add a new element in a higher index, but the array itself should only hold 5 element in it at any time. Hopefully that cleared it up alittle bit Commented Apr 17, 2016 at 23:24

2 Answers 2

1

What you're trying to do but may not realize it is provide a fixed-size stack backed by a circular array.

When you begin stacking top = 0. Then, you insert enough until you've reached capacity and choose to dump the "oldest" values in the stack and make room for "fresher" data. Well, the Oth element is the oldest so couldn't you kill two birdies with one stone when index = size by making it 0?

Consider:

public class CircularStack {

    int size = 5;
    int[] arr = new int[size];
    int top = 0;

    public void push(int i) {
        arr[top++ % size] = i;
    }

    public int pop() {
        return arr[--top % size];
    }
}

The interesting parts of this code are top++ % size and --top % size. They both deal with top being able to go outside the bounds of the array. So, for an array of size 5 the only possible indices will be { 0, 1, 2, 3, 4 }.

It won't take you long to realize this approach introduces another, less evil, problem; I'll leave it to you to discover and resolve it if necessary.

Sign up to request clarification or add additional context in comments.

Comments

0

Generally, in push/pop operations, when you push you want to post-increment (array[i++] = foo or "add it to the array then increment the index") and when you pop you want to pre-decrement (foo = array[--i] or "decrement the index then get the value from the array")

When you reach the end of your array in a push, your top will be 4, which is not a valid index of the array, so your next pop must decrement first and then get the value from the array.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.