[JAVA] Queue와 Deque 무엇이 좋을까?

자바에서 Queue 인터페이스는 기본적인 단방향 큐(FIFO)를 정의하는데 사용됩니다. 하지만, 실제로 Queue 대신 Deque를 사용하여 동일한 동작을 구현해도 성능에 문제가 없습니다. Deque는 큐와 스택 동작을 모두 지원하므로, Queue의 모든 기능을 충분히 대체할 수 있습니다.

---

1. 🌐 Queue와 Deque의 차이

1.1 Queue의 특징

• 단방향 삽입/삭제만 가능하며, FIFO(First In, First Out) 동작을 따릅니다.
• 주요 메서드:
  • 삽입: add(E e), offer(E e)
  • 삭제: poll(), remove()
  • 조회: peek(), element()

1.2 Deque의 특징

• 양방향 삽입/삭제가 가능하지만, 단방향 동작도 구현 가능합니다.
• Deque를 단방향 큐로 사용하면, Queue의 모든 기능을 대체할 수 있습니다.
• 주요 메서드:
  • 삽입: addLast(E e) (뒤쪽 삽입, Queue의 offer와 동일)
  • 삭제: pollFirst() (앞쪽 삭제, Queue의 poll과 동일)
  • 조회: peekFirst() (앞쪽 조회, Queue의 peek과 동일)

---

2. 🎯 Deque를 사용하여 Queue 동작 구현

코드 예제

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeAsQueueExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // 큐의 삽입 동작
        deque.addLast(10); // Queue의 offer()와 동일
        deque.addLast(20);
        deque.addLast(30);

        // 큐의 삭제 동작
        System.out.println(deque.pollFirst()); // 출력: 10 (Queue의 poll()과 동일)
        System.out.println(deque.peekFirst()); // 출력: 20 (Queue의 peek()과 동일)

        // 남은 요소 출력
        System.out.println(deque); // 출력: [20, 30]
    }
}

---

3. 📋 Deque로 구현할 때 성능 분석

Deque를 Queue처럼 사용할 때의 성능은 Queue 구현체와 동일하거나 더 효율적입니다. 특히, ArrayDeque와 LinkedList를 사용할 경우의 성능을 비교해 보면 다음과 같은 특징이 있습니다.

3.1 ArrayDeque의 성능

• 삽입/삭제:
  • O(1): 양 끝에서의 삽입/삭제가 빠릅니다.
  • ArrayDeque는 내부적으로 배열을 사용하므로 캐시 친화적이고 메모리 접근 속도가 빠릅니다.
• 동적 크기 조정:
  • 큐의 크기가 가득 차면 내부 배열을 2배로 늘리는 동작이 발생하지만, 이는 삽입/삭제의 평균 성능에 큰 영향을 미치지 않습니다.

3.2 LinkedList의 성능

• 삽입/삭제:
  • O(1): 양 끝에서 삽입/삭제가 빠릅니다.
• 메모리 오버헤드:
  • 각 노드에 추가적인 포인터 메모리를 사용하므로, 배열 기반의 ArrayDeque보다 메모리를 더 사용합니다.

---

4. 🔍 왜 Deque를 사용하는 것이 괜찮은가?

4.1 Queue 대신 Deque를 사용하는 이유

1. 더 많은 기능 지원:
   • Deque는 양방향 삽입/삭제 기능을 지원하므로, 더 유연하게 동작할 수 있습니다.
   • 하지만 단방향 동작만 구현해도 충분히 Queue를 대체할 수 있습니다.
2. 성능 손실 없음:
   • ArrayDeque나 LinkedList를 사용하여 Deque를 구현하면, Queue의 주요 구현체(LinkedList와 ArrayDeque)와 동일한 성능을 제공합니다.
3. 캐시 친화적:
   • ArrayDeque는 배열 기반이기 때문에 메모리 접근 속도가 빠르고, 대부분의 상황에서 LinkedList보다 효율적입니다.

---

5. ⚡ Deque와 Queue 구현체 비교

구현체	동작 방식	삽입/삭제 성능	중간 접근 성능	메모리 사용	특징
Queue + LinkedList	연결 리스트	O(1)	O(n)	높음	동적 크기, 삽입/삭제 효율적
Queue + ArrayDeque	배열	O(1)	O(n)	낮음	빠른 삽입/삭제, 캐시 친화적
Deque + ArrayDeque	배열	O(1)	O(n)	낮음	큐와 스택 모두 가능, 양방향 삽입/삭제 지원
Deque + LinkedList	연결 리스트	O(1)	O(n)	높음	큐와 스택 모두 가능, 유연한 크기 확장 가능

---

6. 💡 요약

1. Deque로 Queue 구현하기:
   • Deque를 사용하면 단방향 큐(Queue)의 동작을 그대로 구현할 수 있습니다.
   • 예: addLast → offer, pollFirst → poll, peekFirst → peek.
2. 성능 문제 없음:
   • Deque를 사용하여 큐를 구현할 경우 성능은 동일하거나 더 효율적입니다.
   • 특히 ArrayDeque는 캐시 친화적이고 빠른 삽입/삭제를 제공하므로, 대부분의 경우 추천됩니다.
3. 선택 가이드:
   • 단순한 큐 작업만 필요하다면 ArrayDeque를 사용하세요.
   • 양방향 삽입/삭제가 필요하거나 더 유연한 사용이 필요하면 Deque 인터페이스로 구현하세요.
   • 정렬이 필요하다면 Queue 인터페이스를 이용한 PriorityQueue 구현체를 사용해야합니다.

💡 결론적으로, Deque는 Queue를 대체할 수 있는 충분히 강력하고 성능이 좋습니다.