Java新手:有没有一种更简单的方法可以在Java中实现数组Drop-Out堆栈

Question

我正在尝试用Java实现一个drop-out堆栈，它目前正在让我物超所值！哈哈

我已经走到了这一步，据我所知，我的逻辑是合理的，但它不是编译的。我一直得到一个java.lang.ArrayIndexOutOfBoundsException。。。

因此，这是我试图做的最糟糕的事情：我在堆栈中推送和弹出一系列元素，并希望在堆栈顶部添加新元素时，底部元素退出。有什么建议吗？

我的代码：

    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;
        }
   }
}

我认为问题出在这个街区，但我不能确定问题出在哪里。非常感谢您的帮助！

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

Answer 1

您试图做但可能没有意识到的是提供一个由圆形数组支持的固定大小堆栈。

当您开始堆叠top = 0。然后，插入足够的数据，直到达到容量，然后选择转储堆栈中"最旧"的值，为"更新鲜"的数据腾出空间。嗯，Oth元素是最古老的，所以当index = size时，你不能通过使其成为0来一举两得吗？

考虑：

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];
    }
}

这个代码中有趣的部分是top++ % size和--top % size。它们都处理top能够超出数组边界的问题。因此，对于大小为5的数组，唯一可能的索引将是{ 0, 1, 2, 3, 4 }。

你很快就会意识到这种方法引入了另一个不那么邪恶的问题；如果有必要，我会让你发现并解决它。

Answer 2

通常，在推送/弹出操作中，当您推送时，您希望发布增量（array[i++] = foo或"将其添加到数组中，然后递增索引"），而当您弹出时，您想要预减量（foo = array[--i]或"递减索引，然后从数组中获取值"）

当你在推送中到达数组的末尾时，你的top将是4，这不是数组的有效索引，所以你的下一次弹出必须先递减，然后从数组中获取值。