Java 中的链表堆栈

Question

我正在尝试在Java中实现链表样式堆栈（不使用以明显方式构建的）。 推送操作很简单，但弹出操作令人烦恼。我很清楚，将"popped"值返回给调用者并同时调整链表会很有用，但这似乎不起作用。

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;
}

而且在主要方法中：

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

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

这不会发生。当您调用pop()时，Java 会创建对myList的不同"引用"，并且head = head.getNext()行不会更改我们pop() myList。

这种情况通常用第二类来解决，称之为"列表"（或者正如我所说，应该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);
....

Answer 2

通常，

对于这样的链表，您需要一个包含对堆栈顶部的引用的 Header 或 LinkedList 类。

它将有一个字段ListElement top以及pop和push的功能。

正如您所料，push只是将开始设置为新的ListElement并且该元素的next等于旧start。

pop只是返回start元素的值并设置start = start.getNext()从而删除顶部。

Answer 3

当你说时，你没有修改myList

。

head = head.getNext();

您只需在 pop 方法中修改局部变量。

我最喜欢的解决方案是将"列表"和"元素"完全分开，就像两个单独的文件一样。然后事情应该开始变得更有意义了。

列表

• 头部（元素类型）

元素

• 下一个（元素类型）
• 值（整数类型）

Answer 4

你可以在这里找到正确的实现。

代码中的问题是：

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

修改仅函数本地的 head 元素。

您需要将代码拆分为两类：

• ListElement：将只包含值/下一个信息，

  public class ListElement {
       ListElement next;
       Integer value;
  }
  

• LinkedStack：将只包含至少堆栈函数（push/pop），以及对堆栈中第一个ListElement的引用。在调用 pop 函数时需要更新的正是此引用。

  public class LinkedStack {
       private ListElement first;
       public void push(Integer item) {
           ListElement oldfirst = first;
           first = new ListElement();
           first.value= item;
           first.next = oldfirst;
       }
  
       public Integer pop() {
           Integer item = first.value;      
           first = first.next;           
           return item;                 
       }
  }