public class StackDanQueueManual {

    // ===== Stack berbasis array: masuk dan keluar lewat ujung yang sama =====
    static class StackArray {
        private String[] isi = new String[8];
        private int atas;   // jumlah elemen sekaligus indeks slot kosong teratas

        void push(String nilai) {
            if (atas == isi.length) {
                throw new IllegalStateException("Stack penuh");
            }
            isi[atas++] = nilai;
        }

        String pop() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            String nilai = isi[--atas];
            isi[atas] = null;   // lepaskan referensi agar garbage collector bekerja
            return nilai;
        }

        String peek() {
            if (atas == 0) {
                throw new IllegalStateException("Stack kosong");
            }
            return isi[atas - 1];
        }

        int ukuran() {
            return atas;
        }
    }

    // ===== Queue berbasis linked list: masuk di belakang, keluar di depan =====
    static class QueueLinked {
        static class Node {
            String data;
            Node next;

            Node(String data) {
                this.data = data;
            }
        }

        private Node depan;      // elemen keluar dari sini
        private Node belakang;   // elemen masuk dari sini
        private int ukuran;

        void enqueue(String nilai) {
            Node baru = new Node(nilai);
            if (belakang == null) {
                depan = baru;     // queue masih kosong
            } else {
                belakang.next = baru;
            }
            belakang = baru;
            ukuran++;
        }

        String dequeue() {
            if (depan == null) {
                throw new IllegalStateException("Queue kosong");
            }
            String nilai = depan.data;
            depan = depan.next;
            if (depan == null) {
                belakang = null;  // queue kembali kosong
            }
            ukuran--;
            return nilai;
        }

        int ukuran() {
            return ukuran;
        }
    }

    public static void main(String[] args) {
        System.out.println("=== Stack (LIFO) berbasis array ===");
        StackArray stack = new StackArray();
        stack.push("Budi");
        stack.push("Siti");
        stack.push("Dewi");
        System.out.println("peek()  : " + stack.peek());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("pop()   : " + stack.pop());
        System.out.println("ukuran(): " + stack.ukuran());

        System.out.println();
        System.out.println("=== Queue (FIFO) berbasis linked list ===");
        QueueLinked queue = new QueueLinked();
        queue.enqueue("Budi");
        queue.enqueue("Siti");
        queue.enqueue("Dewi");
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("dequeue(): " + queue.dequeue());
        System.out.println("ukuran() : " + queue.ukuran());
    }
}