큐(Queue)

1. 큐(Queue)란?

- 큐는 데이터를 순서대로 저장하는 자료구조로, 먼저 추가된 데이터가 먼저 제거되는 선입선출(FIFO: First In First Out) 방식을 따른다.

- 큐는 주로 작업 스케줄링, 프로세스 관리, BFS 등의 알고리즘에 활용된다.

- 자바에서는 Queue 인터페이스를 통해 큐를 다루며, 구현체로는 LinkedList와 ArrayDeque가 있다.

 

2. 주요 메소드

- offer(E element): 큐의 맨 뒤에 요소를 추가한다.

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

queue.offer("Apple"); // 큐의 맨 뒤에 "Apple" 추가

 

- poll(): 큐의 맨 앞에 있는 요소를 제거한다.

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

queue.offer("Apple");
queue.offer("Banana");

queue.poll(); // 큐의 맨 앞에 있는 "Apple" 제거

 

- peek(): 큐의 맨 앞에 있는 요소를 조회한다.

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

queue.offer("Apple");
queue.offer("Banana");

queue.peek(); // 큐의 맨 앞에 있는 "Apple" 조회

 

3. 우선순위 큐(Priority Queue)

- 우선순위 큐(Priority Queue)란 큐와 유사하지만 데이터가 저장된 순서가 아닌 우선순위에 따라 요소를 처리하는 자료구조이며 비교할 수 없는 객체는 큐를 만들 수 없다..

- 내부 구조는 이진트리 힙으로 구성되어 있어 삽입/삭제는 O(logN)의 복잡도를 가진다.

- 요소들이 자연 순서 또는 지정한 Comparator에 따라 정렬되어 관리되며, 가장 높은 우선순위를 가진 요소가 먼저 제거된다.

- 우선순위 큐는 작업 스케줄링, 다익스트라, 이벤트 처리 등에서 자주 사용된다.

 

3-1. 기본 우선순위 큐

public class PriorityQueueExample {
	public static void main(String[] args) {
    	
        // 내림차순은 Collections.reverseOrder() 사용
        PriorityQueue<Integer> pq = new PrirorityQueue<>();
        
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        
        // 우선순위 큐는 오름차순으로 정렬되므로 1, 3, 5 순서로 제거된다.
        while(!pq.isEmpty()) {
        	System.out.println(pq.poll());
        }

    }
}

 

3-2. Comparator 적용 우선순위 큐

class Fruit {
	String name;
    int priority; // 낮은 숫자가 높은 우선순위라고 가정함
    
    public Fruit(String name, int priority) {
    	this.name = name;
        this.priority = priority;
    }
}

public class PriorityQueueComparatorExample {
	public static void main(String[] args) {
    
    	// Fruit 객체를 우선순위에 따라 오름차순 정렬하도록 Comparator 지정
    	PriorityQueue<Fruit> fpq = new PriorityQueue<>(new Comparator<Fruit>() {
        	@Override
            public int compare(Fruit f1, Fruit f2) {
            	// 내림차순으로 정렬하고 싶다면 f2-f1으로 순서를 뒤집으면 됨
            	return f1.priority - f2.priority;
            }
        });
        
        fpq.offer("Apple", 3);
        fpq.offer("Banana", 1);
        fpq.offer("cherry", 2);
        
        // 우선순위가 높은 순으로 작업 처리, "Banana", "Cherry", "Apple" 순으로 출력
        while(!fpq.isEmpty()) {
        	System.out.println(fpq.poll());
        }
    
    }
}

 

4. 큐 활용 알고리즘

4-1. 카드 큐

- 카드 큐는 1부터 N까지 숫자가 적힌 카드를 큐에 넣고 맨 앞 카드를 버리고 그 다음, 큐의 맨 앞 카드를 꺼내서 큐의 맨 뒤로 옮기는 행동을 마지막 한장이 남을 때까지 반복한다,

public class CardQueueExample {
	public statoc void main(String[] args) {
    
    	int N = 7;
        Queue<Integer> queue = new LinkedList<>();
        
        // 1부터 N까지 큐에 추가
        for (int i = 1; i <= N; i++) {
       		queue.offer(i);
        }
        
        while(queue.size() > 1) {
        	// 1. 맨 앞 카드 제거
            queue.poll();
            
            // 2. 맨 앞 카드를 맨 뒤에 추가
            queue.offer(queue.poll());        
        }
        
        // 마지막 남은 카드 출력
        System.out.println(queue.poll());
    
    }
}