---

⚡ Queue

---

📌큐(Queue)

🔷 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조

• 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
• 선입선출(FIFO:First-In-First-Out): 먼저 삽입된 원소는 가장 먼저 삭제된다.

🔷 큐의 기본 연산

• 삽입: enQueue (저장된 원소 중 마지막 원소를 가리키는 꼬리[Rear]로 삽입됨)

• 삭제: deQueue (저장된 원소 중 마지막으로 삭제된 원소를 가리키는 머리[front,head]에서 삭제됨)

• 생성: createQueue (공백상태의 큐 생성)

• 공백확인: isEmpty (큐가 공백 상태인지를 확인하는 연산)

• 포화확인: isFull (큐가 포화 상태인지를 확인하는 연산)

• 앞쪽 확인: Qpeek (큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산)

  ⭐ 선형큐

🔷 1차원 배열을 이용한 큐

• 큐의 크기 = 배열의 크기
• front: 마지막으로 삭제된 인덱스
• rear: 저장된 마지막 원소의 인덱스

🔷 상태 표현

• 초기 상태: front == rear && rear == -1
• 공백 상태: front == rear
• 포화 상태: rear == n-1(n: 배열의 크기. n-1: 배열의 마지막 인덱스)

public class dailyClass {
	// 배열을 선언함으로써 createQueue 연산
	public static String [] queue = new String[5];
	// front: 마지막으로 삭제된 원소의 위치 / rear: 마지막 원소의 위치
	public static int front = -1, rear = -1;
	
	// front와 rear가 동일하면 공백상태
	public static boolean isEmpty() {
		return front==rear;
	}
	
	// rear가 마지막 인덱스 위치에 가 있으면 포화상태(가 아닐 수도 있다!)
	public static boolean isFull() {
		return rear == queue.length-1;
	}
	
	// rear에 삽입
	public static void enQueue(String item) {
		if(isFull()) {
			System.out.println("꽉 차서 못 넣어용");
			return;
		}
		
		queue[++rear] = item;
	}
	
	// ++front에서 삭제
	public static String deQueue() {
		if(isEmpty()) {
			System.out.println("없어서 못 빼용");
			return null;
		}
		
		return queue[++front];
	}
}

🔷 단점

• 🌟 잘못된 포화 상태 인식
  • 선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear == n-1인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됨
  • 이를 위해 연산이 이루어질 때마다 원소들을 배열의 앞부분으로 이동시킬 수 있으나 이는 효율성이 급격히 떨어진다.
  • 대신 원형 큐를 사용할 수 있다.

⭐ API 활용

• Queue는 구현 클래스가 없기 때문에 LinkedList 구현 클래스로 활용한다.

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

public class dailyClass {
	public static void main(String[] args) {
		// Queue는 구현클래스가 없다. (인터페이스)
		// LinkedList 구현 클래스로 활용
		Queue<String> queue = new LinkedList<>();
		
		// 추가(add, offer)
		queue.add("박영규");
		queue.offer("뉴진스");
		
		// 삭제(remove, poll)
		System.out.println(queue.element());
		System.out.println(queue.peek());
		
		// 조회(element, peek)
		System.out.println(queue.remove());
		System.out.println(queue.poll());
		
		// add, remove, element 예외 발생
		// 나머지는 발생 X
	}
	
}

❗ add, remove, element는 가리키는 요소가 없을 때 예외가 발생하지만 나머진 null을 출력한다.

---

📌 큐 활용

🔷 버퍼

• 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역
• 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미한다.

🔷 버퍼의 자료 구조

• 버퍼는 일반적으로 입출력 및 네트워크와 관련된 기능에 사용된다.
• 순서대로 입력/출력/전달되어야 하므로 큐가 활용된다.

🔷 마이쮸 나누기 알고리즘 예제

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

// 마이쮸 나누기
// 한번 받은 사람은 새롭게 줄을 서고 기존의 받은 양보다 한 개 더 받을 수 있다.
// 사람이 줄을 서면 새로운 사람이 한명씩 와서 줄을 선다.
public class dailyClass {
	static class Person {
		int num; // 사람의 번호
		int cnt; // 현재 가지고 갈 수 있는 마이쮸 카운트
		String name;
		
		public Person(int num, int cnt, String name) {
			this.num = num;
			this.cnt = cnt;
			this.name = name;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = 20;
		int pNum = 1;
		
		// 큐 생성
		Queue<Person> queue = new LinkedList<>();
		queue.add(new Person(pNum++, 1, "박영규"));
		
		while(N > 0) {
			Person p = queue.poll(); // 현재 줄에서 꺼내기
			N -= p.cnt;
			if(N <= 0) {
				System.out.println(p.num + "번이 마지막 마이쮸를 가져갔다!");
			} else {
				System.out.println(p.num+"번 "+p.name+"이(가) "+p.cnt+"만큼 가져감");
				p.cnt++;
				System.out.println("남은 마이쮸: " + N + "개");
				queue.add(p);
				System.out.println("줄을 설 사람의 이름을 입력해주세요.");
				queue.add(new Person(pNum++, 1, sc.next()));
			}
		}
	}
	
}