Java
Queue
dev-rootable
2024. 5. 10. 16:09
📌 Queue
Queue는 '대기열' 개념으로 선입선출(FIFO) 구조를 가진 자료구조다. 시간 순으로 어떤 작업 또는 데이터를 처리할 때
사용되며, 대표적으로 BFS(너비 우선 탐색)에 사용된다.
| Method | Description |
| boolean add(Object o) | 지정된 객체를 Queue에 추가 저장공간 부족 시 IllegalStateException 발생 |
| Object remove() | Queue에서 객체를 꺼내 반환 비어있을 경우 NoSuchElementException 발생 |
| Object element() | 삭제없이 요소를 읽어온다. 비어있을 경우 NoSuchElementException 발생 |
| boolean offer(Object o) | Queue의 마지막에 객체를 추가 |
| Object poll() | Queue의 첫 번째 요소를 제거하고 반환 |
| Object peek() | Queue의 첫 번째 요소를 제거없이 반환 비어있을 경우 null 반환 |
📌 Queue 종류
✅ PriorityQueue
각 요소들에 우선순위를 부여하여 우선순위가 높은 순으로 정렬하는 큐
🔍 특징
- 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 사용된다. (네트워크 제어, 작업 스케줄링)
- 저장할 객체는 필수적으로 Comparable 인터페이스를 구현해야 한다.
- 저장공간으로 배열을 사용하며, 각 요소를 Heap 형태로 저장한다.
- Null 저장 불가능
👨💻 예시 1 (Comparable 구현)
package priorityQueue;
import java.util.Comparator;
import java.util.Random;
public class PriorityQueueApplication {
public static void main(String[] args) {
PriorityQueue<Student> pq1 = new PriorityQueue<>();
PriorityQueue<Student> pq2 = new PriorityQueue<>(comp);
Random rnd = new Random();
char name = 'A';
for (int i = 0; i < 10; i++) {
int math = rnd.nextInt(10);
int science = rnd.nextInt(10);
pq1.offer(new Student(name, math, science));
pq2.offer(new Student(name, math, science));
name++;
}
System.out.println("[pq1 내부 배열 상태]");
for (Object val : pq1.toArray()) {
System.out.print(val);
}
System.out.println();
System.out.println();
System.out.println("[pq2 내부 배열 상태]");
Object[] q = new Object[15];
for (Object val : pq2.toArray(q)) {
System.out.print(val);
}
System.out.println();
System.out.println();
System.out.println("[수학-과학-이름순 뽑기]");
System.out.println("name\tmath\tscience");
while (!pq1.isEmpty()) {
System.out.print(pq1.poll());
}
System.out.println();
System.out.println("[과학-수학-이름순 뽑기]");
System.out.println("name\tmath\tscience");
while (!pq2.isEmpty()) {
System.out.print(pq2.poll());
}
}
static class Student implements Comparable<Student> {
char name;
int math;
int science;
public Student(char name, int math, int science) {
this.name = name;
this.math = math;
this.science = science;
}
/*
* 수학점수가 높은 순
* 수학점수가 같을 경우 과학 점수가 높은 순
* 둘 다 같은 경우 이름순
* */
@Override
public int compareTo(Student o) {
if (this.math == o.math) {
if (this.science == o.science) {
return this.name - o.name; //이름 오름차순
}
return o.science - this.science; //과학 내림차순(science -> math 교체하면 과학-수학-이름순)
}
return o.math - this.math; //수학 내림차순 (math -> science 교체하면 과학-수학-이름순)
}
@Override
public String toString() {
return name + "\t" + math + "\t" + science + "\n";
}
}
}
👨💻 예시 2 (Comparator 인자)
우선순위 큐를 생성할 때 Comparator 인자를 넣어주면 그 인자의 내부 로직대로 정렬이 수행되므로 별도로 구현 코드를
작성하지 않아도 된다. 하지만 객체를 사용하고 커스터마이징 정렬을 원한다면 Comparable을 구현하는 것이 적합하다.
package priorityQueue;
import java.util.*;
public class PriorityQueueApplication {
public static void main(String[] args) {
//랜덤값 오름차순
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
Random rnd = new Random();
for (int i = 1; i <= 10; i++) {
pq.offer(i, rnt.nextInt(10)); //<번호, 랜덤값>
}
}
}
✅ Deque(Double-ended queue)
양방향 연결리스트와 유사한 개념으로 양방향 삽입/삭제 가능
Deque의 조상은 Queue이며, 구현체로 ArrayDeque와 LinkedList 등이 있다. 또한, offer()와 pollLast()를 조합하면 Stack으로도 사용할 수 있다.
🔍 메서드
🔍 ArrayDeque
Deque 인터페이스를 구현한 클래스
- 스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다.
- 사이즈 조절이 가능
- Null 요소는 저장 불가능
🔍 LinkedList
List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있어 Deque/Stack/Queue 등을 구현할 수 있다.
🙋♂️ 큐 구현 (ArrayList vs LinkedList)
큐는 데이터를 꺼낼 때 항상 앞의 원소부터 삭제하므로 데이터를 이동 및 복사하는 작업이 동반된다. ArrayList는 배열
기반의 컬렉션 클래스이기 때문에 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 이동과 복사가 발생하므로 성능이 좋지
못하다. 따라서 큐는 데이터의 삽입/삭제가 용이한 LinkedList로 구현하는 것이 적합하다.
References:
https://st-lab.tistory.com/181
https://st-lab.tistory.com/219
https://st-lab.tistory.com/185