🔷 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
선입선출(FIFO:First-In-First-Out)
: 먼저 삽입된 원소는 가장 먼저 삭제된다.🔷 큐의 기본 연산
삽입: enQueue
(저장된 원소 중 마지막 원소를 가리키는 꼬리[Rear]로 삽입됨)
삭제: deQueue
(저장된 원소 중 마지막으로 삭제된 원소를 가리키는 머리[front,head]에서 삭제됨)
생성: createQueue
(공백상태의 큐 생성)
공백확인: isEmpty
(큐가 공백 상태인지를 확인하는 연산)
포화확인: isFull
(큐가 포화 상태인지를 확인하는 연산)
앞쪽 확인: Qpeek
(큐의 앞쪽에서 원소를 삭제 없이 반환하는 연산)
🔷 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
인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됨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()));
}
}
}
}