java - Sierpinski 地毯使用堆栈而不是递归

Question

我已经实现了一个解决方案来解决 Sierpinski carpet使用递归的问题。现在我想用堆栈而不是递归方法来解决Sierpinski地毯问题。我正在尝试将递归方法转换为堆栈，但是当我从递归方法中推送变量时遇到了麻烦。这是我必须推送和弹出的代码片段 drawGasket(x + i * sub, y + j * sub, sub);

当您调用drawGasket(0, 0, 729)时，您应该在屏幕上看到以下内容:

递归方法:

   public void drawGasket(int x, int y, int side) {
    int sub = side / 3; 

    //Draw center square
    g2d.fill(new Rectangle2D.Double(x + sub, y + sub, sub - 1, sub - 1));

    if(sub >= 3) {
        //Draw 8 surrounding squares
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                if (j!=1 || i != 1)
                    drawGasket(x + i * sub, y + j * sub, sub);
            }
        }
    }
}

堆栈实现:

    public void stack (int x, int y, int side ){
    GenericStack<Integer> s = new GenericStack<>();

    int sub = side /3;
    g2d.fill(new Rectangle2D.Double(x + sub, y + sub, sub - 1, sub - 1));

    while (!s.isEmpty()){
        x=s.pop();
        if (sub >=3){
            for (int i = 0; i < 3; i++){
                for (int j = 0; j < 3; j++){    
                    if (j!=1 || i != 1){
                        int operation = x+i*sub;
                        s.push(operation);
                        int operation2 = y+j*sub;
                        s.push(operation2);
                        s.push(sub);
                    }
                }
            }
        }
    }
}

我的堆栈类:

public class GenericStack<T> {

private int size; // size
private Node<T> head; // node head

public GenericStack() { // constructor
    head = null; // head is null
    size = 0; // size is zero
}

public void push(T element) {
    if(head == null) { // if head is null
        head = new Node(element); // head is node 
    } else {
        Node<T> newNode = new Node(element);
        newNode.next = head;
        head = newNode;
    }

    size++;
}

public T pop() {
    if(head == null)
        return null;
    else {
        T topData = head.data;

        head = head.next;
        size--;

        return topData;
    }
}

public T top() {
    if(head != null)
        return head.data;
    else
        return null;
}

public int size() {
    return size;
}

public boolean isEmpty() {
    return size == 0;
}

private class Node<T> {
    private T data;
    private Node<T> next;

    public Node(T data) {
        this.data = data;
    }

}

Answer 1

如果您可以将递归版本想象为已经是基于堆栈的，那么您应该能够适本地翻译您的代码。如果您将每次递归调用 drawGasket(x + i * sub, y + j * sub, sub); 视为将三个值插入堆栈，并且将 drawGasket 方法“内部”的每个第一步视为从堆栈中弹出三个值，那么在迭代解决方案中显式将这些相同的值插入和弹出 GenericStack 应该遵循相同的模式。基本上，就像在递归解决方案中一样，您需要将连续的值插入堆栈，直到用完要插入的值；然后你需要从堆栈中弹出、弹出、弹出连续的值，并“绘制”一个适合刚刚弹出的值的矩形，直到堆栈为空。