[자바(JAVA)] Stack & Queue의 활용(PriorityQueue, Deque)

Stack & Queue

📌 스택의 활용: 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 앞으로/ 뒤로

📌 큐의 활용: 최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)

 

 

---

 

 

✅ 예시(1) Stack의 활용

 

괄호가 안맞는 경우 isEmpty()가 false임

 

 

---

✅ 예시(2) Queue의 활용

최대 저장을 5개로 지정하면 이런식으로 제일 처음 기입된 내역이 밀려나간다.(FIFO)

 

 

 

TIP)
1.
if(input!=null && !input.equals("")
-> if(!"".equals(input)
==> NullPointerException 방지함

2.
s.nextLine().trim();
-> Scanner입력시 공백만 입력하면 무시한다.

 

 

 

✅ 예시(3) Queue의 활용_PriorityQueue

- Queue인터페이스 구현체중 하나로, 저장한 순서에 관계없이 우선순위가 높은것부터 꺼내는 특징이 있다.

그리고 null은 지정할 수 없다(예외터짐)

- 저장공간으로 배열을 사용하고 있으며, 각 요소를 힙(heap)이라는 자료구조로 저장한다.

 

 

우선순위란?

기본적으로 작은 값이 우선순위가 높습니다. 이를 "작은 요소 우선" 또는 "최소 힙(Min Heap)"이라고 합니다. 따라서 우선순위 큐에서 poll() 메서드를 호출하면 가장 작은 요소가 반환됩니다.

하지만 PriorityQueue는 우리가 원하는 순서로도 설정할 수 있습니다. 이를 "커스텀 우선순위"라고 합니다. PriorityQueue는 생성자에 Comparator를 제공하거나 요소를 추가할 때 Comparator 객체를 지정하여 우선순위를 커스텀할 수 있습니다.

Comparator를 이용하여 최대 힙(Max Heap)으로 만들거나, 다른 정렬 기준에 따라 우선순위를 결정할 수 있습니다. 예를 들어, PriorityQueue에 특정 객체들을 추가할 때, 특정 필드를 기준으로 우선순위를 설정할 수 있습니다.

 

 

import java.util.PriorityQueue;
import java.util.Comparator;

// 최대힙 예시
public class Main {
    public static void main(String[] args) {
        // Comparator를 이용하여 최대 힙(Max Heap)으로 만듦
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        maxHeap.add(5);
        maxHeap.add(2);
        maxHeap.add(8);
        maxHeap.add(1);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 출력: 8, 5, 2, 1 (내림차순 정렬)
        }
    }
}

 

요약하자면, PriorityQueue는 기본적으로 작은 값이 우선순위가 높지만, 사용자가 Comparator를 이용하여 원하는 순서로도 설정할 수 있다.

또한 객체를 저장할 수도 있는데 대신 각 객체의 크기를 비교할 수  있는 방법을 제공해줘야 한다.

따라서 커스텀 우선순위를 활용하여 다양한 우선순위 큐를 만들 수 있다.

 

 

 

✅ 예시(4) Queue의 활용_Deque

Queue의 변형으로 양쪽 끝에 추가/ 삭제가 가능하다.

덱은 스택과 큐를 하나로 합쳐둔것과 같으며, 스택으로도 사용이 가능하고 큐로도 사용이 가능하다.