001    package de.hska.java.aufgaben.interfaces;
002    
003    
004    /**
005     * Implementiert eine Queue mit einem Feld. Wenn das Feld zu kleine für die
006     * hinzugefügten Werte sind, dann wird dessen Grösse verdoppelt.
007     * 
008     * <p>
009     *   <a href="http://www.home.hs-karlsruhe.de/~pach0003/informatik_1/aufgaben/interfaces.html#queue">Zurück zum Aufgabentext</a>
010     * </p>
011     * 
012     * @author Christian Pape
013     *
014     */
015    public class ArrayQueue implements Queue {
016    
017            /**
018             * Index des ersten Werts, der in diese Queue eingefügt wurde.
019             * Er erhöht sich um Eins, wenn remove() aufgerufen wird.
020             */
021            private int ersterWert = 0;
022            
023            /**
024             * Index des nächsten freien Platzes für einen neuen Wert.
025             * An diese Stelle wird mit add() ein neuer Wert hinzugefügt.
026             */
027            private int naechsterLetzterWert = 0;
028            
029            /**
030             * Die Queue mit den Werten. Sie ist zyklisch angeordnet.
031             * Wenn beim Hinzufügen das Ende erreicht ist, am Anfang aber
032             * noch freier Platz von zuvor entfernten Werten existiert,
033             * dann wird dieser aufgefüllt.
034             */
035            private int [] queue;
036            
037            /**
038             * Erzeugt eine ArrayQueue mit initial <code>groesse</code> möglichen Werten.
039             */
040            public ArrayQueue(int groesse) {
041                    queue = new int[groesse];
042            }
043            
044            /**
045             * Erzeugt eine ArrayQueue mit initial 100 möglichen Werten.
046             */
047            public ArrayQueue() {
048                    this(100);
049            }
050            
051            public void add(int wert) {
052                    if ( (naechsterLetzterWert + 1) % queue.length == ersterWert ) {
053                            int [] neueQueue = new int[2 * queue.length];
054                            // Wert von queue in das neue Feld umkopieren
055                            for (int i = ersterWert; i < queue.length; i++) {
056                                    neueQueue[i - ersterWert] = queue[i];
057                            }
058                            for (int i = naechsterLetzterWert; i < ersterWert; i++) {
059                                    neueQueue[i - naechsterLetzterWert + ersterWert] = queue[i];
060                            }
061                            ersterWert = 0;
062                            naechsterLetzterWert = queue.length - 1;
063                            queue = neueQueue;
064                            
065                    }
066                    queue[naechsterLetzterWert] = wert;
067                    naechsterLetzterWert = (naechsterLetzterWert + 1) % queue.length;
068            }
069    
070            public boolean isEmpty() {
071                    return ersterWert == naechsterLetzterWert;
072            }
073    
074            public int remove() {
075                    int wert = 0;
076                    if (! isEmpty()) {
077                            wert = queue[ersterWert];
078                            ersterWert = (ersterWert + 1) % queue.length;
079                    }
080                    
081                    return wert;
082            }
083    
084    }