public class Queue {

    private int first, last;
    private int[] arr;
    // Konstruktor:
    public Queue() {
        first = last = -1;
        arr = new int[4];
    }
    // Objekt-Methoden:
    public boolean isEmpty() { return first == -1; }
    public void enqueue(int x) {
        if (first == -1) {
            first = last = 0;
        } else {
            int n = arr.length;
            last = (last + 1) % n;
            if (last == first) {
                int[] b = new int[2*n];
                for (int i = 0; i < n; ++i) 
                    b[i] = arr[(first + i) % n];
                first = 0; 
                last  = n;
                arr   = b;
            } 
        } // end if and else
        arr[last] = x;
    }

    public int dequeue() {
        int result = arr[first];
        if (last == first) {
            first = last = -1;
            return result;
        }
        int n = arr.length;
        first = (first+1) % n;
        // Anzahl der Elemente ist (last-first) mod n + 1
        // aber % in Java ist keine modulo-Operation
        int num = (last-first+n) % n + 1;     
        if (num > 1 && num <= n/4) {
            int[] b = new int[n/2];
            for (int i = 0; i < num; ++i)
                b[i] = arr[(first + i) % n];
            first = 0;
            last = num - 1;    
            arr = b;
        }
        return result;
    }
    
    public String toString() {
        if (first == -1) return "[]";

        String res = "[";
        for (int i=0; i<arr.length; ++i) {
            res += i == first ? " ("
                :  i  > 0     ? ", "
                :               " ";

            res += arr[i];
            res += i == last ? ")" : "";
        }
        
        res += " ]";
        return res;
    }
    public static void main(String args[]) {
        Queue q = new Queue();

        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);
        q.enqueue(5);
        q.dequeue();
        q.dequeue();
        q.enqueue(6);
        q.enqueue(7);
        q.enqueue(8);
        q.enqueue(9);
        q.enqueue(10);
        System.out.println(""+q);
        while (q.isEmpty() == false) {
            int x = q.dequeue();
            System.out.println(x);
        }
    }
} // end of class Queue