Java verkettete Liste in Stack

Question

Um ein wenig selbst in Datenstrukturen zu verbessern, habe ich versucht, meinen eigenen Stack zu entwerfen. Um dies zu tun, entschied ich mich, eine verknüpfte Liste zu verwenden, um mich undefined Länge Stapel zu verwenden (und weil ich von C-Programmierung komme). Mein Code ist:

public class Main { 

    public static void main(String[] args) { 
     Stack stk = new Stack(); 
     obj buf_el; 
     Scanner s=new Scanner(System.in); 
     boolean stop=false; 
    do{ 
     String buffer= s.next(); 
     System.out.println("Created first buff"); 
     if(buffer.equals("exit")) stop=true; 
     if(buffer.equals("pop")){ 
      buf_el = stk.pop(); 
      System.out.println("Element Popped from stack:\t\t[#]\t-->\t"+buf_el.field()); 
     } 
     else if(buffer.equals("push")){ 
      obj pushed = new obj(s.next()); 
      stk.push(pushed); 
      System.out.println("Element pushed in the stack:\t\t[#]\t<--\t"+pushed.field()); 
     } 
     else if(buffer.equals("stats")) stk.stats(); 
     else if(buffer.equals("all")) stk.traverse(); 
    } 
    while(stop==false); 
    } 
} 

class obj{ 
    private String field = new String(); 
    private obj next = null; 
    private obj back = null; 
    obj (String field){ 
     this.field=field; 
    } 

    public obj() { 

    } 

    void concat(obj next){ 
     this.next=next; 
     this.next.back=this; 
    } 
    void del(){ 
     this.next=null; 
     this.back.concat(null); 
    } 
    obj next(){ 
     return this.next; 
    } 
    obj back(){ 
     return this.back; 
    } 
    String field(){ 
     return this.field; 
    } 
} 

class Stack{ 
    private obj head = null; 
    private obj tail = null; 
    private int pops=0; 
    private int pushes=0; 
    void push(obj el){ 
     pushes++; 
     if(this.head==null | this.tail==null){ 
      this.head = el; 
      this.tail = el; 
     } 
     else{ 
      head.concat(el); 
     } 
    } 
    obj pop(){ 
     if(head==null & tail==null) System.out.println("The stack is empty, Operation failed."); 
     else{ 
      pops++; 
      if(this.head==this.tail){ 
       System.out.println("This is the last element; the stack is empty now"); 
       obj ret=new obj(this.head.field()); 
       this.head=null; 
       this.tail=null; 
       return ret; 
      } 
      else{ 
       obj ret=new obj(this.head.field()); 
       this.head=this.head.back(); 
       return ret; 
      } 
     } 
     return null; 
    } 
    void stats(){ 
     System.out.println("Number of pops\t||\t"+pops); 
     System.out.println("Number of pushes\t||\t"+pushes); 
     System.out.println("Length of the stack\t||\t"+(pushes-pops)); 
    } 
    void traverse(){ 
     if(head==null & tail==null) System.out.println("The stack is empty, Operation failed"); 
     obj cursor=null; 
     System.out.println(" TAIL"); 
     System.out.println("\t|"); 
     System.out.println("\t|"); 
     System.out.println("\t|"); 
     System.out.println("\tV"); 
     do { 
      cursor=tail; 
      System.out.println(cursor.field()); 
      System.out.println("\t|"); 
      System.out.println("\t|"); 
      System.out.println("\t|"); 
      System.out.println("\tV"); 
      cursor=cursor.next(); 
     } 
     while(cursor!=null); 
     System.out.println(" HEAD"); 
    } 
} 

GitHub

Aber es hat ein großes Problem: wenn ich ein neues Element schieben es auf dem vorherigen Element überschrieben wird. Wo ist der Fehler? Wahrscheinlich habe ich etwas missverstanden, was mit den "by reference" -Praktiken in Java zu tun hat. Welche Methoden würden Sie verwenden, um ein solches Programm zu erstellen?

P.S. Ich weiß, dass es eine Stack-Bibliothek gibt, aber ich glaube, es wäre gut, diese Dinge zu programmieren, um meine Sprachkenntnisse zu verbessern.

Answer 1

ich zwei Änderungen vorgenommen ik Arbeit zu machen:

zuerst in einem Push Sie th neues Element Kopf machen

void push(obj el) { 
    pushes++; 
    if (this.head == null | this.tail == null) { 
     this.head = el; 
     this.tail = el; 
    } else { 
     el.concat(head); 
     head = el; 
    } 
} 

zweite in o pop müssen Sie das nächste Element Kopf

machen

obj pop() { 
    if (head == null & tail == null) 
     System.out.println("The stack is empty, Operation failed."); 
    else { 
     pops++; 
     if (this.head == this.tail) { 
      System.out.println("This is the last element; the stack is empty now"); 
      obj ret = new obj(this.head.field()); 
      this.head = null; 
      this.tail = null; 
      return ret; 
     } else { 
      obj ret = new obj(this.head.field()); 
      this.head = this.head.next(); 
      return ret; 
     } 
    } 
    return null; 
} 

EDIT didnt't Prüfung durchqueren, hatte es zu ändern:

void traverse() { 
    if (head == null & tail == null) 
     System.out.println("The stack is empty, Operation failed"); 
    obj cursor = null; 
    System.out.println(" TAIL"); 
    System.out.println("\t|"); 
    System.out.println("\t|"); 
    System.out.println("\t|"); 
    System.out.println("\tV"); 
    cursor = tail; 
    while (cursor != null) { 
     System.out.println(cursor.field()); 
     System.out.println("\t|"); 
     System.out.println("\t|"); 
     System.out.println("\t|"); 
     System.out.println("\tV"); 
     cursor = cursor.back(); 
    } 
    System.out.println(" HEAD"); 
} 

Answer 2

Sie sollten versuchen, die Funktion equalsTo in Ihrer Obj-Klasse zu überschreiben; Es sollte so aussehen:

@Override 
public boolean equals(obj o){ 
    if (o.field.equalsTo(this.field) { 
     return true; 
    } 
} 

so sollte diese

arbeiten

if(this.head==null | this.tail==null){ 
      this.head = el; 
      this.tail = el; 
     } 
     else{ 
      head.concat(el); 
     } 

Answer 3

Ich habe in Ihnen code.First ausstellen zu sehen, wenn Sie dann Concat mit Schwanz und Bewegung zu beenden hinzufügen möchten der Schwanz zum aktuellen Knoten.wenn Sie t1 Kopf und Schwanz beide auf den gleichen Knoten nach dem t2 add und Kopf wird auf t1 zeigen und Schwanz wird t2.That Teil in Ihrem Code fehlt.

tail.concat(el); 
tail=tail.next(); 

Zweiter in Traverse Prozessschleife initialisieren einmal aus Seitenschleife

cursor=head;