基于动态数组的堆栈

Question

我正在尝试创建一个基于动态数组的堆栈，但当我尝试将元素元素推入完整数组时出现索引超出范围错误。我还使数组通用以适应所有类型的堆栈。

import java.util.Arrays;
import java.util.Iterator;

public class Stack<T> {
    private int topStack;
    private int stackSize;
    private T[] stack;

    // Constructor
    public Stack(T[] arr) {
        stack = arr;
        stackSize = arr.length;
        topStack = -1;
    }

    // isEmpty
    public boolean isEmpty() {
        if (topStack == -1)
            return true;
        return false;
    }

    // isFull method
    public boolean isFull() {
        if ((topStack + 1) == stackSize)
            return true;
        return false;
    }

    // increment array by 10 spaces <-----------------------------------
    public void incrementArray() {
        T[] temp = (T[]) new Object[stackSize*2];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack=temp;
        stackSize=stackSize*2;
    }

    // decrement array
    public void decrementArray() {
        stackSize=stackSize/2;
        T[] temp = (T[]) new Object[stackSize];
        System.arraycopy(stack, 0, temp, 0, stackSize);
        stack=temp;
    }

    // push method which adds element to top of stack
    public void push(T element) {
        if (isFull())
            incrementArray();
        topStack=topStack+1;
        stack[topStack] = element;
    }

    // peek method which shows top of stack without popping it
    public T peek() {
        return stack[topStack];
    }

    // pop which copies top of stack, deletes top and returns copy
    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        int temp = topStack+1;
        if(temp<stackSize/2)
            decrementArray();
        return stack[topStack--];
    }

    public static void main(String[] args)  {
        Stack operands = new Stack<>(new Integer[0]);
        
            operands.push(2);
            operands.push(1);

    }
}

我正在尝试增加堆栈大小而不是让它溢出边界。

Answer 1

你应该给你的堆栈一个初始的

size > 0

。就目前而言，您的初始

stackSize

是 0。猜猜

stackSize*2

等于什么？另一个观察结果是，您创建了一个通用堆栈，但在创建它时没有指定类型

main

此外，请注意，您可以更改

public boolean isEmpty() {
    if (topStack == -1)
        return true;
    return false;
}

到

public boolean isEmpty() {
    return topStack == -1;
}

您可以在其他返回

boolean

的方法中进行类似的更改。

当您的代码没有按应有的方式运行时，请考虑正在发生的事情以及为什么会发生这种情况。在您的代码中放置无处不在的打印语句是检查键值以查看它们是否符合您的预期的良好开端。一种更复杂的方法是使用调试工具在程序执行时单步执行以查看各个字段的值。

Answer 2

你应该使用动态分配内存的链表栈。那些堆栈永远不会溢出。当您的计算机内存已满时它会溢出

public class DynamicStack {

 static  class Node{
    int data;
    Node next;

    Node(int d){
        data = d;
        next = null;
    }
}

static class Stack{
    public static  Node topHead;

    public static boolean isEmpty(){
        return topHead == null;
    }

    public static void push(int data){
        
        Node newnode = new Node(data);

        if(isEmpty()){
            topHead = newnode;
            return;
        }
        
        newnode.next = topHead;
        topHead = newnode;

    }

    public static int pop(){
        if (isEmpty()) {
            return -1;
        }
        int data = topHead.data;

        topHead = topHead.next;
        return data;
    }

    
    public static int peek(){
        if (isEmpty()) {
            return -1;
        }
        
        return topHead.data;
    }


}

public static void main(String[] args) {
    Stack st = new Stack();
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);

    while (!st.isEmpty()) {
        System.out.println(st.peek());
        st.pop();
    }
  }
}

我希望这对你有用