java - java中的链表堆栈

Question

我正在尝试用 Java 实现一个链表样式的堆栈(不使用明显的内置方法)。 push操作简单明了，pop操作却让人头疼。我很清楚，将“弹出”值返回给调用者，同时调整链表会很有用，但这似乎不起作用。

public class ListElement {

/* constructor */
public ListElement(Integer data) {
    value = data;
}

/* next pointer and the data */
private ListElement next;
private Integer value;

/* gets the next element */
public ListElement getNext() {
    return next;
}

/* gets the data */
public Integer getValue() {
    return value;
}

/* sets the next element */
public void setNext(ListElement elem) {
    next = elem;
}

/* sets the data */
public void setValue(Integer data) {
    value = data;
}

/* prints out the list */
public void printList(ListElement head) {
    String listString = "";
    ListElement elem = head;
    while (elem != null) {
        listString = listString + elem.getValue().toString() + " ";
        elem = elem.getNext();
    }
    System.out.println(listString);
}

/* inserting at the front */
public ListElement push(ListElement head, Integer data) {
    ListElement elem = new ListElement(data);
    elem.setNext(head);
    return elem;
}

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();

    return popped;
}

 public static void main(String[] args) {



    System.out.println("Constructing List with 2 ...");
    ListElement myList = new ListElement(2);
    myList.printList(myList);

    System.out.println("Adding 1 to beginning ...");
    myList = myList.push(myList, 1);
    myList.printList(myList);

    System.out.println("Adding 0 to beginning ...");
    myList = myList.push(myList, 0);
    myList.printList(myList);

    System.out.println("Pop ...");
    Integer popped =  myList.pop(myList);
    System.out.println("Value is " + popped);
    myList.printList(myList);
      }

 }

Answer 1

通常在像您这样的结构中，您有两个类，一个是 ListElement，另一个是 List。我认为名称 StackElement 和 Stack 会更好，但是，继续......

问题是 Java 在您的 pop 方法中，正如您所怀疑的那样:

/* pop the first element */
public Integer pop (ListElement head){
    Integer popped = head.getValue();
    head = head.getNext();
    return popped;
}

而且在main方法中:

System.out.println("Pop ...");
Integer popped =  myList.pop(myList);

这里的问题是，您希望 myList 使用 pop() 方法中修改后的值 head.getNext() 进行更新。

这不会发生....当您调用 pop() 和行 head = head 时，Java 会创建对 myList 的不同“引用” .getNext() 不会更改 pop() 之外的 myList。

这种情况通常用第二个类来解决，称之为“List”(或者如我所说，应该是 Stack)...

public class Stack() {
    private StackElement head = null;
    public push(Integer value) {
        StackElement topush = new StackElement(value);
        topush.setNext(head);
        head = topush;
    }
    public Integer pop() {
        StackElement topop = head;
        if (head != null) {
            head = topop.getNext();
            return topop.getValue();
        }
        return null;
    }
}

然后，在您的 main 方法中，您应该使用这个新的 Stack 类:

Stack stack = new Stack();
stack.push(2);
....