Schlagwort: Datenstruktur

Datenstrukturen und Java klingt im ersten Moment nach einem Widerspruch: Java hat Objekte und keine Strukturen. Bei näherer Betrachtung sieht man jedoch, dass die vermeintlichen Datenstrukturen zumindest in C++ als Klassen und somit als Objekte realisiert sind – alleine die Bezeichnung ist noch ein Ãœberbleibsel aus prozeduralen C-Zeiten.
Wir können also festhalten, dass eine Datenstruktur Attribute und Funktionen hat (um die Sprache möglichst neutral zu halten). Unterschiedliche Datenstrukturen haben unterschiedliche Attribute und Funktionen. Dies steht im Gegensatz zum objektorientierten Ansatz der Wiederverwendung von Objekten.
Java bietet von Haus aus bereits ein grosses Repertoire (JDK) wo man mit C++ die STL bemühen muss. So lässt sich in Java eine FIFO Queue bereits durch die Klassendefinition und dem Überschreiben von remove vollständig implementieren:

public class FIFOList extends LinkedList implements Queue{
    public Object remove() {
        return remove(0);
    }
}

Beispiel von: Simple Thoughts
Wenn ich jedoch den durch die Struktur beschriebenen Funktionsumfang anschaue muss ich feststellen, dass die Funktionalität zwar der einer FIFO Queue entspricht, aber bereits die Methodennamen leicht verwirrlich sind. Zudem gibt es zahlreiche Funktionen, die mit einer FiFo Queue nichts zu tun haben. Ein C++ Entwickler, der nur die Signaturen sieht kann nicht erkennen, worum es sich handelt. Zudem weiss ich mit einer solchen Umsetzung nicht wie die Queue funktioniert.
Aus diesem Grund habe ich die C++ Implementation genommen, sie für Java angepasst und mit einigen convenient Methoden ergänzt:

public class FiFoQueue {
	private FiFoNode first=null;
	private FiFoNode last=first;
	public FiFoQueue(){		
	}
	// Put a new elemnt in the queue
	public void enqueue(T element){
		FiFoNode temp = new FiFoNode();
		temp.value=element;
		temp.next=last;
		last=temp;
	}
	// Get the element from the queue that is in front
	public T dequeue(){
		FiFoNode temp = first;
		first=first.next;
		return temp.value;
	}
	// Check if the queue is empty
	public boolean isEmpty(){
		return first==last && first==null;
	}
	// Empty the queue
	public void empty(){
		first=last=null;
	}
	class FiFoNode{
		FiFoNode next;
		T value;
		FiFoNode(){
		}
	}
}