큐(Queue) 란?
•
FIFO(선입선출)구조의 자료구조
•
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림
•
JAVA에서 구현
1.
LinkedList
•
LinkedList는 List 인터페이스와 Queue 인터페이스를 동시에 상속받고 있기 때문에,
스택 / 큐 로서도 응용이 가능하다.
•
실제로 LinkedList 클래스에 큐 동작과 관련된 메서드를 지원함
(push, pop, poll, peek, offer ..등)
2.
ArrayDeque
•
Deque(Double-Ended Queue)는 양쪽으로 넣고 빼는 것이 가능한 큐
•
스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있음
•
스택으로 사용할 때 Stack 클래스보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠름
•
사이즈에 제한이 없음
•
null 저장 불가능
3.
PriorityQueue
•
우선 순위를 가지는 큐 (우선 순위 큐)
•
일반적인 큐와는 조금 다르게, 원소에 우선 순위(priority)를 부여하여
우선 순위가 높은 순으로 정렬되고 꺼냄
•
수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행할때 쓰임
(네트워크 제어, 작업 스케쥴링)
•
우선순위 큐에 저장할 객체는 필수적으로Comparable인터페이스를 구현해야함
•
compareTo() 메서드 로직에 따라 자료 객체의 우선순위를 결정하는 식으로 동작되기 때문
•
저장공간으로 배열을 사용, 각 요소를 힙(heap) 형태로 저장
•
null 저장 불가능
