Java Datenstruktur Stack mit verknüpfter Liste

Question

Ich habe versucht, Stack (Push) mit LinkedList in Java zu implementieren, dann erkannte ich, dass ich ein großes Problem hatte, obwohl ich neue Knoten anbrachte, die sie beim Traversieren nicht waren.

Ich erkannte, dass ich ein Node-Objekt verwendet, das zuvor immer wieder definiert wurde, so dass die Daten neu geschrieben wurden. Wie der folgende Code:

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'); 

     } 
} 

Dann habe ich es so gemacht und es hat funktioniert. Jetzt bin ich wirklich verwirrt, ich denke es ist wegen Garbage Collection aber nicht sicher.

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

Sie haben so ziemlich alles falsch. Es ist ein Stapel. Sie kümmern sich um den letzten und vorherigen. Push muss nur this.last-> node.previous machen und node wird zuletzt. Pop muss nur das Gegenteil tun.

Traversal wird nicht benötigt.

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