Queue mit Ringstruktur



  • Ich habe eine Queue in Ringstruktur (Listenimplementation).
    In diese Queue lese ich die Zahlen 1-6 ein. Danach möchte ich sie wieder auslesen. Nach FiFo müsste dann ja wieder die zahlenreihe "1,2,3,4,5,6" kommen. Aber die Ausgabe gibt "1,6,5,4,3,2". Kann mir jemand sagen wo der Fehler liegt?

    class Zelle<E> {
    
        E        e;
        Zelle<E> next = null;
    
        Zelle(E el) {
            e = el;
        }
    }
    
    public class Queue<E> {
    
        /**************************************************************************/
        /* FELDER VEREINBAREN                                                     */
        /**************************************************************************/
        private Zelle ende;
    
        /**************************************************************************/
        /* METHODE ZUM EINFUEGEN EINES ELEMENTS                                   */
        /**************************************************************************/
        void enQueue(E e) {
    
            Zelle<E> neueZelle = new Zelle<E>(e);
    
            if(istLeer()) {
                ende = neueZelle;
                neueZelle.next = ende;
            } else {
                neueZelle.next = ende.next;
                ende.next = neueZelle;
            } 
        }
    
        /**************************************************************************/
        /* METHODE ZUM ENTFERNEN EINES ELEMENTS                                   */
        /**************************************************************************/
        E deQueue() {
            if(istLeer()) throw new QueueFehler("Fehler: Queue leer!");
    
            E last = (E) this.ende.e;
    
            if(this.ende.next==this.ende) {
                this.ende = null;
            } else {
                ende.e = ende.next.e;
                ende.next = ende.next.next;
            }
            return last;
        }
    
        /**************************************************************************/
        /* METHODE ZUM PRUEFEN, OB DIE QUEUE LEER IST                             */
        /**************************************************************************/
        boolean istLeer () {
            return ende == null;
        }
    }
    


  • Die falsche Ausgabe liegt daran, das dein ende.next immer auf die zuletzt eingefügt Zelle zeigt.
    Du musst dir in deinem Ring die erste Zelle merken - und die letzte, ab welcher neue Zellen eingefügt und mit der ersten verbunden werden.

    public class Queue<E> { 
    
    	    /**************************************************************************/ 
    	    /* FELDER VEREINBAREN                                                     */ 
    	    /**************************************************************************/ 
    	    private Zelle ende;
    	    private Zelle anfang;
    
    	    /**************************************************************************/ 
    	    /* METHODE ZUM EINFUEGEN EINES ELEMENTS                                   */ 
    	    /**************************************************************************/ 
    	    void enQueue(E e) { 
    
    	        Zelle<E> neueZelle = new Zelle<E>(e); 
    
    	        if(istLeer()) { 
    	            ende = neueZelle;
    	            anfang = neueZelle;
    	            neueZelle.next = ende; 
    	        } else { 
    	        	ende.next = neueZelle;
    	        	neueZelle.next = anfang;
    	        	ende = neueZelle;
    	        } 
    	    } 
    
    	    /**************************************************************************/ 
    	    /* METHODE ZUM ENTFERNEN EINES ELEMENTS                                   */ 
    	    /**
    	     * @throws Exception ************************************************************************/ 
    	    E deQueue() throws Exception { 
    	        if(istLeer()) throw new Exception("Fehler: Queue leer!"); 
    
    	        E last = (E) this.anfang.e; 
    
    	        if(this.anfang.next==this.anfang) { 
    	            this.ende = null; 
    	        } else { 
    	            anfang.e = anfang.next.e; 
    	            anfang.next = anfang.next.next; 
    	        } 
    	        return last; 
    	    } 
    
    	    /**************************************************************************/ 
    	    /* METHODE ZUM PRUEFEN, OB DIE QUEUE LEER IST                             */ 
    	    /**************************************************************************/ 
    	    boolean istLeer () { 
    	        return anfang == null; 
    	    } 
    	}
    


  • Achso... Dann hab ich die Aufgabenstellung einfacg falsch verstanden. Ich dachte man soll nur einen Anker (ende) verwenden. Mit anfang UND ende ist das natürlich easy. Danke!



  • @Wubbel
    Wenn das so in deiner Aufgabenstellung gefordert ist, dann musste dir ne methode schreiben, die, um eine neue Zelle in den Ring aufzunehmen, den Ring bis zur Zelle vor dem Ende durchläuft und hier einfügt. (Das würde ja sonst "ende" übernehmen)


Log in to reply