Java 不一致堆栈溢出

Question

我一直在为我的 AP 计算机科学类(class)做我的期末项目，并且正在修改 AP Picture Lab 来完成它(所有源代码都可以在 https://github.com/jvperrin/ap-picture-lab 上找到)。

对于我的项目的一部分，我实现了深度优先搜索以获取与目标像素相邻的黑色像素。但是，似乎每次我运行该程序时都会出现堆栈溢出错误，或者该程序运行良好。我遇到这个问题是有原因的吗？它与 Java 如何存储堆栈内存有关吗？

错误信息

Exception in thread "main" java.lang.StackOverflowError
at java.awt.image.ComponentColorModel.getRGB(Unknown Source)
at java.awt.image.BufferedImage.getRGB(Unknown Source)
at SimplePicture.getBasicPixel(SimplePicture.java:300)
at Pixel.getAlpha(Pixel.java:86)
at Pixel.setBlue(Pixel.java:296)
at ZPicture.depthFirstSearch(ZPicture.java:50)
at ZPicture.depthFirstSearch(ZPicture.java:73)
at ZPicture.depthFirstSearch(ZPicture.java:73)
at ZPicture.depthFirstSearch(ZPicture.java:73)
....

Z图片类:

    import java.util.ArrayList;
import java.util.Stack;

public class ZPicture extends SimplePicture {
    protected Pixel[][] pixels;
    protected boolean[][] checked;
    protected Stack<Pixel> stack;
    // a multidimensional array list?!?!
    //letters is the pixels in letters
    protected ArrayList<ArrayList<Pixel>> letters;
    //chars are the key points in letters
    protected ArrayList<ZChar> chars;
    protected final int BLACK = 30;
    protected final int SIZE = 10;

    public ZPicture(String fileName) {
        super(fileName);
        pixels = this.getPixels2D();
        checked = new boolean[pixels.length][pixels[0].length];
        stack = new Stack<Pixel>();
        letters = new ArrayList<ArrayList<Pixel>>();
        letters.add(new ArrayList<Pixel>());
        chars = new ArrayList<ZChar>();
    }

    // Z METHODS
    public void findLetters() {
        // Y
        for (int row = 0; row < pixels.length; row++) {
            // X
            for (int col = 0; col < pixels[0].length; col++) {
                Pixel p = pixels[row][col];
                if (isBlack(p)) {
                    stack.push(p);
                    depthFirstSearch();
                }
            }
        }
        sortLetters();
        findPoints();
        printLetters();
    }

    protected void depthFirstSearch() {
        // base case - if stack has elements
        if (!stack.isEmpty()) {
            Pixel p = stack.pop();
            checked[p.getY()][p.getX()] = true;
            letters.get(letters.size() - 1).add(p);
            p.setBlue(255);

            // get surrounding pixels
            Pixel pt = pixels[p.getY() - 1][p.getX()];
            Pixel pr = pixels[p.getY()][p.getX() + 1];
            Pixel pb = pixels[p.getY() + 1][p.getX()];
            Pixel pl = pixels[p.getY()][p.getX() - 1];

            // if pixel is black and unchecked, add to stack
            if (isBlack(pt)) {
                stack.push(pt);
            }
            if (isBlack(pr)) {
                stack.push(pr);
            }
            if (isBlack(pb)) {
                stack.push(pb);
            }
            if (isBlack(pl)) {
                stack.push(pl);
            }

            // recursion
            depthFirstSearch();
        } else {
            System.out.println("New Letter: " + letters.size());
            // note: the final letter is always empty
            letters.add(new ArrayList<Pixel>());
        }
    }

    protected boolean isBlack(Pixel p) {
        if (p.getBlue() < BLACK && p.getRed() < BLACK && p.getGreen() < BLACK
                && checked[p.getY()][p.getX()] == false) {
            return true;
        }
        return false;
    }

}

(我在其他地方有一个 main 方法，它实例化一个 ZPicture 并调用 findletters)。

Answer 1

StackOverFlowError 是由递归调用引起的(这甚至不是必需的)。错误的原因很简单:对于堆栈中的每个元素，算法都会进行另一个递归调用。如果黑色像素的面积足够大，相邻黑色像素的数量将超过堆栈大小，从而导致 StackOverFlowError。好消息:递归调用在这里没有任何意义，因为您已经使用了堆栈。只需将其删除，代码就可以正常工作。