큐(Queue) : 데이터를 처리하기 전에 잠시 저장하고 있는 자료구조
FIFO(first-in-first-out) 형식
끝에 추가 됨
인터페이스
deque : 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있음
인터페이스 >ArrayDeque와 LinkedList 클래스들로 구현됨
Queue 메서드
add() : 큐 용량을 넘어서지 않는 선에서 원소를 추가
넘어가면 IllegalStateException이 발생
offer() : 큐 용량을 넘어서지 않는 선에서 원소를 추가
원소 추가에 실패하면 false가 반환
remove(), poll() : 큐의 처음에 있는 원소를 제거하거나 가져옴
어떤 원소가 제거되느냐는 큐의 정렬 정책에 따라 달라짐
큐에 원소가 없으면 remove() > NoSuchElementException 발생
poll() : null 반환
element(), peek() : 큐의 처음에 있는 원소를 삭제하지 않고 가져옴
큐에 원소가 없으면 element() > NoSuchElementException 발생
peek() : null 반환
package ex13; import java.util.LinkedList; import java.util.Queue; public class QueueTest { public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); for (int i = 0; i < 5; i++) { q.add(i); } System.out.println("큐의 요소: " + q); int e = q.remove(); System.out.println("삭제된 요소: " + e); System.out.println(q); } }
우선 순위 큐(priority queues) : 우선순위에 따라 저장
기본적인 우선순위 - 원소들의 값
무작위로 삽입되었더라고 정렬된 상태로 원소들을 추출함
항상 정렬된 상태로 원소들을 저장하고 있는 것은 아님
heap라는 자료구조를 내부적으로 사용함
가장 높은 우순 순위의 작업이 큐에서 먼저 추출되어서 시작됨
대표적인 예시) 작업 스케줄링(job scheduling)
** heap : 이진트리의 일종
add()와 remove()를 호출 > 가장 작은 원소가 효율적으로 트리의 루트로 이동
package ex13; import java.util.PriorityQueue; public class PriorityQueueTest { public static void main(String[] args) { PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(30); pq.add(80); pq.add(20); System.out.println(pq); System.out.println("삭제된 원소: " + pq.remove()); } }
Share article