public class SymmetricStack {

    private int[] data;
    private int first;
    private int last;

    public SymmetricStack() {
        data = new int[1];
        first = last = -1;
    }

    public int getFirst() {
        return first;
    }

    public void setFirst(int first) {
        this.first = first;
    }

    public int getLast() {
        return last;
    }

    public void setLast(int last) {
        this.last = last;
    }

    public int[] getData() {
        return data;
    }

    public void setData(int[] data) {
        this.data = data;
    }

    public int getNumberOfElements() {
        if (first == -1) return 0;
        
        if (last >= first) // -> Normalfall
            return last-first+1;
        else // -> letztes liegt vor ersten (zyklischer Shift)
            return data.length-(first-last-1);
    }
    
    public boolean isEmpty() {
        return first == -1;
    }
    
    public boolean isFull() {
        return getNumberOfElements() == data.length;
        // (last+1)%data.length == first
    }

    public void increase() {
        if (!isFull()) 
            return; // -> nicht verdoppeln, falls noch nicht voll
        
        int n = data.length; // Länge des alten Arrays (siehe Aufgabenstellung)
        
        int countElements = getNumberOfElements();
        
        int[] newStack = new int[n*2];
        for (int i = 0; i < countElements; i++) // für alle aktuell gespeicherten Elemente
            newStack[n/2+i] = data[(first+i)%n]; // kopieren
        data = newStack;
        
        first = n/2;
        last = first+n-1;
    }

    public void decrease() {
        if (getNumberOfElements() > data.length/4) 
            return; // -> nicht halbieren
        else if (isEmpty()) {
            if (data.length>1)
                data = new int[data.length/2];
        } else {
            int n = data.length; // Länge des alten Arrays (siehe Aufgabenstellung)
            int countElements = getNumberOfElements();

            int[] newStack = new int[n/2];
            last = n/8-1; // wir zählen last vor dem eintragen immer 1 hoch bis zum letzten Element

            for (int i = 0; i < countElements; i++) {
                newStack[++last] = data[first++];
                first %= n; // zyklisch weiterzählen im alten Array
                last %= (n/2); // ggf. nötig?
            }

            first = n/8;
            data = newStack;
        }
    }

    public void prepend(int x) {
        increase(); // vergrößern, falls nötig (increase entscheidet selbst)
        
        if (isEmpty()) // Stack noch leer -> first/last auf n/2 setzen
            first = last = data.length/2;
        else if (--first < 0) // first reduzieren
            first = data.length-1; // falls < 0 zyklisch von oben weitermachen
         
        data[first] = x; // Element schreiben
    }

    public void append(int x) {
        increase(); // vergrößern, falls nötig (increase entscheidet selbst)
        
        if (isEmpty()) // Stack noch leer -> first/last auf n/2 setzen
            first = last = data.length/2;
        else if (++last >= data.length) // first erhöhen
            last = 0; // falls zu groß zyklisch von unten weitermachen
        
        data[last] = x; // Element schreiben
    }

    public void removeFirst() {
        // Wirklich löschen müssen wir nichts, denn ob im Stack jetzt eine 0 oder
        // eine andere Zahl steht ist egal. Wir geben den Platz einfach frei,
        // indem wir den Zeiger umsetzen (dann wird der vorherige Wert nicht beachtet).
        
        if (!isEmpty()) { // -> Fehlerbehandlung (nichts zu entfernen)
            if (first == last) // last und first auf -1 setzen, falls dann leer
                first = last = -1;
            else if (++first >= data.length) { // first eins nach oben schieben; dann
                first = 0;    // ggf. wieder ganz unten bei 0
            }
        }
        decrease(); // ggf. verkleinern (decrease entscheidet selbst)
    }
    
    
    
    // removeLast ÄNDERN

    public void removeLast() {
        // Wirklich löschen müssen wir nichts (siehe removeFirst).
        
        if (!isEmpty()) { // -> Fehlerbehandlung (nichts zu entfernen)
            if (first == last) // last und first auf -1 setzen, falls numberOfElementens == 1
                last = first = -1;
            else if (--last < 0) {// last eins nach unten schieben; dann
                last = data.length-1;    // ggf. wieder ganz oben
            }
        }
        decrease(); // ggf. verkleinern (decrease entscheidet selbst)
    }

    @Override
    public String toString() {
        String out = "";
        for (int i = 0; i < data.length; i++) {
            if (first <= last && (i < first || i > last))
                out += "* ";
            if (first <= last && i > first && i < last)
                out += " " + data[i];
            if (first > last && i > last && i < first)
                out += "* ";
            if (first > last && (i > first || i < last))
                out += " " + data[i];
            if (i == first)
                out = out + "(" + data[i];
            if (i == last)
                out += (first == last ? "" : " " + data[i]) + ")";
        }
        return out;
    }
}