Generische Warteschlange

[Leno]

Hallo,

ich habe eine Frage,ich lernen gerade für eine Klausur und soll eine Warteschlange implementieren naiver ansatz.

folgende Beschreibung liegt vor :

WirspeicherndieElementederWarteschlangeineinemFeldfesterGro ̈ße.Ineiner weiteren Variablen (size) merken wir uns, wie viele Feldelemente belegt sind.

Ich wollte mal fragen ob jemand über meine Implementierung rüberschauen kann. Leider habe ich keine Lösung hier mein Code :

public class Warteschlange <T>{

	// generisches Feld 
	private T[] feld ;
	
	private int size;
	
	public Warteschlange(int maxSize) {
		
		feld = (T[]) new Object [maxSize];	
		this.size = 0;	
	}
	
	// hinzufügen von neum Element in Warteschlange 
	public void enqueue( T element) {
		
		feld[this.size] = element;
		
		this.size++;
		
	}
	
	public T front() {
		
		return feld[0];
	
	}
	
	// entferne erstes Element aus meiner Warteschlange  
	public T dequeue(){
		
		// Verschieben der Elemente 
		for(int i=1 ; i <size ; i++) { 
		 
			feld[i-1] = feld[i];
		
		}
		
		size--;  // setze den Speicher wieder zurück 
		
		return feld[0];
		
		
		
	}
	
	
	
	public int getSize(){
		
		return this.size;
		
	}
	
	
	
	
	
	
}

Danke im Voraus

 

[faetzminator]

Sieht eigentlich gut aus. Du kannst aber - wenn du willst - folgendes auch einfacher schreiben:

a[i] = x;
i++;
// -->
a[i++] = x;

Und beim Löschen eines Entries kannst du, statt dass du eine for-Schleife verwendest, auch [c]System.arraycopy()[/c] verwenden.

 

[Kr0e]

"dequeue" ist meiner Ansicht nach fehlerhaft. Es wird das erste Element zurück gegeben, nachdem die übrigen Elemente kopiert wurden, oder ? Vlt soll das ja auch so sein, aber der Sinn einer Queue ist ja dass man das Element das man entfernt hat dann auch benutzt....

Ansich sieht der Ansatz aber ok aus.

 

[Kr0e]

Und beim Löschen eines Entries kannst du, statt dass du eine for-Schleife verwendest, auch [c]System.arraycopy()[/c] verwenden.

Das würde ich auch drigend raten, Bei extrem vielen Elementen fällt das schon recht stark ins GEwicht. Mich würde es sogar garnicht wundern wenn der Compiler diese Schleife ersetzt

 

[Leno]

Komisch ich sehe den Fehler bei dequeue nicht. Ich dachte man ennimmmt das erste Element aus dem Speicher FIFO prinzip und verschiebt die anderen dann

 

[Kr0e]

Ja exakt!

Aber dein Code:

    // entferne erstes Element aus meiner Warteschlange  
    public T dequeue(){
        
        // Verschieben der Elemente 
        for(int i=1 ; i <size ; i++) { 
         
            feld[i-1] = feld[i];
        
        }
        
        size--;  // setze den Speicher wieder zurück 
        
        return feld[0];
        
        
        
    }

Gibt das erste Element nach dem Kopiern zurück...

 

[faetzminator]

Ah ja, gar nicht gesehen... Du musst das erste Element in einer lokalen Variable speichern, dann [c]System.arraycopy()[/c] verwenden, size-- und noch das Element zurückgeben.

 

[Leno]

Ich gebe bereits feld[0] zurück da liegt das erste Element doch, oder verstehe ich da was falsch:bahnhof:

 

[Kr0e]

Aber du kopierst doch VORHER alle Elemente einen Index nach vorne. Sprich das ALTE ERSTE Element geht dabei verloren und du gibts quasi das ehemals 2te Objekt zurück.