[JAVA]Queue

Queue의 이해

Queue란?

1. FIFO(First In, First Out) 방식의 자료구조로, 먼저 들어간 요소가 먼저 나오는 구조
2. 현실에서 흔히 볼 수 있는 줄 서기(대기열)와 같음
3. 고객센터에 먼저 전화를 한 사람이 먼저 상담을 받고 나감(선입선출)
4. 새로 온 사람은 맨 뒤에 줄을 섬

Priority Queue와 Circular Queue

1. 우선순위 큐(Priority Queue)

1. 값의 크기(우선순위)에 따라 먼저 나오는 큐
2. 일반적인 큐는 선인선출로 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐는 우선순위가 높은 데이터가 먼저 나온다는 차이점
3. ex) 응급실 환자 진료(심정지 환자가 감기환자보다 먼저 진료받음)
4. 동작 과정

삽입 데이터	현재 큐 상태
5 추가	[5]
1 추가	[1, 5]
3 추가	[1, 3, 5]
4 추가	[1, 3, 4, 5]
poll() 실행	1 제거 → [3, 4, 5]
poll() 실행	3 제거 → [4, 5]

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 기본적으로 작은 값이 먼저 나옴 (Min Heap)

        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(4);

        System.out.println("우선순위 큐 상태: " + pq);  // 내부적으로 정렬

        while (!pq.isEmpty()) {
            System.out.println("처리 중: " + pq.poll()); // 우선순위가 높은 요소(작은 값)부터 출력
        }
    }
}

2. 원형 큐(Circular Queue)

1. 배열 기반 큐에서 빈 공간을 효율적으로 활용하는 자료구조

2. 일반적인 큐는 앞에서 데이터를 빼면 빈 공간이 생겨 비효율적

3. 원형 큐는 앞의 빈 공간을 재사용 할 수 있도록 순환 구조

4. 사용 이유: 메모리 낭비 최소화, 고정 배열을 유지하면서 효율적 활용

-----------------------초기 상태------------------------------
Front = 0, Rear = -1
[ _, _, _, _, _ ]
-----------------------데이터 삽입----------------------------
A 추가: [ A, _, _, _, _ ]  (Front=0, Rear=0)
B 추가: [ A, B, _, _, _ ]  (Front=0, Rear=1)
C 추가: [ A, B, C, _, _ ]  (Front=0, Rear=2)
-----------------------데이터 제거----------------------------
A 제거: [ _, B, C, _, _ ]  (Front=1, Rear=2)
B 제거: [ _, _, C, _, _ ]  (Front=2, Rear=2)
--------------새로운 데이터 삽입(원형 구조 활용)-----------------
D 추가: [ _, _, C, D, _ ]  (Front=2, Rear=3)
E 추가: [ _, _, C, D, E ]  (Front=2, Rear=4)
F 추가 (원형으로 돌아감): [ F, _, C, D, E ]  (Front=2, Rear=0)
-------------------------------------------------------------

Queue 의 동작을 체감할 수 있는 문제

은행 창구 시스템을 Queue로 구현

• 은행에 고객이 도착하면 순서대로 줄을 서고(FIFO, 선입선출)
• 한 명씩 창구에서 처리가 완료되면 다음 고객이 호출
• 모든 고객이 처리될 때까지 Queue를 유지

작성 코드

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        //큐 생성(LinkedList 사용)
        Queue<String> queue = new LinkedList<>();


        for(int i = 1; i < 6; i++) {
            queue.offer("대기 번호 "+ i + "번 고객");
            System.out.println("현재 대기 중인 고객: " + queue);
            try {
                Thread.sleep(1000); //1초 동안 처리
            } catch (InterruptedException e){
                e.printStackTrace();
            }
        }
        System.out.println("총 대기 중인 고객: " + queue);

        //은행 창구에서 고객을 한 명씩 처리
        while(!queue.isEmpty()){
            String currentCustomer = queue.poll(); //맨 앞 고객 처리
            System.out.println("알림: " + currentCustomer + "님 창구에서 처리 중...");

            try {
                Thread.sleep(1000); //1초 동안 처리
            } catch (InterruptedException e){
                e.printStackTrace();
            }
            System.out.println("알림: " + currentCustomer + "님 처리 완료! 남은 고객: " + queue);
        }
        System.out.println("모든 고객이 처리되었습니다.");
    }
}

출력

현재 대기 중인 고객: [대기 번호 1번 고객]
현재 대기 중인 고객: [대기 번호 1번 고객, 대기 번호 2번 고객]
현재 대기 중인 고객: [대기 번호 1번 고객, 대기 번호 2번 고객, 대기 번호 3번 고객]
현재 대기 중인 고객: [대기 번호 1번 고객, 대기 번호 2번 고객, 대기 번호 3번 고객, 대기 번호 4번 고객]
현재 대기 중인 고객: [대기 번호 1번 고객, 대기 번호 2번 고객, 대기 번호 3번 고객, 대기 번호 4번 고객, 대기 번호 5번 고객]
총 대기 중인 고객: [대기 번호 1번 고객, 대기 번호 2번 고객, 대기 번호 3번 고객, 대기 번호 4번 고객, 대기 번호 5번 고객]
알림: 대기 번호 1번 고객님 창구에서 처리 중...
알림: 대기 번호 1번 고객님 처리 완료! 남은 고객: [대기 번호 2번 고객, 대기 번호 3번 고객, 대기 번호 4번 고객, 대기 번호 5번 고객]
알림: 대기 번호 2번 고객님 창구에서 처리 중...
알림: 대기 번호 2번 고객님 처리 완료! 남은 고객: [대기 번호 3번 고객, 대기 번호 4번 고객, 대기 번호 5번 고객]
알림: 대기 번호 3번 고객님 창구에서 처리 중...
알림: 대기 번호 3번 고객님 처리 완료! 남은 고객: [대기 번호 4번 고객, 대기 번호 5번 고객]
알림: 대기 번호 4번 고객님 창구에서 처리 중...
알림: 대기 번호 4번 고객님 처리 완료! 남은 고객: [대기 번호 5번 고객]
알림: 대기 번호 5번 고객님 창구에서 처리 중...
알림: 대기 번호 5번 고객님 처리 완료! 남은 고객: []
모든 고객이 처리되었습니다.

코드 해석

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

• Queue 인터페이스를 LinkdeList 구현
• FIFO 방식
  
  

for(int i = 1; i < 6; i++) {
            queue.offer("대기 번호 "+ i + "번 고객");
            System.out.println("현재 대기 중인 고객: " + queue);
            try {
                Thread.sleep(1000); //1초 동안 처리
            } catch (InterruptedException e){
                e.printStackTrace();
            }
        }

• offer()메서드를 사용해여 큐의 끝에 데이터 추가

String currentCustomer = queue.poll();

• poll()메서드를 사용하면 맨 앞 고객을 꺼내고, 문자열에서 제거
• 큐가 비어 있을 때poll()을 호출하면 null 반환

while (!queue.isEmpty()) {
    String currentCustomer = queue.poll(); 
}

• 큐가 빌때까지 한명 씩 처리
• isEmpty 문자열 길이가 0일때 ture를 리턴
  - !queue.isEmpty() 문자열이 있다면 !false -> true 출력