Ein Stack in Java.


Suche nach bestehenden Lösungen

Wenn man nach einem Stack für Java sucht, stößt man auf java.util.Stack<E> und meint, damit gefunden zu haben, was man braucht. Neben einer etwas seltsamen search-Methode und einer etwas eigenartig benannten empty-Methode stößt man bald darauf, dass java.util.Stack die Klasse java.util.Vector erweitert, statt sie zu verwenden.

Dies verstößt gegen die Regel "composition over inheritance" ("Komposition über/vor Vererbung"). Damit hat ein java.util.Stack-Objekt Methoden, die es nicht nach außen haben sollte. Dies ist sehr schlechtes Design. So wird einem bald klar:

Ein eigener Stack muss her!

Was sollte ein Stack an Methoden bieten?

Meiner Ansicht nach reichen für einen Stapel Stack<E> die folgenden Methoden:

Die Implementierung eines eigenen Stacks

Meine Implementation eines Stapels ist unter de.duehl.basics.collections.Stack zu finden. So sieht der Quellcode aus:

Stack<E>

package de.duehl.basics.collections;

import java.util.ArrayList;
import java.util.List;

public class Stack<E> {

    private final List<E> stackElements;

    public Stack() {
        stackElements = new ArrayList<>();
    }

    public void push(E element) {
        stackElements.add(element);
    }

    public boolean isEmpty() {
        return stackElements.isEmpty();
    }

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Der Stack ist leer!");
        }
        else {
            int lastIndex = stackElements.size() - 1;
            E lastElement = stackElements.get(lastIndex);
            stackElements.remove(lastIndex);
            return lastElement;
        }
    }

    @Override
    public String toString() {
        return "Stack [stackElements=" + stackElements + "]";
    }

    public void clear() {
        stackElements.clear();
    }

}

Ausnahmeklasse

Die verwendete Ausnahme EmptyStackException liegt im gleichen Paket und sieht so aus:

EmptyStackException

package de.duehl.basics.collections;

public class EmptyStackException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public EmptyStackException(String errorMessage) {
        super(errorMessage);
    }

}

Tests

Natürlich habe ich bei der Entwicklung auch passende Tests dazu geschrieben:

Tests

    @Test
    public void create() {
        Stack stack = new Stack<>();
        assertNotNull(stack);
    }

    @Test (expected = EmptyStackException.class)
    public void failOnPopEmptyStack() {
        Stack stack = new Stack<>();
        stack.pop();
    }

    @Test
    public void pushAndPopOneElement() {
        Stack stack = new Stack<>();
        stack.push("foo");

        String actual = stack.pop();
        String expected = "foo";
        assertEquals(expected, actual);
    }

    @Test
    public void pushAndPopTwoElements() {
        Stack stack = new Stack<>();
        stack.push("foo");
        stack.push("bar");

        String actual1 = stack.pop();
        String expected1 = "bar";
        assertEquals(expected1, actual1);

        String actual2 = stack.pop();
        String expected2 = "foo";
        assertEquals(expected2, actual2);
    }

    @Test
    public void pushAndPopThreeElements() {
        Stack stack = new Stack<>();
        stack.push("foo");
        stack.push("bar");
        stack.push("baz");

        String actual1 = stack.pop();
        String expected1 = "baz";
        assertEquals(expected1, actual1);

        String actual2 = stack.pop();
        String expected2 = "bar";
        assertEquals(expected2, actual2);

        String actual3 = stack.pop();
        String expected3 = "foo";
        assertEquals(expected3, actual3);
    }

    @Test (expected = EmptyStackException.class)
    public void pushThreeElementsAndFailOnPopFourElements() {
        Stack stack = new Stack<>();
        stack.push("foo");
        stack.push("bar");
        stack.push("baz");

        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
    }

    @Test
    public void emptyStackIsEmpty() {
        Stack stack = new Stack<>();
        assertTrue(stack.isEmpty());
    }

    @Test
    public void notEmptyStackIsNotEmpty() {
        Stack stack = new Stack<>();
        stack.push("foo");
        assertFalse(stack.isEmpty());
    }

    @Test
    public void clearedEmptyStackIsEmpty() {
        Stack stack = new Stack<>();
        stack.clear();
        assertTrue(stack.isEmpty());
    }

    @Test
    public void clearedNotEmptyStackIsEmpty() {
        Stack stack = new Stack<>();
        stack.push("foo");
        stack.clear();
        assertTrue(stack.isEmpty());
    }

    @Test
    public void testToString() {
        Stack stack = new Stack<>();
        stack.push("foo");
        stack.push("bar");
        stack.push("baz");

        String actual = stack.toString();
        String expected = "Stack [stackElements=[foo, bar, baz]]";
        assertEquals(expected, actual);
    }

Diese Tests werden natürlich alle erfüllt und zeigen zum einen die Verwendung und stellen zum anderen sicher, dass der Stack so arbeitet, wie ich es mir wünsche.

Anmerkungen

Die Methode E pop() ließe sich refakturieren. Aktueller Zustand:

pop() - aktueller Zustand

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Der Stack ist leer!");
        }
        else {
            int lastIndex = stackElements.size() - 1;
            E lastElement = stackElements.get(lastIndex);
            stackElements.remove(lastIndex);
            return lastElement;
        }
    }

Mögliche Verbesserung:

pop() - mögliche Verbesserung

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Der Stack ist leer!");
        }
        else {
            return popNotEmptyStack();
        }
    }

    private E popNotEmptyStack() {
        int lastIndex = stackElements.size() - 1;
        E lastElement = stackElements.get(lastIndex);
        stackElements.remove(lastIndex);
        return lastElement;
    }

Allerdings sollte man meinem Empfinden nach die Methode E popNotEmptyStack() nicht auf die folgende Variante verkürzen:

popNotEmptyStack - nicht empfehlenswert

    private E popNotEmptyStack() {
        return stackElements.remove(stackElements.size() - 1);
    }

Nach meinem Empfinden ist die obere Variante in vier Zeilen deutlich selbsterklärender und weist besser darauf hin, was dort alles passiert. So etwas würde ich nur entsprechend vereinfachen, sollte sie sich definitiv als Flaschenhals entpuppen.

Das Empfinden darüber mag aber von Entwickler zu Entwickler abweichen.

zu meiner Javaseite zu meiner Javaseite

zur Startseite des Servers zur Startseite des Servers

Impressum

Valid CSS! Valid XHTML 1.0!

TOP Zum Seitenanfang

zuletzt geändert: