#

Stacks N Queues

Stacks und Queues gehören wohl zu den am Häufigsten benutzten Datenstrukturen. Um so trauriger ist ihr Fehlen in der Java API. Darum habe ich mir meine eigenen, performanten Varianten gebaut.

Zwar gibt es dort die Klasse java.util.Stack, jedoch erbt diese Klasse von Vector und ist damit sehr überladen und auch nicht sonderlich performant, weswegen die Vector Klasse auch durch die ArrayList Klasse abgelöst werden sollte.
Da ich eine performante Implementierung beider Strukturen benötigte, habe ich mir einige Performanz-Gedanken gemacht und diese Strukturen durch Interfaces definiert und schließlich mit verschieden Implementierungen umgesetzt.
Beide Interfaces, für Stack und für Queue, erben natürlich vom Interface Collection. Denn Stacks und Queues sind ebenfalls Collections.

  • Stack

  • Interface Stack
  • ArrayListStack
  • LinkedListStack
  • Queue

  • Interface Queue
  • Empty Queue Exception
  • NonDeletingArrayListQueue
  • LinkedListQueue
  • Fazit (Performanz)
  • Stack

    Auf das Prinzip eines Stack möchte ich hier nicht näher eingehen, es handelt es sich um eine triviale LIFO Datenstruktur.

    Für ein pop() auf ein leeren Stack existiert bereits die Klasse EmptyStackException, welche von der Stack Klassen in der API benutzt wird.

    Interface Stack

    import java.util.Collection;
    import java.util.EmptyStackException;
     
    /**
     * This interface provides stack (last in, first out = LIFO) functionality, 
     * that may be backed by any other datastructure.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public interface Stack extends Collection {
    /**
     * Looks at the object at the top of this stack without removing it from the stack.
     * 
     * @return
     * @throws EmptyStackException
     */
    public Object peek();
     
    /**
     * Removes the object at the top of this stack and returns that object as the value of this function.
     * 
     * @return
     * @throws EmptyStackException
     */
    public Object pop();
     
    /**
     * Pushes an item onto the top of this stack.
     * 
     * @param item
     * @return
     */
    public void push(Object item);
    }

    ArrayListStack

    ArrayList ist eine auf ein sehr schnelles Array basierende Datenstruktur mit dynamischer Größe, d.h. sie kann bei Bedarf wachsen. Aber genau dieses Wachsen kann zu Performanzverlusten führen, da intern ArrayList einen neuen größeren Array erzeugt und durch System.arrayCopy alle Werte des alten Arrays in das neue und größere Array kopiert. Daher wurde bei dieser Implementierung ein zusätzlicher Konstruktor mit einer Default-Kapazität erstellt und die Methode enshureCapacity(int capacity) eingefügt, um bei einem wiederverwerteten Stack die Mindestgröße sichern zu können. Möchte man beispielsweise einen Baum in Preorder durchlaufen, so ist es sinnvoll, vorher die Methode enshureCapacity mit der Anzahl an Knoten im Baum aufzurufen. So kann ein automatisches Vergrößern des Arrays nicht passieren und damit keine zusätzliche Performanz verschlingen.

    Intern werden neue Elemente an die höchste freie Arrayposition eingefügt. Würde man die Position 0 wählen, so müssten bei jedem push() / pop() alle folgenden Arrayelemente zum Anfang des Arrays verschoben werden, was wiederum zu einer miserablen Performanz führen würde.
    Damit die toArray-Methoden die Elemente des Stack in der Reihenfolge enthalten, die sie auch bei sukzesivem pop() Aufruf hätten, wird vor dem zurückliefern des Arrays dieser umgedreht (reverse). Schließlich befindet sich das nächste Element am höchsten Arrayindex.
    Auch wurde eine einfache Implementierung des Iterator-Interfaces umgesetzt, dass den Array in umgekehrter Reihenfolge iteriert, um ebenfalls die richtige pop() Reihenfolge zu erzeugen.

    Insgesamt ist somit der ArrayListStack mit vordefinierter Größe wohl der schnellste im Bezug auf die Operationen push, pop, peek und iterator. Lediglich wenn man das darunterliegende Array selber verwaltet, dürfte man etwas schneller werden.
    Wird die Größe nicht vordefiniert, so ist ArrayListStack immernoch sehr performant, man verschwendet jedoch etwas Zeit auf die automatische Vergrößerung der darunterliegenden ArrayList.
    Lediglich von der Speichergröße ist dieser Stack nicht optimal: Wird ein Stack mit n Elementen initialisiert, wird ein entsprechend großer Array reserviert, egal ob er gebraucht wird oder nicht.

    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.EmptyStackException;
    import java.util.Iterator;
    import java.util.NoSuchElementException;
     
    /**
     * This {@link Stack} is backed by an {@link java.util.ArrayList}.
     * The data is stored such, that the array position 0 contains the bottom of the stack.
     * Therefore the included {@link java.util.Iterator} iterates backwards through the array to have
     * the correct pop ordering for the elements.
     * Also the methods {@link #toArray()} and {@link #toArray(Object[])} return the elements in
     * the correct pop ordering for the elements.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public class ArrayListStack implements Stack, Serializable{
    private static final long serialVersionUID = 1L;
     
    private ArrayList stack;
     
    public ArrayListStack(){
    stack = new ArrayList();
    }
     
    public ArrayListStack(int capacity){
    stack = new ArrayList(capacity);
    }
     
    public void enshureCapacity(int capacity){
    stack.ensureCapacity(capacity);
    }
     
    public boolean isEmpty(){
    return stack.size()==0;
    }
     
    public Object peek(){
    if (stack.size()>0)return stack.get(stack.size()-1);
    else throw new EmptyStackException();
    }
     
    public Object pop(){
    if (stack.size()>0)return stack.remove(stack.size()-1);
    else throw new EmptyStackException();
    }
     
    public void push(Object item){
    stack.add(item);
    }
     
    public void clear(){
    stack.clear();
    }
     
    public int size() {
    return stack.size();
    }
     
    /**
     * Enshures, that the returned array has the same order as if {@link #pop()} was called.
     * Internaly the arraylist is beeing reversed.
     * 
     * @see java.util.Collection#toArray()
     */
    public Object[] toArray() {
    return reverse(stack.toArray());
    }
     
    /**
     * See {@link #push(Object)}
     * 
     * @see java.util.Collection#add(java.lang.Object)
     */
    public boolean add(Object o) {
    push(o);
    return true;
    }
     
    public boolean contains(Object o) {
    return stack.contains(o);
    }
     
    public boolean remove(Object o) {
    return stack.remove(o);
    }
     
    /**
     * See {@link #push(Object)}
     * 
     * @see java.util.Collection#addAll(java.util.Collection)
     */
    public boolean addAll(Collection c) {
    Iterator iter = c.iterator();
    for (int i=0; i<c.size(); i++){
    push(iter.next());
    }
    return true;
    }
     
    public boolean containsAll(Collection c) {
    return stack.containsAll(c);
    }
     
    public boolean removeAll(Collection c) {
    return stack.removeAll(c);
    }
     
    public boolean retainAll(Collection c) {
    return stack.retainAll(c);
    }
     
    /**
     * The {@link Iterator} returns it's items in the same order as {@link #pop()} would do.
     *  
     * @see java.util.Collection#iterator()
     * @see #pop()
     */
    public Iterator iterator() {
    return new ArrayListStackIterator(stack);
    }
     
    private static final Object[] reverse(Object[] array){
    Object tmp;
    int middle = (int) array.length/2;
    int rightOffset = array.length;
    for (int i=0; i>middle; i++){
    rightOffset--;
    tmp = array[i];
    array[i] = array[rightOffset];
    array[rightOffset] = tmp;
    }
    return array;
    }
     
    /**
     * Enshures, that the returned array has the same order as if {@link #pop()} was called.
     * Internaly the arraylist is beeing reversed.
     * 
     * @see java.util.Collection#toArray()
     */
    public Object[] toArray(Object[] a) {
    return reverse(stack.toArray(a));
    }
     
    public static class ArrayListStackIterator implements Iterator{
    private int actualIndex;
    private ArrayList stack;
     
    public ArrayListStackIterator(ArrayList stack){
    this.stack = stack;
    actualIndex = stack.size()-1;
    }
     
    /**
     * not implemented
     * 
     * @see java.util.Iterator#remove()
     */
    public void remove() {}
     
    public boolean hasNext() {
    if (actualIndex>-1) return true;
    return false;
    }
     
    public Object next() {
    if (actualIndex>-1) return stack.get(actualIndex--);
    throw new NoSuchElementException();
    }
    }
    }

    LinkedListStack

    LinkedList benutzt eine doppelt verkettete Liste als Datenstruktur. Entsprechend können Elemente an die erste Position in konstanter Zeit eingefügt werden. Daher ist es nicht nötig, wie bei ArrayList, einen speziellen Iterator zu erstellen oder die toArray Methoden umzuschreiben. Die LinkedList enthält an Position 0 immer das oberste Stackelement.

    Die Performanz dieses Stacks ist lediglich durch zwei Punkte etwas langsamer als der ArrayListStack: Bei einer LinkedList muss für jedes eingefügte Objekt ein neuer Listenknoten erzeugt werden.
    Ansonsten ist die LinkedList durch ihren Zugriff auf ihr erstes Element in konstanter Laufzeit ebenfalls sehr performant und dazu speichertreu, d. h. es wird immer nur die Menge an Speicher reserviert, wie Elemente im Stack vorhanden sind.

    import java.io.Serializable;
    import java.util.Collection;
    import java.util.EmptyStackException;
    import java.util.Iterator;
    import java.util.LinkedList;
     
    /**
     * This {@link Stack} is backed by an {@link java.util.LinkedList}.
     * The data is stored such, that the array position 0 contains the bottom of the stack.
     * The iterator from {@link #iterator()} as well as the methods {@link #toArray()} and {@link #toArray(Object[])} return the elements in
     * the correct pop ordering for the elements.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public class LinkedListStack implements Stack, Serializable{
    private static final long serialVersionUID = 1L;
     
    private LinkedList stack = new LinkedList();
     
    /**
     * Tests if this stack is empty.
     * 
     * @return
     */
    public boolean isEmpty(){
    return stack.isEmpty();
    }
     
    /**
     * Looks at the object at the top of this stack without removing it from the stack.
     * 
     * @return
     */
    public Object peek(){
    if (stack.size()>0) return stack.getFirst();
    else throw new EmptyStackException();
    }
     
    /**
     * Removes the object at the top of this stack and returns that object as the value of this function.
     * 
     * @return
     */
    public Object pop(){
    if (stack.size()>0) return stack.removeFirst();
    else throw new EmptyStackException();
    }
     
    /**
     * Pushes an item onto the top of this stack.
     * 
     * @param item
     * @return
     */
    public void push(Object item){
    stack.addFirst(item);
    }
     
    /**
     * Clears the stack, so it's empty
     */
    public void clear(){
    stack.clear();
    }
     
    public int size() {
    return stack.size();
    }
     
    /**
     * Enshures, that the returned array has the same order as if {@link #pop()} was called.
     * 
     * @see java.util.Collection#toArray()
     */
    public Object[] toArray() {
    return stack.toArray();
    }
     
    /**
     * See {@link #push(Object)}
     * 
     * @see java.util.Collection#add(java.lang.Object)
     */
    public boolean add(Object o) {
    push(o);
    return true;
    }
     
    public boolean contains(Object o) {
    return stack.contains(o);
    }
     
    public boolean remove(Object o) {
    return stack.remove(o);
    }
     
    /**
     * See {@link #push(Object)}
     * 
     * @see java.util.Collection#add(java.lang.Object)
     */
    public boolean addAll(Collection c) {
    Iterator iter = c.iterator();
    for (int i=0; i<c.size(); i++){
    push(iter.next());
    }
    return true;
    }
     
    public boolean containsAll(Collection c) {
    return stack.containsAll(c);
    }
     
    public boolean removeAll(Collection c) {
    return stack.removeAll(c);
    }
     
    public boolean retainAll(Collection c) {
    return stack.retainAll(c);
    }
     
    /**
     * The {@link java.util.Iterator} returns it's items in the same order as {@link #pop()} would do.
     *  
     * @see java.util.Collection#iterator()
     * @see #pop()
     */
    public Iterator iterator() {
    return stack.listIterator();
    }
     
    /**
     * Enshures, that the returned array has the same order as if {@link #pop()} was called.
     * 
     * @see java.util.Collection#toArray()
     */
    public Object[] toArray(Object[] a) {
    return stack.toArray(a);
    }
    }

    Queue

    Interface Queue

    import java.util.Collection;
    import java.util.EmptyStackException;
     
    /**
     * This interface provides queue (first in, first out = FIFO) functionality, 
     * that may be backed by any other datastructure.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public interface Queue extends Collection {
    /**
     * Looks at the next (first) object of this queue without removing it.
     * 
     * @return
     * @throws EmptyQueueException
     */
    public Object peekNext();
     
    /**
     * Looks at the last object of this queue without removing it.
     * 
     * @return
     * @throws EmptyQueueException
     */
    public Object peekLast();
     
    /**
     * Removes the next (first) object of this queue and returns that object as the value of this function.
     * 
     * @return
     * @throws EmptyQueueException
     */
    public Object pop();
     
    /**
     * Pushes/adds an item to the last position of this stack.
     * 
     * @param item
     * @return
     */
    public void push(Object item);
    }

    EmptyQueueException

    Da es im Gegensatz zur EmptyStackException kein Pendant in der API gibt, hier die EmptyQueueException.

    public class EmptyQueueException extends RuntimeException {
    private static final long serialVersionUID = 1L;
     
    public EmptyQueueException() {
    super();
    }
     
    public EmptyQueueException(String message) {
    super(message);
    }
     
    public EmptyQueueException(Throwable cause) {
    super(cause);
    }
     
    public EmptyQueueException(String message, Throwable cause) {
    super(message, cause);
    }
     
    }

    NonDeletingArrayListQueue

    ArrayLists sind, wie bereits festgestellt, sehr schnelle Datenstrukturen. Jedoch im Falle einer Queue kommt folgendes Performanz-Problem besonders zum tragen:
    Entfernt man aus einer ArrayList ein Element, das nicht an letzter Position ist, so müssen alle Elemente hinter dem entfernten Element um eine Position nach links (Richtung Anfang des Arrays) verschoben werden.
    Fügt man ein Element nicht an das Ende einer ArrayList ein, so müssen alle nachfolgenden Elemente nach rechts verschoben werden.
    Man kann also nicht wie beim Stack nur in einer Richtung Elemente einfügen und Entfernen. Dies führt dazu, dass eine einfache Implementierung, welche die Array-Elemente entfernt, sehr unperformant wird (um einige hundert Faktoren!).
    Um diese Problem zu umgehen wurde eine ArrayList Implementierung derart umgesetzt, dass entfernte Objekte aus der Queue nicht aus der ArrayList entfernt werden. Ein interner Zeiger zeigt lediglich auf das nächste Element.

    Damit ist die Laufzeit Performanz dieser Queue gerettet und auch sehr schnell. Der Nachteil liegt offen auf der Hand: Mit jeder Benutzung der Queue wächst die Anzahl der nicht benutzten Elemente in der Queue. Daher sollte bei Benutzung dieser Queue gelegentlich, am Besten vor ihrer Benutzung, die Methode clear() aufgerufen werden, welche den internen Zeiger wieder auf das erste Element setzt und damit die Arrayposition 0 wieder benutzt.

    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Iterator;
     
    /**
     * This queue implementation is back'ed by an ArrayList and doesn't delete pop'ed objects and thus grows constantly, but
     * is faster than removing poped objects. 
     * Invoking clear will remove all objects, also the old and pop'ed ones.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public class NonDeletingArrayListQueue implements Queue, Serializable {
    private static final long serialVersionUID = 1L;
     
    private ArrayList queue;
    private int firstIndex = 0;
     
    public NonDeletingArrayListQueue(){
    queue = new ArrayList();
    }
     
    public NonDeletingArrayListQueue(int capacity){
    queue = new ArrayList(capacity);
    }
     
    public void enshureCapacity(int capacity){
    queue.ensureCapacity(capacity+firstIndex);
    }
     
    public Object peekNext() {
    if (queue.size()>firstIndex) return queue.get(firstIndex);
    throw new EmptyQueueException();
    }
     
    public Object peekLast() {
    if (queue.size()>firstIndex) return queue.get(queue.size()-1);
    throw new EmptyQueueException();
    }
     
    public Object pop() {
    if (queue.size()>firstIndex) return queue.get(firstIndex++);
    throw new EmptyQueueException();
    }
     
    public void push(Object item) {
    queue.add(item);
    }
     
    public int size() {
    return queue.size()-firstIndex;
    }
     
    public void clear() {
    queue.clear();
    firstIndex = 0;
    }
     
    public boolean isEmpty() {
    return queue.isEmpty();
    }
     
    public Object[] toArray() {
    return queue.subList(firstIndex, queue.size()).toArray();
    }
     
    public boolean add(Object o) {
    return queue.add(o);
    }
     
    public boolean contains(Object o) {
    return queue.subList(firstIndex, queue.size()).contains(o);
    }
     
    public boolean remove(Object o) {
    return queue.subList(firstIndex, queue.size()).remove(o);
    }
     
    public boolean addAll(Collection c) {
    Iterator iter = c.iterator();
    for (int i=0; i<c.size(); i++)
    push(iter.next());
    return true;
    }
     
    public boolean containsAll(Collection c) {
    return queue.subList(firstIndex, queue.size()).containsAll(c);
    }
     
    public boolean removeAll(Collection c) {
    return queue.subList(firstIndex, queue.size()).removeAll(c);
    }
     
    public boolean retainAll(Collection c) {
    return queue.subList(firstIndex, queue.size()).retainAll(c);
    }
     
    public Iterator iterator() {
    return queue.subList(firstIndex, queue.size()).listIterator();
    }
     
    public Object[] toArray(Object[] a) {
    return queue.subList(firstIndex, queue.size()).toArray(a);
    }
    }

    LinkedListQueue

    Die LinkedList ist für Queues besonders gut geeignet, da sich das Problem der ArrayList hier nicht bemerkbar macht: Die LinkedList ermöglicht das Hinzufügen und Entfernen von Elementen sowohl am Anfang als auch am Ende in konstanter Laufzeit.

    Dennoch bleibt die kleine Performanzissue mit dem Erzeugen neuer Listenknoten beim Einfügen in die Liste.

    import java.io.Serializable;
    import java.util.Collection;
    import java.util.Iterator;
    import java.util.LinkedList;
     
    /**
     * This queue implementation is back'ed by an LinkedList.
     * 
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public class LinkedListQueue implements Queue, Serializable {
    private static final long serialVersionUID = 1L;
     
    private LinkedList queue = new LinkedList();
     
    public Object peekNext() {
    if (queue.size()>0) return queue.getFirst();
    throw new EmptyQueueException();
    }
     
    public Object peekLast() {
    if (queue.size()>0) return queue.getLast();
    throw new EmptyQueueException();
    }
     
    public Object pop() {
    if (queue.size()>0) return queue.removeFirst();
    throw new EmptyQueueException();
    }
     
    public void push(Object item) {
    queue.addLast(item);
    }
     
    public int size() {
    return queue.size();
    }
     
    public void clear() {
    queue.clear();
    }
     
    public boolean isEmpty() {
    return queue.isEmpty();
    }
     
    public Object[] toArray() {
    return queue.toArray();
    }
     
    public boolean add(Object o) {
    queue.addLast(o);
    return true;
    }
     
    public boolean contains(Object o) {
    return queue.contains(o);
    }
     
    public boolean remove(Object o) {
    return queue.remove(o);
    }
     
    public boolean addAll(Collection c) {
    Iterator iter = c.iterator();
    for (int i=0; i<c.size(); i++)
    push(iter.next());
    return true;
    }
     
    public boolean containsAll(Collection c) {
    return queue.containsAll(c);
    }
     
    public boolean removeAll(Collection c) {
    return queue.removeAll(c);
    }
     
    public boolean retainAll(Collection c) {
    return queue.retainAll(c);
    }
     
    public Iterator iterator() {
    return queue.listIterator();
    }
     
    public Object[] toArray(Object[] a) {
    return queue.toArray(a);
    }
    }

    Fazit

    Die folgenden Performanzvergleiche wurden nur grob durchgeführt, auf einem Rechner, der noch weitere Software installiert und aktiv hat. Dennoch sind die bei den jeweiligen Klassen besprochenen Performanz entscheidenen Punkte hier zu erkennen. Besonders die Listenknoten-Erzeugung bei der LinkedList ist Performanz relevant. Dennoch ist der Performanzmessung nicht zuviel Beachtung zu schenken.

    Klasse push 10^6 pop 10^6 push 10^7 pop 10^7
    ArrayListStack 109 63 1.188 609
    ArrayListStack mit enshureCapacity 47 47 531 609
    LinkedListStack 79 62 2.125 547
    java.util.Stack 453 140 891 1.172
    java.util.Stack mit enshureCapacity 94 125 688 1.312

    Klasse push 10^6 pop 10^6 push 10^7 pop 10^7
    LinkedListQueue 94 47 1.906 547
    NonDeletingArrayListQueue 641 31 1.140 344
    NonDeletingArrayListQueue mit enshureCapacity 78 62 453 359

    /**
     * @author <a href="http://www.graviton.de">M. Serhat Cinar</a>
     *
     */
    public class TestPerformances {
     
    /**
     * @param args
     */
    public static void main(String[] args) {
     
    final Class[] stacks = {ArrayListStack.class, LinkedListStack.class};
     
    final Object test = new Object();
     
    final Class[] queues = {LinkedListQueue.class, 
    NonDeletingArrayListQueue.class};
     
    final int amount[] = {1000000, 10000000};
     
    int i, j;
    long start, duration;
     
    Stack stack = null;
    ArrayListStack astack = null;
     
    for (i=0; i<stacks.length; i++){
    for (int a=0; a<amount.length; a++){
    try {
    stack = (Stack) stacks[i].newInstance();
    }
    catch (Exception e) {
    e.printStackTrace();
    }
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)stack.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(stack.getClass().getName()+
    " push "+amount[a]+" in "+duration+" ms");
     
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)stack.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(stack.getClass().getName()+
    " pop "+amount[a]+" in "+duration+" ms");
    }
    // test with predefined size
    if (stack instanceof ArrayListStack){
    for (int a=0; a<amount.length; a++){
    try{
    astack = (ArrayListStack) stacks[i].newInstance();
    }
    catch (Exception e) {
    e.printStackTrace();
    }
    astack.enshureCapacity(amount[a]);
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)stack.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(stack.getClass().getName()+
    " presized push "+amount[a]+" in "+duration+" ms");
     
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)stack.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(stack.getClass().getName()+
    " presized pop "+amount[a]+" in "+duration+" ms");
    }
    }
    }
     
    java.util.Stack jstack;
    for (int a=0; a<amount.length; a++){
    jstack = new java.util.Stack();
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)jstack.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(jstack.getClass().getName()+
    " push "+amount[a]+" in "+duration+" ms");
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)jstack.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(jstack.getClass().getName()+
    " pop "+amount[a]+" in "+duration+" ms");
    }
    // test with predefined size
    for (int a=0; a<amount.length; a++){
    jstack = new java.util.Stack();
    jstack.ensureCapacity(amount[a]);
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)jstack.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(jstack.getClass().getName()+
    " presized push "+amount[a]+" in "+duration+" ms");
     
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)jstack.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(jstack.getClass().getName()+
    " presized pop "+amount[a]+" in "+duration+" ms");
    }
     
     
    Queue queue = null;
    NonDeletingArrayListQueue aqueue = null;
    for (i=0; i<queues.length; i++){
    for (int a=0; a<amount.length; a++){
    try{
    queue = (Queue) queues[i].newInstance();
    }
    catch (Exception e) {
    e.printStackTrace();
    }
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)queue.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(queue.getClass().getName()+
    " push "+amount[a]+" in "+duration+" ms");
     
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)queue.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(queue.getClass().getName()+
    " pop "+amount[a]+" in "+duration+" ms");
    }
    // test with predefined size
    if (queue instanceof NonDeletingArrayListQueue){
    for (int a=0; a<amount.length; a++){
    try{
    aqueue = (NonDeletingArrayListQueue) 
    queues[i].newInstance();
    }
    catch (Exception e) {
    e.printStackTrace();
    }
    aqueue.enshureCapacity(amount[a]);
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)aqueue.push(test);
    duration = System.currentTimeMillis()-start;
    System.out.println(aqueue.getClass().getName()+
    " presized push "+amount[a]+" in "+duration+" ms");
     
    start = System.currentTimeMillis();
    for (j=0; j<amount[a]; j++)aqueue.pop();
    duration = System.currentTimeMillis()-start;
    System.out.println(aqueue.getClass().getName()+
    " presized pop "+amount[a]+" in "+duration+" ms");
    }
    }
    }
    }
    }
    Tags:, , , , , ,

    6 Responses to “Stacks N Queues” »»

    1. Comment by Toni | 18:33 07.08.06|X

      Sehr gute Zusammenfassung und Erklärung dieser Basisdatenstrukturen!! Die Leute in GM werden sich freuen…solltest vielleicht von http://www.graviton.de/ai mal hierher verlinken.

      …aber ich hätte mir noch die Testklasse gewünscht, mit der du die selbstgeschrieben Stacks getestet hast…und eine Gegenüberstellung zu java.util.Stack.

    2. Comment by Secco | 9:22 08.08.06|X

      Update: Habe nun die Testklasse um die java.util.Stack erweitert und auch hier gepostet.

    3. Comment by andrej | 14:05 08.08.06|X

      hast du dir mal auch die jakarta.collection lib angeschaut? es gibt auch mehrere konkurentprodukte aus dem os sektor. die jakartapackete knn man ja fast schon als bestandteil des jdk sehen 😉

    4. Comment by Secco | 8:06 09.08.06|X

      collections von apache kenne ich. aber ich habe noch keine performance-vergleiche gemacht. im übrigen sind das auch nicht die finalen klassen, wie ich sie benutzt habe. wegen performance habe ich die darunterliegenden arrays selber verwaltet und auf das collections interface verzichtet. auÃerdem habe ich die internen arrays mit einer fixen gröÃe initialisiert und push/pop positionen über indizes verwaltet. auch bounds der internen arrays habe ich nicht geprüft (zuviel push->arrayindexoutofboundsexception). lediglich die enshureCapacity methode habe ich noch zusätzlich implementiert, damit man die objekte wiederbenutzen kann. insgesamt dürfte die geschwindigkeit dieser klassen weit besser sein. aber sie sind halt nciht sehr collection like.

    5. Comment by Ralf | 18:05 13.08.06|X

      hi, ein kleiner hinweis am rande… hast du schonmal in die api von java 5 geschaut, da gibt es jetzt auch eine queue implementierung 😉 ein weiterer blick verrät, dass stack bereits seit java 1.0 im package java.util vorhanden ist

    6. Comment by Secco | 20:22 13.08.06|X

      Queue ist, wie ich sehe wirklich gut definiert, mit einem Interface. Tatsächlich arbeite ich hauptsächlich noch mit Java 1.4. Aber den Stack haben sie noch nicht verbessert.
      Danke für den Hinweis.

    Leave a Reply »»

    Note: All comments are manually approved to avoid spam. So if your comment doesn't appear immediately, that's ok. Have patience, it can take some days until I have the time to approve my comments.