public class Queue {
    private int first, last;
    private int[] a;

    public Queue() {
        first = last = -1;
        a = new int[4];
    }

    public boolean isEmpty() {
        return first == -1;
    }

    public String toString() {
        if (first == -1)
            return "[]";
        String result = "[" + a[first];
        int n = a.length;
        int end = (last + 1) % n;
        for (int i = (first + 1) % n; i != end; i = (i + 1) % n)
            result = result + ", " + a[i];
        return result + "]";
    }

    public void enqueue(int x) {
        if (first == -1) {
            first = last = 0;
            a[0] = x;
            return;
        }
        int n = a.length;
        last = (last + 1) % n;
        if (last == first) {
            int[] b = new int[2 * n];
            int t = first;
            for (int i = 0; i < n; ++i) {
                b[i] = a[t];
                t = (t + 1) % n;
            }
            first = 0;
            last = n;
            a = b;
        }
        a[last] = x;
    }

    public int dequeue() {
        int result = a[first];
        if (last == first) {
            first = last = -1;
        } else {
            first = (first + 1) % a.length;
        }
        return result;
    }

    public static void main(String args[]) {
        Queue queue = new Queue();
        for (int i = 0; i < 100; i++) {
            if (i % 4 == 2) {
                System.out.println("entfernt: " + queue.dequeue());
                System.out.println("[" + queue.a.length + "]: " + queue);
            }

            queue.enqueue(i);
            System.out.println("[" + queue.a.length + "]: " + queue);
        }
        while (!queue.isEmpty()) {
            System.out.println("entfernt: " + queue.dequeue());
            System.out.println("[" + queue.a.length + "]: " + queue);
        }
    }
} // end class Queue