Stack/Queue/Deque/PriorityQueue

🛩️ Stack (스택)

• 스택 선언 및 사용 (push, pop, peek):

Stack<Integer> stack = new Stack<>();

stack.push(1);  // 스택에 1 추가
stack.push(2);  // 스택에 2 추가

System.out.println(stack.peek());  // 스택의 최상단 요소 반환 (2)

stack.pop();  // 스택에서 최상단 요소 제거 (2 제거)

System.out.println(stack.isEmpty());  // 스택이 비었는지 확인 (false)

• 문자열 괄호 유효성 검사 (스택 활용):

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    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 != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

---

🛩️ Queue (큐)

• 큐 선언 및 사용 (add, remove, peek):

Queue<Integer> queue = new LinkedList<>();

queue.add(1);  // 큐에 1 추가
queue.add(2);  // 큐에 2 추가

System.out.println(queue.peek());  // 큐의 첫 번째 요소 반환 (1)

queue.remove();  // 큐에서 첫 번째 요소 제거 (1 제거)

System.out.println(queue.isEmpty());  // 큐가 비었는지 확인 (false)

• BFS(너비 우선 탐색) 구현 (큐 활용):

public void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];

    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println("Visited: " + node);

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

---

🛩️ Deque (덱, 양방향 큐)

• 덱 선언 및 사용 (addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast):

Deque<Integer> deque = new LinkedList<>();

deque.addFirst(1);  // 덱의 앞쪽에 1 추가
deque.addLast(2);   // 덱의 뒤쪽에 2 추가

System.out.println(deque.peekFirst());  // 덱의 첫 번째 요소 확인 (1)
System.out.println(deque.peekLast());   // 덱의 마지막 요소 확인 (2)

deque.removeFirst();  // 덱의 첫 번째 요소 제거 (1 제거)
deque.removeLast();   // 덱의 마지막 요소 제거 (2 제거)

System.out.println(deque.isEmpty());  // 덱이 비었는지 확인 (true)

• 슬라이딩 윈도우 최대값 문제 (덱 활용):

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int[] result = new int[nums.length - k + 1];
    int idx = 0;

    for (int i = 0; i < nums.length; i++) {
        // 윈도우 범위를 벗어난 값 제거
        if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 덱 내에서 현재 값보다 작은 값 제거
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);  // 현재 인덱스를 덱에 추가

        // 윈도우가 k 크기에 도달하면 결과 배열에 최대값 추가
        if (i >= k - 1) {
            result[idx++] = nums[deque.peekFirst()];
        }
    }

    return result;
}

---

🛩️ PriorityQueue (우선순위 큐)

• 우선순위 큐 선언 및 사용 (add, poll, peek):

PriorityQueue<Integer> pq = new PriorityQueue<>();  // 기본적으로 최소 힙

pq.add(3);
pq.add(1);
pq.add(2);

System.out.println(pq.peek());  // 우선순위가 가장 높은 요소 반환 (1)

pq.poll();  // 우선순위가 가장 높은 요소 제거 (1 제거)

System.out.println(pq.peek());  // 이제 가장 높은 우선순위 요소는 2

• 최대 힙을 사용한 우선순위 큐 선언:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

maxHeap.add(3);
maxHeap.add(1);
maxHeap.add(2);

System.out.println(maxHeap.peek());  // 가장 큰 값 반환 (3)

• 다익스트라 알고리즘 (우선순위 큐 활용):

public int[] dijkstra(int start, List<List<int[]>> graph, int n) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.add(new int[] {start, 0});

    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int node = current[0];
        int distance = current[1];

        if (distance > dist[node]) continue;

        for (int[] neighbor : graph.get(node)) {
            int nextNode = neighbor[0];
            int weight = neighbor[1];

            if (dist[node] + weight < dist[nextNode]) {
                dist[nextNode] = dist[node] + weight;
                pq.add(new int[] {nextNode, dist[nextNode]});
            }
        }
    }

    return dist;
}

---

유용한 팁:

1. Stack은 DFS나 괄호 문제, 후위 표기법 계산 등에 자주 사용됩니다.

2. Queue는 BFS, 너비 우선 탐색 문제에서 필수적으로 사용됩니다.

3. Deque는 슬라이딩 윈도우 문제에서 양방향으로 삽입/제거를 빠르게 처리할 수 있어 효율적입니다.

4. PriorityQueue는 최소 힙/최대 힙을 이용한 우선순위 처리가 필요한 문제에서 유용하며, 다익스트라 알고리즘처럼 최단 경로 탐색에도 자주 사용됩니다.