Zásobník je lineární datová struktura určená pro ukládání prvků a jejich opětovný výběr v opačném pořadí - poslední přidaný prvek je vybrán jako první (LIFO = last in first out). Typickým zásobníkem je například hromada talířů nebo knih poskládaných na sebe.

Zásobník je jedna z nejdůležitějších datových struktur v informatice. Používá se pro rekurzi, volání podprogramů, výpočty matematických výrazů, překlad formálních jazyků, zpracovávání procesorových instrukcí... setkáte se s ním tedy téměř na všech možných úrovních abstrakce - od fyzické implementace na úrovni hardware až po vysoce abstraktní implementace v aplikačních programovacích jazycích.

Zásobník v základní variantě poskytuje tyto funkce:

push(a)
vloží prvek a na vrchol zásobníku
pop()
vrátí vrchol zásobníku a vrchol odebere
peek()
vrátí vrchol zásobníku (beze změny)
diagram

Implementace

Rozhraní

package ds.stack;

/**
 * Stack implemented using linked list.
 * @author Vojtěch Hordějčuk
 */
public class LinkedStack<DATA> implements Stack<DATA> {
    private static class Node<DATA> {
        private DATA innerValue;
        private Node<DATA> next;
    }

    private Node<DATA> top;

    /**
     * Adds an element on the top of the stack.
     * @param value data to push
     */
    @Override
    public void push(final DATA value) {
        final Node<DATA> newTop = new Node<DATA>();
        newTop.innerValue = value;
        newTop.next = top;
        top = newTop;
    }

    /**
     * Pops an element from the stack top.
     * Throws exception if no element is present.
     * @return popped element (former stack top)
     */
    @Override
    public DATA pop() {
        if (top != null) {
            final DATA topValue = top.innerValue;
            top = top.next;
            return topValue;
        } else {
            throw new IllegalStateException("Stack underflow.");
        }
    }

    /**
     * Checks if the stack is empty.
     * @return TRUE if the stack is empty, FALSE otherwise
     */
    @Override
    public boolean isEmpty() {
        return top == null;
    }
}

Zdrojový kód Pokrytí testy

Pomocí spojového seznamu

Implementace využívající spojový seznam má teoreticky neomezenou kapacitu, ale prvky zabírají více paměti, než by mohly (ke každému prvku totiž náleží ukazatel na prvek následující).

package ds.stack;

/**
 * Stack implemented using linked list.
 * @author Vojtěch Hordějčuk
 */
public class LinkedStack<DATA> implements Stack<DATA> {
    private static class Node<DATA> {
        private DATA innerValue;
        private Node<DATA> next;
    }

    private Node<DATA> top;

    /**
     * Adds an element on the top of the stack.
     * @param value data to push
     */
    @Override
    public void push(final DATA value) {
        final Node<DATA> newTop = new Node<DATA>();
        newTop.innerValue = value;
        newTop.next = top;
        top = newTop;
    }

    /**
     * Pops an element from the stack top.
     * Throws exception if no element is present.
     * @return popped element (former stack top)
     */
    @Override
    public DATA pop() {
        if (top != null) {
            final DATA topValue = top.innerValue;
            top = top.next;
            return topValue;
        } else {
            throw new IllegalStateException("Stack underflow.");
        }
    }

    /**
     * Checks if the stack is empty.
     * @return TRUE if the stack is empty, FALSE otherwise
     */
    @Override
    public boolean isEmpty() {
        return top == null;
    }
}

Zdrojový kód Pokrytí testy

Pomocí pole

Implementace využívající pole má kapacitu omezenou shora velikostí pole.

package ds.stack;

/**
 * Array based stack with maximum capacity.
 * @author Vojtěch Hordějčuk
 */
public class ArrayStack<DATA> implements Stack<DATA> {
    private final DATA[] storage;
    private int top;

    /**
     * Creates a new instance.
     * @param capacity stack capacity (maximum number of elements to store)
     */
    public ArrayStack(final int capacity) {
        this.storage = (DATA[]) new Object[capacity];
        this.top = -1;
    }

    /**
     * Adds an element on the top of the stack.
     * @param value data to push
     */
    @Override
    public void push(final DATA value) {
        if (top == storage.length - 1) {
            throw new IllegalStateException("Stack overflow.");
        }

        storage[++top] = value;
    }

    /**
     * Pops an element from the stack top.
     * Throws exception if no element is present.
     * @return popped element (former stack top)
     */
    @Override
    public DATA pop() {
        if (top == -1) {
            throw new IllegalStateException("Stack underflow.");
        }

        return storage[top--];
    }

    /**
     * Checks if the stack is empty.
     * @return TRUE if the stack is empty, FALSE otherwise
     */
    @Override
    public boolean isEmpty() {
        return top == -1;
    }
}

Zdrojový kód Pokrytí testy

Reference