java - 如何实现栈中的空元素

Question

我想为图灵机实现一个名为 Tape 的通用类，但我不知道如何实现磁带的空白部分。到目前为止，它看起来像:

public class Tape<T>{

private Stack<T> left  = new Stack<T>();   // left part of tape
private Stack<T> right = new Stack<T>();   // right part of tape
private T current;
private T BLANK = null;

public Tape(){
    right.push(BLANK);
    current = BLANK;
}
public void move(Direction direction) {
    if (direction == Direction.LEFT) {
        right.push(current);
        if (left.isEmpty()) left.push(BLANK);  // increase size of tape if necessary
        current = left.pop();
    } else if (direction == Direction.RIGHT) {
        left.push(current);
        if (right.isEmpty()) right.push(BLANK);  // increase size of tape if necessary
        current = right.pop();
    }
}

主要问题是，我不知道如何处理这个空白信号。目前它被设置为 null，但至少因为我想调用 move 并且堆栈为空，所以 push() 和 pop() 不起作用。

由于我不知道 T 的类型，有什么想法如何标记空白吗？

Answer 1

我会在 Tape 的构造函数中定义 BLANK。

private T BLANK;
private T current;
public Tape(T BLANK) {
    this.BLANK = BLANK;
    right.push(current = BLANK);
}

这样，根据您对 T 类型的了解，您可以使用任何对 BLANK 有意义的内容。例如:

new Tape<Integer>(null);

或者:

new Tape<String>(null);

或者甚至:

new Tape<String>("BLANK");

尝试例如:

import java.util.Stack;

enum Direction {LEFT, RIGHT}

public class Tape<T>{

    private Stack<T> left  = new Stack<T>();   // left part of tape
    private Stack<T> right = new Stack<T>();   // right part of tape
    private T current;
    private T BLANK;

    public static void main(String[] args) {
        new Tape<String>("BLANK").move(Direction.RIGHT);
    }

    public Tape(T BLANK){
        this.BLANK = BLANK;
        right.push(BLANK);
        current = BLANK;
    }
    public void move(Direction direction) {
        if (direction == Direction.LEFT) {
            right.push(current);
            if (left.isEmpty()) left.push(BLANK);  // increase size of tape if necessary
            current = left.pop();
        } else if (direction == Direction.RIGHT) {
            left.push(current);
            if (right.isEmpty()) right.push(BLANK);  // increase size of tape if necessary
            current = right.pop();
        }
    }
}