import java.util.*;

class PrioKø<T extends Comparable<T>> implements Kø<T>, Iterable<T> {

    private Node<T> første = null;
    private int størrelse = 0;

    private static class Node<T> {

        T element;
        Node<T> neste;

        public Node(T element) {
            this.element = element;
            this.neste = null;
        }
    }

    @Override
    public boolean erTom() {
        return størrelse == 0;
    }

    @Override
    public int størrelse() {
        return størrelse;
    }

    @Override
    public T hvemErNeste() {
        if (erTom()) {
            return null;
        }
        return første.element;
    }

    @Override
    public void inn(T element) {
        Node<T> ny = new Node<>(element);
        størrelse++;
        // Hvis køen er tom eller høyest prioritet
        if (første == null || element.compareTo(første.element) < 0) {
            ny.neste = første;
            første = ny;
            return;
        }
        // Finn plass etter prioritet
        Node<T> søker = første;
        while (
            søker.neste != null && element.compareTo(søker.neste.element) >= 0
        ) {
            søker = søker.neste;
        }
        // Funnet plassen
        ny.neste = søker.neste;
        søker.neste = ny;
    }

    @Override
    public T ut() {
        if (erTom()) {
            return null;
        }
        T element = første.element;
        første = første.neste;
        størrelse--;
        return element;
    }

    @Override
    public Iterator<T> iterator() {
        return new KøIterator();
    }

    private class KøIterator implements Iterator<T> {

        private Node<T> gjeldende = første;

        @Override
        public boolean hasNext() {
            return gjeldende != null;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            T element = gjeldende.element;
            gjeldende = gjeldende.neste;
            return element;
        }
    }
}