// 11. hét – Verem és sor láncolt listával (generikus)
// Futtatás: java LinkedStackQueue.java
public class LinkedStackQueue {

    // Közös interfész: a felhasználó nem tudja (és nem is kell tudnia), hogyan van megvalósítva
    interface Stack<T> {
        void push(T x);
        T pop();
        boolean isEmpty();
    }

    static class Node<T> {
        T value;
        Node<T> next;
        Node(T v, Node<T> n) { value = v; next = n; }
    }

    // Verem listával: a teteje a lista eleje – push és pop O(1), nincs "tele" állapot
    static class LinkedStack<T> implements Stack<T> {
        private Node<T> top;

        public void push(T x) { top = new Node<>(x, top); }

        public T pop() {
            if (top == null) throw new IllegalStateException("üres verem");
            T x = top.value;
            top = top.next;
            return x;
        }

        public boolean isEmpty() { return top == null; }
    }

    // Verem tömbbel (7. hét) – ugyanaz az interfész
    static class ArrayStack<T> implements Stack<T> {
        private final java.util.ArrayList<T> data = new java.util.ArrayList<>();
        public void push(T x) { data.add(x); }
        public T pop() { return data.remove(data.size() - 1); }
        public boolean isEmpty() { return data.isEmpty(); }
    }

    // Sor listával: kivétel az elejéről (front), betétel a végére (rear) – mindkettő O(1)
    static class LinkedQueue<T> {
        private Node<T> front, rear;
        private int size;

        void enqueue(T x) {
            Node<T> n = new Node<>(x, null);
            if (rear == null) front = n;   // üres sor volt
            else rear.next = n;
            rear = n;
            size++;
        }

        T dequeue() {
            if (front == null) throw new IllegalStateException("üres sor");
            T x = front.value;
            front = front.next;
            if (front == null) rear = null; // kiürült: a rear-t is nullázni kell!
            size--;
            return x;
        }

        boolean isEmpty() { return front == null; }
        int size() { return size; }
    }

    // A felhasználó kódja csak az interfészt látja
    static String reverse(String s, Stack<Character> st) {
        for (char c : s.toCharArray()) st.push(c);
        StringBuilder sb = new StringBuilder();
        while (!st.isEmpty()) sb.append(st.pop());
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println("reverse listás veremmel: " + reverse("adatszerkezet", new LinkedStack<>()));
        System.out.println("reverse tömbös veremmel: " + reverse("adatszerkezet", new ArrayStack<>()));

        LinkedQueue<String> q = new LinkedQueue<>();
        q.enqueue("Li");
        q.enqueue("Wang");
        q.enqueue("Chen");
        System.out.print("sor: dequeue = " + q.dequeue());
        q.enqueue("Anna");
        System.out.print(", maradék: ");
        while (!q.isEmpty()) System.out.print(q.dequeue() + " ");
        System.out.println();
    }
}