[Java] 알고리즘_Queue

✅ 큐 (Queue)

👉 먼저 집어 넣은 데이터가 먼저 나오는 선입선출(First in First out) 구조로 저장하는 형식

📢 특징

• 자료가 일렬로 놓인 선형 자료구조
• 제일 먼저 추가된 자료가 먼저 나오는 선입선출 자료구조

🌐 Queue의 기본 기능

• Queue에 데이터를 추가 → enQueue
• Queue에서 데이터를 회수 → deQueue
• Queue가 비었는지 확인 → isEmpty
• Queue의 제일 앞에 데이터를 확인 → peek()
• Queue가 가득 차있는지 확인 (고정된 배열을 사용하는 경우)

🌐 선형 Queue

🚧 예제 코드

public class Main {
	private final int[] arr = new int[16];
    // Queue에서 데이터 꺼내는 위치
    private int front = -1;
    
    // Queue에 데이터를 추가하는 위치
    private int rear = -1;
    
    public Main() {}
    
    // 데이터 추가
    public void enQueue(int x) {
    	// rear + 1 이 배열의 크기만해질때
        if(rear == arr.length -1) {
        	throw new RuntimeException("Queue is full");
        }
        // rear를 하나 증가시킴
        rear++;
        // arr[rear] = x;
    }
    
    // 데이터 회수
    public int deQueue() {
    	// front == rear 일때 Queue가 비어있음
        if(front == rear) {
        	throw new RuntimeException("Queue is empty");
        }
        // front를 하나 증가시킴
        front++;
        // arr[front]의 값을 반환
        return arr[front];
    }
    
    // 다음에 나올 데이터가 무엇인지 확인 (Queue에서 빼내지 않음)
    public int peek() {
    	if(isEmpty()) {
        	throw new RuntimeException("Queue is empty");
        }
        // 비어있지 않다면 front + 1의 값 반환
        return arr[front + 1];
    }
    
    public static void main(String[] args) {
    	Main intQueue = new Main();
        intQueue.enQueue(1);
        intQueue.enQueue(1);
        System.out.println(intQueue.deQueue());
        System.out.println(intQueue.deQueue());
    }
}

❗ 선형 Queue의 문제점

• Stack의 top과 달리 배열을 활용한 Queue의 rear는 앞으로 이동하지 못하고, 계속해서 뒤로만 이동
• 배열 기반의 선형 Queue는 물리적 구조상 배열의 끝에 도달하게 되면 더이상 enQueue 작업 불가능
• deQueue가 발생하면 배열의 앞쪽에는 빈 공간이 확보되지만, Queue가 가득 차있다고 인식
• 데이터를 앞쪽으로 이동하여 공간을 활용할 수 있지만, 비효율적임

🌐 원형 Queue

👉 선형 Queue의 대안으로 front와 rear가 배열의 끝에 도달할 경우 다시 제일 앞쪽으로 이동하도록 구현

⚠️ 포화 상태와 공백 상태 비교를 위해 front 위치를 비워두어야 하므로 실제 크기보다 배열의 크기 + 1

⚠️ 인덱스 판단 기준도 + 1

🚧 예제 코드

public class MyCyQueue {
	private final int size = 4;
    private final int offset = size + 1;
    private final int[] arr = new int[offset];
    private int front = 0;
    private int rear = 0;
    
    public myCyQueue() {}
    
    // 데이터 추가
    public void enQueue(int x) {
    	// 다음에 데이터가 들어가는 곳: (rear + 1) % (size + 1)
        // 다음에 데이터가 나올 곳과 일치 할 경우 Full (예외)
        if ((rear + 1) % offset == front) {
        	throw new RuntimeException("Queue is full");
        }
        rear = (rear + 1) % offset;
        arr[rear] = x;
    }
    
    // 데이터 회수
    public int deQueue() {
    	if (front == rear) {
        	throw new RuntimeException("Queue is empty");
        }
        front = (front + 1) % offset;
        return arr[front];
    }
    
    public boolean isEmpty() {
    	return front == rear;
    }
    
    public static void main(Stirng[] args) {
    	MyCyQueue queue = new MyCyQueue();
        queue.enQueue(1);
        queue.enQueue(2);
        queue.enQueue(3);
        queue.enQueue(4);
        queue.enQueue(5); // 예외 발생(queue is full)
        System.out.println(queue.deQueue());
        queue.enQueue(5);
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        queue.enQueue(6);
        queue.enQueue(7);
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
        System.out.println(queue.deQueue());
    }
}

✅ interface Queue <T>

👉 Java Collection Framework에서 제공하는 interface Queue를 활용할 때, 주로 LinkedList를 구현체로 사용

🌐 Queue의 기능

• enQueue - Queue가 가득 차있다면
  • add() → 예외 발생
  • offer() → false 반환
• deQueue - Queue가 비어있다면
  • remove() → 예외 발생
  • poll() → null 반환
• peek - Queue가 비어있다면
  • element() → 예외 발생
  • peek() → null 반환

🚧 구현

public class JavaQueue {
	public static void main(String[] args) {
    	Queue<Integer> queue = new LinkedList<>();
        
        // ensQueue
        // offer, add - enQueue에 해당하는 메소드
        queue.offer(1);
        queue.add(2);
        
        // deQueue
        // remove, poll - deQueue에 해당하는 메소드
        System.out.println(queue.remove());
        System.out.println(queue.poll());
        
        // peek
        // peek, element - peek에 해당하는 메소드
        System.out.println(queue.peek());
        System.out.println(queue.element());
    }
}