Gihak111 Navbar

알고리즘 하면 딱 떠오르는 스택과 큐에 대해 알아보자.

먼저, 스택과 큐에 대해 알기 전에, 다음 자료 타입의 차이를 알아야 한다.

먼저, ADT의 관점에서 스택과 큐를 알아보자.

스택과 큐

사용 사례

둘의 사용사례를 알아보자.

기술 문서에서 큐를 만났을때

### 항상 FIFO 를 의미하진 않는다.  
1코어인 CPU가 p1, p2, p3의 일 3개를 멀티 캐스팅으로 실행된다고 하면, p1, p2, p3가 번갈아 가며 실행된다.  
p1이 실행중이면, p2, p3는 ready queue에 있게 된다.  
이런 경우에는 FIFO가 아닌, Priority Queue 즉 우선숭의 큐 에 해당한다.  
큐는 대기열로 사용될 때도 있기 때문에, 잘 봐야 한다.

스택/큐 관련 에러와 해결방법

중간에 Priority Queue가 나왔었다. 이도 알아보자.
우선순위 큐는 힙과 비교된다.

Priority Queue와 Heap

Priority Queue와 Heap

힘의 키를 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다.  
Priority queue = ADT  
Heap = data structure  
그래서 Priority queue 의 구현테가 Heap 이라고들 한다. 효울, 성능 모두 좋기 떄문이다.

사용 사례

힙 메모리의 heap은 이 heap과는 다르다.
heap의 사전적인 의미가 더미 이다. 힙 메모리는 사실 메모리 더미 그런거다.

예제를 통해서 알아보자.

예제 코드

  1. 스택 구현 예제
    ```java import java.util.Stack;

public class StackExample {

public static void main(String[] args) {
    // Stack 생성
    Stack<Integer> stack = new Stack<>();
    
    // Stack에 요소 추가 (push)
    stack.push(1);
    stack.push(2);
    stack.push(3);

    // Stack 상태: [1, 2, 3] (3이 가장 위에 있음)

    // 최상단 요소 확인 (peek)
    System.out.println("Top element: " + stack.peek()); // 출력: 3

    // Stack에서 요소 제거 (pop)
    System.out.println("Popped element: " + stack.pop()); // 출력: 3
    System.out.println("Top element after pop: " + stack.peek()); // 출력: 2

    // Stack 상태: [1, 2] (2가 가장 위에 있음)
} } ```
  1. 큐 구현 예제
    ```java import java.util.LinkedList; import java.util.Queue;

public class QueueExample {

public static void main(String[] args) {
    // Queue 생성
    Queue<Integer> queue = new LinkedList<>();
    
    // Queue에 요소 추가 (enqueue)
    queue.add(1);
    queue.add(2);
    queue.add(3);

    // Queue 상태: [1, 2, 3] (1이 가장 앞에 있음)

    // 가장 앞의 요소 확인 (peek)
    System.out.println("Front element: " + queue.peek()); // 출력: 1

    // Queue에서 요소 제거 (dequeue)
    System.out.println("Dequeued element: " + queue.poll()); // 출력: 1
    System.out.println("Front element after dequeue: " + queue.peek()); // 출력: 2

    // Queue 상태: [2, 3] (2가 가장 앞에 있음)
} }


3. 힘 구현 예제
```java
import java.util.PriorityQueue;

public class MinHeapExample {

    public static void main(String[] args) {
        // Min Heap 생성 (PriorityQueue를 사용)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // Min Heap에 요소 추가
        minHeap.add(3);
        minHeap.add(1);
        minHeap.add(2);

        // Min Heap 상태: [1, 3, 2] (가장 작은 값이 root에 있음)

        // 최소값 확인 (peek)
        System.out.println("Min element: " + minHeap.peek()); // 출력: 1

        // Min Heap에서 최소값 제거 (poll)
        System.out.println("Removed min element: " + minHeap.poll()); // 출력: 1
        System.out.println("Min element after poll: " + minHeap.peek()); // 출력: 2

        // Min Heap 상태: [2, 3] (2가 root에 있음)
    }
}
  1. 우선순위 큐 구현 예제 ```java import java.util.PriorityQueue;

class Task implements Comparable { private String name; private int priority;

public Task(String name, int priority) {
    this.name = name;
    this.priority = priority;
}

public String getName() {
    return name;
}

@Override
public int compareTo(Task other) {
    // 우선순위가 낮은 숫자가 더 높은 우선순위
    return Integer.compare(this.priority, other.priority);
}

@Override
public String toString() {
    return "Task{name='" + name + "', priority=" + priority + '}';
} }

public class PriorityQueueExample {

public static void main(String[] args) {
    // Priority Queue 생성
    PriorityQueue<Task> priorityQueue = new PriorityQueue<>();
    
    // 우선순위 큐에 작업 추가
    priorityQueue.add(new Task("Task 1", 3));
    priorityQueue.add(new Task("Task 2", 1));
    priorityQueue.add(new Task("Task 3", 2));

    // Priority Queue 상태: [Task 2, Task 1, Task 3] (우선순위가 낮은 숫자가 먼저 처리됨)

    // 가장 높은 우선순위 작업 확인 (peek)
    System.out.println("Highest priority task: " + priorityQueue.peek()); // 출력: Task 2

    // 우선순위 큐에서 작업 처리 (poll)
    System.out.println("Processing task: " + priorityQueue.poll()); // 출력: Task 2
    System.out.println("Next highest priority task: " + priorityQueue.peek()); // 출력: Task 3

    // Priority Queue 상태: [Task 3, Task 1] (우선순위에 따라 정렬됨)
} }

```

이제 다 이해했으리라 믿는다.

이 글은, 이 유튜브 영상을 참고하였다. https://www.youtube.com/watch?v=-2YpvLCT5F8 https://www.youtube.com/watch?v=P-FTb1faxlo