Fronta je lineární datová struktura určená pro ukládání prvků a jejich opětovný výběr ve stejném pořadí, v jakém byly do fronty přidány - nejstarší přidaný prvek je vybrán jako první (FIFO = first in first out). S frontami se setkáváme v každodenním životě a vyskytují se všude tam, kde je třeba férově vyřešit rozdílné rychlosti vstupů a výstupů, nebo jak odložit zpracování úloh na později a přitom zachovat jejich pořadí.

Fronta v základní variantě poskytuje tyto funkce:

enqueue(a)
vloží prvek a na konec fronty
dequeue()
vrátí první (nejstarší) prvek ze začátku fronty a odebere jej
diagram

Implementace

Rozhraní

package ds.queue;

/**
 * Queue implementation using array.
 *
 * @author Vojtěch Hordějčuk
 */
public class ArrayQueue<DATA> implements Queue<DATA> {
    private final DATA[] storage;
    private int top;
    private int bottom;

    public ArrayQueue(final int capacity) {
        this.storage = (DATA[]) new Object[capacity];
        this.top = -1;
        this.bottom = -1;
    }

    @Override
    public void enqueue(final DATA value) {
        if (top < 0) {
            // first element
            top = 0;
            bottom = 0;
            storage[0] = value;
        } else {
            final int bottomToBe = (bottom + 1) % storage.length;

            if (bottomToBe == top) {
                throw new IllegalStateException("Queue is full.");
            }

            bottom = bottomToBe;
            storage[bottom] = value;
        }
    }

    @Override
    public DATA dequeue() {
        if (top < 0) {
            throw new IllegalStateException("Queue is empty.");
        } else if (top == bottom) {
            // last element
            final DATA valueTuReturn = storage[top];
            storage[top] = null;
            top = -1;
            bottom = -1;
            return valueTuReturn;
        } else {
            final DATA valueTuReturn = storage[top];
            storage[top] = null;
            top = (top + 1) % storage.length;
            return valueTuReturn;
        }
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }
}

Zdrojový kód Pokrytí testy

Implementace 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.queue;

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

    private Node<DATA> first;
    private Node<DATA> last;

    @Override
    public void enqueue(final DATA value) {
        final Node<DATA> newLast = new Node<DATA>();
        newLast.innerValue = value;

        if (first == null) {
            // first element
            first = newLast;
            last = newLast;
        } else {
            last.next = newLast;
            last = newLast;
        }
    }

    @Override
    public DATA dequeue() {
        if (first == null) {
            throw new IllegalStateException("Queue is empty.");
        }

        final DATA valueToReturn = first.innerValue;

        if (first == last) {
            // last element
            first = null;
            last = null;
        } else {
            first = first.next;
        }

        return valueToReturn;
    }

    @Override
    public boolean isEmpty() {
        return first == null;
    }
}

Zdrojový kód Pokrytí testy

Implementace pomocí pole

Implementace fronty pomocí pole je zajímavá tím, že se pro dosažení maximálního využití paměti musí ukazatele po přejetí konce pole vrátit zpět na jeho začátek.

package ds.queue;

/**
 * Queue implementation using array.
 *
 * @author Vojtěch Hordějčuk
 */
public class ArrayQueue<DATA> implements Queue<DATA> {
    private final DATA[] storage;
    private int top;
    private int bottom;

    public ArrayQueue(final int capacity) {
        this.storage = (DATA[]) new Object[capacity];
        this.top = -1;
        this.bottom = -1;
    }

    @Override
    public void enqueue(final DATA value) {
        if (top < 0) {
            // first element
            top = 0;
            bottom = 0;
            storage[0] = value;
        } else {
            final int bottomToBe = (bottom + 1) % storage.length;

            if (bottomToBe == top) {
                throw new IllegalStateException("Queue is full.");
            }

            bottom = bottomToBe;
            storage[bottom] = value;
        }
    }

    @Override
    public DATA dequeue() {
        if (top < 0) {
            throw new IllegalStateException("Queue is empty.");
        } else if (top == bottom) {
            // last element
            final DATA valueTuReturn = storage[top];
            storage[top] = null;
            top = -1;
            bottom = -1;
            return valueTuReturn;
        } else {
            final DATA valueTuReturn = storage[top];
            storage[top] = null;
            top = (top + 1) % storage.length;
            return valueTuReturn;
        }
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }
}

Zdrojový kód Pokrytí testy

Reference