스택 / 큐

/* ── 배열 기반 스택 직접 구현 ───────────────────────────── */
public class ArrayStack<T> {
    private Object[] data;
    private int top = -1;

    public ArrayStack(int capacity) {
        data = new Object[capacity];
    }

    public void push(T item) {
        if (top == data.length - 1) throw new RuntimeException("Stack Overflow");
        data[++top] = item; // top 먼저 올리고 저장
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (top == -1) throw new RuntimeException("Stack Underflow");
        T item = (T) data[top];
        data[top--] = null; // GC 참조 해제 후 top 낮춤
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (top == -1) throw new RuntimeException("Empty Stack");
        return (T) data[top]; // top만 반환, 제거 안 함
    }

    public boolean isEmpty() { return top == -1; }
    public int size()       { return top + 1; }
}

/* ── Java 표준 — ArrayDeque를 Stack으로 사용 (권장) ─────── */
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);       // = addFirst(), 앞에 추가
stack.push(20);
stack.pop();          // = removeFirst(), 20 반환 — LIFO
stack.peek();         // = peekFirst(), 제거 없이 조회

// Stack 클래스보다 ArrayDeque를 권장하는 이유:
// Stack은 Vector 상속 → 모든 메서드 synchronized → 불필요한 동기화 비용
// ArrayDeque는 동기화 없음 → 단일 스레드에서 훨씬 빠름

/* ── 활용 예: 괄호 유효성 검사 ─────────────────────────── */
public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    return stack.isEmpty();
}

/* ── 원형 배열 큐 직접 구현 ─────────────────────────────── */
public class CircularQueue<T> {
    private Object[] data;
    private int front = 0, rear = 0, size = 0;
    private final int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        data = new Object[capacity];
    }

    public void enqueue(T item) {
        if (size == capacity) throw new RuntimeException("Queue Full");
        data[rear] = item;
        rear = (rear + 1) % capacity; // 원형 인덱스 — 끝에 도달하면 0으로
        size++;
    }

    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (size == 0) throw new RuntimeException("Queue Empty");
        T item = (T) data[front];
        data[front] = null;
        front = (front + 1) % capacity; // front도 원형으로 이동
        size--;
        return item;
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull()  { return size == capacity; }
}

/* ── Java 표준 — ArrayDeque를 Queue로 사용 (권장) ──────── */
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);    // enqueue — 실패 시 false 반환 (add는 예외)
queue.offer(20);
queue.poll();     // dequeue — 10 반환, 비어있으면 null (remove는 예외)
queue.peek();     // front 조회 — 제거 없음, 비어있으면 null

/* ── 활용 예: BFS (너비 우선 탐색) ──────────────────────── */
public void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[graph.size()];
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll(); // FIFO — 가장 먼저 넣은 노드부터 처리
        System.out.print(node + " ");
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next); // 인접 노드를 rear에 추가
            }
        }
    }
}