Queue
여러분들이 많이 아는 바로 일반적인 Queue 이다.
FIFO 방식을 가지고 있으며, 선언 방식과 대표적인 메서드는 다음과 같다.
Queue<Integer> q = new LinkedList<>(); # LinkedList<>()로 선언
Queue<Integer> q = new ArrayDeque<>(); # ArrayDeque<>()로 선언
q.offer(1) # 1 삽입
q.offer(2) # 2 삽입
q.peek() # 1 조회
q.poll() # 1 제거PriorityQueue
우선순위 Queue 이다. 우선순위에 따라 자동 정렬되고, 기본은 오름차순이다. 선언 방식과 대표적인 메서드는 다음과 같다.
PriorityQueue<Integer> pq = new PriorityQueue<>(); # PriorityQueue<>()로 선언, 오름차순
pq.offer(3); # 3 삽입
pq.offer(1); # 1 삽입
pq.offer(2); # 2 삽입
pq.peek(); # 1 조회
pq.poll(); # 1 제거
PriorityQueue<Integer> pq = new PriorityQueue<> (Collections.reverseOrder()); # PriorityQueue<>()로 선언, 내림차순
pq.offer(3); # 3 삽입
pq.offer(1); # 1 삽입
pq.offer(2); # 2 삽입
pq.peek(); # 1 조회
pq.poll(); # 1 제거Deque
Deque는 양방향 큐다. 앞 뒤로 값을 삽입할 수 있다.
Deque<Integer> dq = new LinkedList<>();
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(1); // 앞에 1 삽입
dq.addLast(2); // 뒤에 2 삽입
dq.addFirst(1); // 앞에 3 삽입
dq.pollLast(); // 2제거, (뒤에서 제거)
dq.pollFirst(); // 3제거, (앞에서 제거)Queue 인터페이스를 구현하는 클래스 중 LinkedList<>()와 ArrayDeque<>() 의 차이점은
LinkedList는 이중연결리스트 자료구조를 사용한다. 그리고 노드 기반으로 포인터 2개를 사용한다. null 값을 허용하며 포인터 관리로 인해 메모리 사용이 많아 일반적으로 속도가 느리다.
ArrayDeque<>()는 동적배열 기반의 원형 큐 구조로 연속된 배열 공간을 사용한다. null 값은 허용하지 않으며 배열 기반이기 때문에 캐시 친화적인 구조로 큐/덱 연산에서 속도가 빠르다.
결론은 Queue를 선언할 때는 ArrayDeque<>() 를 사용하는게 속도와 메모리 측면에서 좋다.
