Java新手: Is there an easier way to implement an array Drop-Out stack in Java?

Question

我正在尝试在 Java 中实现一个退出堆栈，它目前正在给我带来机会!哈哈

我已经走到这一步了，据我所知，我的逻辑是合理的，但它无法编译。我不断收到 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;
        }
   }
}

我认为问题出在这个 block 上，但我无法确定问题所在。非常感谢任何帮助!

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

你很快就会意识到这种方法会带来另一个不那么严重的问题；如果有必要的话，我会把它留给你去发现和解决。