Queue
Collection 인터페이스를 상속받은 인터페이스이다.
일반적으로 선입 선출의 특성을 갖지만 구현에 따라서 요소에 따라 정렬된 순서를 갖거나, 양방향에서 자료를 입/출력하기도 한다.
- 제공 함수
삽입 : add(e) offer(e)
삭제 : remove() poll()
탐색 : element() peek()
add, remove, element는 요소가 없는 경우에 예외를 반환하고 offer, poll, peek은 null을 반환한다.
입력과 출력은 O(1)의 시간 복잡도를 가진다.
BlockingQueue
thread-safe한 큐이다. 큐가 꽉차거나 비어있을때 사용할 수 있을 때 까지 대기하는 put과 take 메소드를 가지고 있다.
- ArrayBlockingQueue
배열을 기반으로 한 정적인 크기를 가지는 큐이다. - LinkedBlockingQueue
크기를 지정할 수 있는 노드 기반의 큐이다. - SynchronousQueue
내부에 버퍼가 없는 큐이다. 입력한 경우 다른 스레드가 출력할 때 까지 대기한다. 반대의 경우도 마찬가지이다. 일종의 교환 역할만을 수행한다.
PriorityQueue
입력 순서가 아닌 요소의 비교 우위 순서에 따라 출력되는 순서가 바뀐다. 요소간의 비교를 할 수 없는 경우 예외를 발생시킨다.
내부는 배열 기반의 힙으로 구성되어있다.
입력은 O(logn)의 시간복잡도를 가지고 출력은 O(1)의 시간 복잡도를 가진다.
동기화를 제공하는 클래스는 PriorityBlockingQueue이다.
Deque
'double ended queue'의 줄임말로 양 끝단에서 입/출력이 가능한 인터페이스이다.
출처 : https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html
큐와 마찬가지로 자료가 없거나 꽉 찬 경우 예외를 던지는 메소드와 null을 던지는 메소드로 나뉜다.
- ArrayDeque
배열 기반의 데크이며 크기를 확장한다. 동기화 되어있지 않다. - ConcurrentLinkedDeque
노드 기반의 데크이며 동기화를 제공한다. - LinkedBlockingDeque
노드 기반의 데크이며 동기화를 제공하고 크기를 제한할 수 있다.
참조
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html
