기본기를 다지자/자료구조

[java] Queue (ArrayDeque)

아. 이렇게 하면 될거 같은데.. 2025. 2. 16. 23:43
728x90

📌 Queue 란?

큐는 선입선출 (FIFO) 방식으로 데이터를 처리하는 자료 구조 이다.

 

 

 

Front에서는 데이터를 제거하기만 하고 Rear에서는 데이터를 추가하기만한다.

이번에도 역시 Java Doc에서 Queue에 대한 설명을 확인해보자.

 

Queue는 처리 전 요소를 저장하는 컬렉션입니다. FIFO(선입선출) 방식으로 작동하는 것이 일반적이지만, 우선순위 큐나 LIFO(후입선출) 방식의 큐도 존재합니다.
Queue는 삽입( add , offer ), 제거( remove , poll ), 검사( element , peek ) 연산을 제공합니다. 각 연산은 예외를 던지거나 특수 값을 반환하는 두 가지 형태로 존재합니다. 고정 용량의 큐에서는 offer가 일반적으로 사용됩니다.
BlockingQueue는 대기 기능을 제공하는 큐입니다. null요소 삽입은 대부분의 큐에서 허용되지 않으며, 큐는 요소 기반의 equals 와hashCode를 정의하지 않습니다.

 

 

Queue는 보통 LinkedList와 ArrayDeque로 사용한다.

LinkedList는 이전 포스트를 참고하면 된다.

그러므로 요번 포스트에서는 Queue를 구현한 ArrayDeque에 대해 공부해보자

 

ArrayDeque java Doc

ArrayDeque<E>는 Deque인터페이스를 가변 크기 배열로 구현한 클래스입니다. 용량 제한이 없으며, 스택으로 사용할 때 Stack보다, 큐로 사용할 때 LinkedList 보다 빠를 수 있습니다. 이 클래스는 스레드 안전하지 않으며, null요소를 허용하지 않습니다. 대부분의 연은 상수 시간에 수행되며, 반복자는 fail-fast 동작을 통해 동시 수정 시 ConcurrentModificationException을 던질 수 있습니다. Fail-fast는 동시 수정 버그를 감지하는 용도로만 사용되어야 합니다.

 

생성자.. 생성자를 보자

ArrayDeque의 생성자는 3가지가 있다.

 

  1. ArrayDeque()
  2. ArrayDeque(Collection<? extends E> c)
  3. ArrayDeque(int numElements)

1번은 기본 생성자로 기본적으로 크기가 16으로 설정된다.

2번은 주어진 컬렉션 c의 모든 요소를 포함하는 ArrayDeque를 생성한다. 컬렉션의 요소들은 해당 컬렉션의 순서대로 ArrayDeque에 삽입된다.

3번은 주어진 numElements용량을 가진 빈 ArrayDeque를 생성한다. 즉 초기 크기를 설정 할 수 있는 생성자이다.

 

생성자는 ArryaList와 비슷한 느낌이다. -> ArrayDeque는 내부적으로 동적배열을 사용하기 때문에 같은 동적 배열을 사용하는 ArrayList와 비슷하다.

 

// 1
ArrayDeque<Integer> deque = new ArrayDeque<>();

// 2
List<String> list = Arrays.asList("a", "b", "c");
ArrayDeque<String> deque = new ArrayDeque<>(list);

// 3
ArrayDeque<String> deque = new ArrayDeque<>(32);

 

📌 ArrayDeque 메서드

이러한 ArrayDeque의 메서드를 확인해보자

기능 메서드 설명
삽입 add(E e) ArrayDeque의 뒤쪽(tail) 끝에 요소를 추가한다. 추가할 수 없는 경우 IllegalStateException을 던진다
offer(E e) tail에 요소를 추가한다. 추가할 수 없는 경우
false를 반환한다.
addFirst(E e), offerFirst(E e) ArrayDeque에 head에 요소를 삽입한다.
addLast(E e), offerLast(E e) ArrayDeque에 tail에 요소를 삽입한다.
삭제 remove() 앞쪽(head)에서 요소를 제거하고 반환한다. 큐가 비어있을 경우 NoSuchElementException을 던진다
poll() 앞쪽(head)에서 요소를 제거하고 반환한다. 큐가 비어있을 경우 null을 반환한다.
removeFirst(), pollFirst() ArrayDeque에 head의 요소를 제거하고 반환한다.
removeLast(), pollLast() ArrayDeque에 tail의 요소를 제거하고 반환한다.
조회 peek() head의 요소를 제거하지 않고 반환한다. 큐가 비었을 경우 null을 반환
element() head의 요소를 제거하지 않고 반환한다. 큐가 비었을 경우 NoSuchElementException을 던진다.
peekFirst(), getFirst() ArrayDeque에 head의 요소를 제거하지 않고 반환한다.
peekLast(), getLast() ArrayDequedp tail의 요소를 제거하지 않고 반환한다.
기타 clear() 덱의 모든 요소를 제거한다
size() 덱에 들어있는 요소의 개수를 반환한다.

 

역시 LinkedList와 비슷하게 exception을 던지는 메서드와 아닌 메서드들이 나뉘어져 있다.

 

🤔 왜 빠르다고 할까?

자바 공식 문서에도 보면 LinkedList보다 Queue에서 보통 빠르다고 하는데 왜 빠를까? 궁금하다.

 

GPT에게 물어보니 ArrayDeque는 연속적인 배열을 사용하여 독립적인 객체를 사용하는 LinkedList보다 빠르다고 한다. 그리고 LinkedList는 추가적인 포인터를 가지고 있어 메모리사용량이 ArrayDeque보다 더 크다고 한다.

 

직접 확인해보자

 

메서드 ArrayDeque LinkedList
offer 1,956,573,166 11,618,255,250
poll 395,724,459 2,184,586,042

 

음.. 확실히 LinkedList보다 ArrayDeque가 압도적이었다.

 

솔직히 이렇게 차이날줄은 몰랐다.

offer연산을 보면 LinkedList는 노드를 만들어 포인터만 연결해주면 되서 ArrayDeque보다 빠를 줄 알았다. 찾아보니 포인터를 설정하고 연결하는 과정에서 ArrayDeque보다 추가적인 연산이 들어가서 LinkedList가 더 느리다고 한다.

나는 동적배열의 리사이징 때문에 최소 비슷하거나 LinkedList가 더 빠를 줄 알았다.

 

그럼 Queue를 구현하는 구현체는 ArrayDeque가 맞냐? 대부분은 그럴 것이다.

큐는 앞에서 삭제하고, 뒤에서 추가한다. 이는 ArrayDeque, LinkedList 모두 O(1)의 시간복잡도를 가진다.

 

만약 중간에 삽입을 해야 하는 경우가 있다면 이미 벌써 큐가 아니지만

동적배열 형식보다 LinkedList가 더 빠를 것이다.

 

간단하게 실험해봤다. 다시 말하지만 이건 큐가 아니다.

ArrayList와 LinkedList를 중간에서 삽입 하였을때 시간을 측정해보았다.

 

  ArrayList LinkedList
시간 14,835,657,125 197,694,500

 

확실이 중간에 삽입한다고 가정하였을때는 LinkedList가 훨씬 빠르다.

🤔 느낀점

오늘은 Queue의 ArrayDeque에 대해 알아보았는데 신기했다. 자바의 공식문서에도 적혀있듯이 LinkedList와 비교했을때 성능이 많이 차이가 났기 때문이다. 이제는 Queue의 구현체는 ArrayDeque만 쓸 것 같다.

728x90
반응형