动态数组堆栈

huangapple go评论56阅读模式
英文:

Dynamic array based stack

问题

我正在尝试创建一个基于动态数组的栈,当我尝试将元素推入已满的数组时,出现了索引越界错误。我还使数组具有通用性,以容纳所有类型的栈。

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

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

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

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

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

	// 增加数组大小的方法 &lt;-----------------------------------
	public void incrementArray() {
		T[] temp = (T[]) new Object[stackSize * 2];
		System.arraycopy(stack, 0, temp, 0, stack.length);
		stack = temp;
		stackSize = stackSize * 2;
	}

	// 减小数组大小的方法
	public void decrementArray() {
		stackSize = stackSize / 2;
		T[] temp = (T[]) new Object[stackSize];
		System.arraycopy(stack, 0, temp, 0, stackSize);
		stack = temp;
	}

	// 推入元素到栈顶的push方法
	public void push(T element) {
		if (isFull())
			incrementArray();
		topStack = topStack + 1;
		stack[topStack] = element;
	}

	// 查看栈顶元素而不弹出的peek方法
	public T peek() {
		return stack[topStack];
	}

	// 弹出顶部元素的pop方法,复制顶部并返回副本
	public T pop() throws EmptyStackException {
		if (isEmpty()) {
			throw new EmptyStackException();
		}
		int temp = topStack + 1;
		if (temp &lt; 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);
	}
}

我正在尝试增加栈的大小,而不是使其超出边界。

英文:

I'm trying to create a dynamic array based stack and I am getting an index out of bound error when I try to push elements elements onto a full array. I also made the array generic to accommodate all types of stacks.

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

public class Stack&lt;T&gt; {
	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 &lt;-----------------------------------
	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&lt;stackSize/2)
			decrementArray();
		return stack[topStack--];
	}

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

	}
}

I'm trying to increase the stack size instead of having it overflow out of bounds.

答案1

得分: 2

你应该为你的堆栈设置一个初始的 size &gt; 0。目前,你的初始 stackSize 为0。猜猜看 stackSize*2 等于多少?另一个观察是,你创建了一个泛型堆栈,但在 main 中创建它时没有指定类型。

另外,请注意你可以将以下代码段:

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

改为:

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

你可以在其他返回 boolean 的方法中进行类似的更改。

当你的代码不按预期运行时,思考一下发生了什么以及可能的原因。在你的代码中广泛使用打印语句是检查关键值是否符合预期的良好第一步。更复杂的方法是使用调试工具逐步执行你的程序,查看各个字段的值。

英文:

You should give your stack an initial size &gt; 0. As it stands, your initial stackSize is 0. And guess what stackSize*2 is equal to? And another observation is that you created a generic stack but did not specify a type when creating it in main

Also, note that you can change

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

to

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

You can make similar changes in other methods that return a boolean.

When your code does not behave the way it should, think about what is going on and why that might happen. Placing ubiquitous print statements thru out your code is a good first step to check on key values to see if they are what you expect them to be. A more sophisticated method is to use a debugging tool to step thru your program as it executes to look at the values of various fields.

答案2

得分: 0

你应该使用动态分配内存的链表栈。这些栈永远不会溢出。只有当你的计算机内存已满时才会溢出。

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

希望这对你有用。

英文:

you should use linked list stack which is dynamically allocated memory. those stack never overflow. it is overflow when your computer memory will full

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

i hope this is useful for you

huangapple
  • 本文由 发表于 2023年2月16日 05:59:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/75465827.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定