// 7. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises07.java
import java.util.ArrayDeque;

public class Exercises07 {

    // F1. Tízes -> kettes számrendszer veremmel (a maradékok fordított sorrendben adják az eredményt)
    static String toBinary(int n) {
        if (n == 0) return "0";
        ArrayDeque<Integer> s = new ArrayDeque<>();
        while (n > 0) {
            s.push(n % 2);
            n = n / 2;
        }
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pop());
        return sb.toString();
    }

    // F2. String megfordítása veremmel
    static String reverse(String str) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        for (char c : str.toCharArray()) s.push(c);
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pop());
        return sb.toString();
    }

    // F3. Minimum-verem: push, pop és min mind O(1). Egy második verem tárolja az eddigi minimumokat.
    static class MinStack {
        private final ArrayDeque<Integer> data = new ArrayDeque<>();
        private final ArrayDeque<Integer> mins = new ArrayDeque<>();

        void push(int x) {
            data.push(x);
            if (mins.isEmpty() || x <= mins.peek()) mins.push(x);
        }

        int pop() {
            int x = data.pop();
            if (x == mins.peek()) mins.pop();
            return x;
        }

        int min() { return mins.peek(); }
    }

    // F4. Visszavonás (undo) szövegszerkesztőben: minden művelet előtti állapotot verembe teszünk
    static void undoDemo() {
        ArrayDeque<String> history = new ArrayDeque<>();
        String text = "";
        String[] typed = { "Hello", ", ", "World", "!!!" };
        for (String t : typed) {
            history.push(text);
            text = text + t;
            System.out.println("  gépelés: \"" + text + "\"");
        }
        for (int i = 0; i < 2; i++) {
            text = history.pop();
            System.out.println("  undo:    \"" + text + "\"");
        }
    }

    // F5. Kódkövetés: betű = push, '*' = pop és kiírás
    static String trace(String ops) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();
        for (char c : ops.toCharArray()) {
            if (c == '*') out.append(s.pop());
            else if (c != ' ') s.push(c);
        }
        return out.toString();
    }

    // F6. Szomszédos azonos betűpárok ismételt törlése: "abbaca" -> "ca"
    static String removeAdjacentDuplicates(String str) {
        ArrayDeque<Character> s = new ArrayDeque<>();
        for (char c : str.toCharArray()) {
            if (!s.isEmpty() && s.peek() == c) s.pop();
            else s.push(c);
        }
        StringBuilder sb = new StringBuilder();
        while (!s.isEmpty()) sb.append(s.pollLast()); // alulról felfelé
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("F1. toBinary(50) = " + toBinary(50) + ", toBinary(13) = " + toBinary(13));
        System.out.println("F2. reverse(\"verem\") = " + reverse("verem"));
        MinStack ms = new MinStack();
        for (int x : new int[] { 5, 3, 7, 2, 8 }) ms.push(x);
        System.out.print("F3. min: " + ms.min());
        ms.pop();
        ms.pop();
        System.out.println(", két pop után: " + ms.min());
        System.out.println("F4. undo:");
        undoDemo();
        System.out.println("F5. trace(\"D A T * A * S * T R * U C * T\") = " + trace("D A T * A * S * T R * U C * T"));
        System.out.println("F6. removeAdjacentDuplicates(\"abbaca\") = " + removeAdjacentDuplicates("abbaca"));
    }
}