/** Eine Klasse fuer Queues ("Schlangen"). Eine Queue ist eine
    dynamische Datenstruktur, in die man eine beliebige hohe 
    Anzahl von Objekten einfuegen und die in ihr vorhandenen
    wieder aus herausnehmen kann. Dabei gilt das FIFO-Prinzip
    ("first in first out"): Das zuerst eingefuegte Element ist
    auch dasjenige, das zuerst herausgenommen wird - ganz wie
    bei einer Supermarkt-Schlange.
*/

public class FIFO
{
    private int length=2;
    private int readIndex,writeIndex;
    private Object[] queue;
    private int numberOfObjects;

    /** Erzeugt eine leere Schlange. */
    public FIFO()
    {
	queue = new Object[length];
	readIndex=0;
	writeIndex=0;
	numberOfObjects = 0;
    }

    /** Fuegt ein Element x in die Schlange ein.
	@param x das einzufuegende Element */
    public void in(Object x)
    {
	int nextWriteIndex = (writeIndex+1) % length;
	int i,j=0;
	int newLength;

	if (nextWriteIndex == readIndex)
	{
	    newLength = length*2;
	    Object[] auxQueue = new Object[newLength];

	    for (i=readIndex; i!=writeIndex; i=(i+1)%length)
	    {
		auxQueue[j] = queue[i];
		j++;
	    }
	    queue = auxQueue;
	    readIndex = 0;
	    writeIndex = length-1;
	    length = newLength;
	}
	queue[writeIndex] = x;
	writeIndex = (writeIndex+1) % length;
	
	numberOfObjects++;
    }

    /** Liefert aus einer nicht-leeren Schlange das Element, das unter den
	in der Schlange vorhandenen zuerst eingetragen wurde. Ist die
	Schlange leer, so wird null zurueckgeliefert.
	@return das Element */
    public Object out()
    {
	if (this.empty())
	{
	    return null;
	}
	Object y = queue[readIndex];
	readIndex = (readIndex+1) % length;
	numberOfObjects--;

	return y;
    }

    /** Testet, ob die Schlange leer ist. */
    public boolean empty()
    {
	return (readIndex == writeIndex);
    }
}