Java數據結構使用鏈接列表的堆棧

Question

我試圖在Java中使用LinkedList實現Stack（push），然後我意識到我有一個很大的問題，即使我在附加新節點時它們不在那裏，但在遍歷期間。

我意識到我正在使用之前定義的節點對象，因此數據正在被重寫。像下面的代碼：

package LLAPPLICATION; 

import java.util.Scanner; 

class Node { 
    Node next; 
    int data; 
} 

public class Stack { 
    Node first; 

    void push(Node node) { 
     if (first == null) { 
      first = node; 
      first.next = null; 

     } else if (first.next == null) { 
      first.next = node; 
      node.next = null; 
     } else { 
      Node temp = new Node(); 
      temp = first; 
      while (temp.next != null) { 
       temp = temp.next; 
      } 
      temp.next = node; 
      node.next = null; 
     } 
    }     

    public static void main(String[] args) { 
     Scanner inp = new Scanner(System.in); 
     Stack stk = new Stack(); 
     Node tmp = new Node(); 
     char cho; 
     do { 
     System.out.print("Enter the element to insert ::"); 
         /* This is the part where it got tricky.If I use tmp by declaring it at the top it just wont happen.I think its because of garbage collection i.e. every iteration causes new instance i.e tmp to be created and hence preventing it from being overwritten*/ 
         tmp.data = inp.nextInt(); 
         stk.push(tmp); 
         System.out.print("Do you want to PUSH again..(Y/N):"); 
         cho = inp.next().charAt(0); 
        } while (cho == 'Y' || cho == 'y'); 

     } 
} 

然後，我做到了這一點，它的工作。現在我很困惑，我認爲這是因爲垃圾收集，但不知道。

package LLAPPLICATION; 

import java.util.Scanner; 

class Node { 
    Node next; 
    int data; 
} 

public class Stack { 

    Node first; 

    void push(Node node) { 
     if (first == null) { 
      first = node; 
      first.next = null; 

     } else if (first.next == null) { 
      first.next = node; 
      node.next = null; 
     } else { 
      Node temp = new Node(); 
      temp = first; 
      while (temp.next != null) { 
       temp = temp.next; 
      } 
      temp.next = node; 
      node.next = null; 
     } 
    } 

    public static void main(String[] args) { 
     Scanner inp = new Scanner(System.in); 
     Stack stk = new Stack(); 
     char cho; 

        do { 
     /*If I declare a tmp inside of the loop it does*/ 
         Node tmp = new Node(); 
         System.out.print("Enter the element to insert ::"); 
         tmp.data = inp.nextInt(); 
         stk.push(tmp); 
         System.out.print("Do you want to PUSH again..(Y/N):"); 
         cho = inp.next().charAt(0); 
        } while (cho == 'Y' || cho == 'y'); 
     } 
} 

Answer 1

你幾乎一切都錯了。這是一個堆棧。你關心的是上一個和上一個。推只需要使this.last-> node.previous和節點成爲最後一個。流行只需要做相反的事情。

不需要遍歷。

void push(Node node){ 
    if (this.last != null) 
     node.previous = this.last; 
    this.last = node; 
    size++ 
} 

Node pop(){ 
    if (this.last == null){ 
    // Exception/etc 
    } 
    Node n = this.last; 
    this.last = n.previous; 
    size-- 
    return node; 
}