java - 使用链表的堆栈回文不会返回正确答案

Question

我一直在使用链表实现堆栈。实现如下:

public class Node {
    public Object e;
    Node next;
    public Node(Object e){
        this.e=e;
    }
}

public class Stack {
    Nodo last, first;
    int count;
    public void push(Object n){
        Nodo temp=new Nodo(n);
        temp.next=last;
        last=temp;
        if (first==null){
            first=temp;
        }
        count++;
    }
    public boolean isEmpty(){
        if (count==0) return true;
        else return false;
    }
    public Object pop(){
        Object obj=null;
        if (isEmpty()){
            return -1;
        }
        else{
            obj=last.e;
            last=last.next;
        }
        count--;
        return obj;
    }
    public void print(){
        Nodo current=last;
        while (current!=null){
            System.out.println(current.e);
            current=current.next;
        }
    }
public boolean palindrome(){
        Stack cadT1=new Stack();
        Stack cadT2=new Stack();
        cadT1=this;
        //System.out.println(this.isEmpty());
        while (this.isEmpty()!=true){
            cadT2.push(this.pop());
        }
        cadT1.print();
        while (cadT1.isEmpty()!=true){
            /*if (!(cadT1.pop().equals(cadT2.pop()))){
                return false;
            }*/
            System.out.println(cadT1.pop()+" "+cadT2.pop());
        }
        return true;
    }

我在回文函数的实现上遇到了问题，其中我也使用了堆栈。我遇到的问题是它总是返回 true 值。我已经评论了当前不起作用的代码部分。在分析我的代码时，我发现当我执行以下作业时:

cadT1=this;

cadT1 变量仍然为空。我通过将以下行放入回文函数的 while 中对此进行了测试:

System.out.println(cadT1.pop()+" "+cadT2.pop());

我发现我的代码没有执行该行，那是因为 while 循环中的条件:

while (cadT1.isEmpty()!=true){

始终设置为 false。我的主类中的运行代码如下:

 Stack word=new Stack();
    word.push('a');
    word.push('s');
    word.push('d');
    word.push('f');
    System.out.println(word.palindrome());

我做错了什么？谢谢

Answer 1

这是因为你已经用这个从当前堆栈中弹出了所有元素

cadT2.push(this.pop());

现在，当您调用 cadT1.print() 时，它不会打印任何内容(cadT1 是对当前堆栈的引用)。因此，cadT1.isEmpty() 将为 true。

你可以做的是迭代链表并构建第二个堆栈，而不是从当前堆栈中弹出元素来构建第二个堆栈(如果弹出，则当前堆栈中将没有任何元素可供比较反对)。