[CS공부] ArrayDeuqe vs Queue

1. Queue

• 인터페이스 기반
• 인터페이스 교체 자유
• 원형 배열 선형 배열 구조 정리 안되어 있음 -> 인터페이스이기 때문에
• ArrayDeuqe 나 LinkedList 나 PriorityQueue 등 사용 가능
• new Queue<>(); 는 불가 클래스의 인스턴스를 생성할 때 사용 -> new 이다 인터페이스는 인스턴스를 가질 수 없다.

  Queue는 구현이 없지만 객체를 생성해주세요 와 같은 말이다.

2. ArrayDeque

• 배열 기반이라 인덱스 접근이 빠르다
  • LickedList 보다 빠름 -> 포인터로 연결된 노드 구조 -> 메모리 사용량이 많고 접근 속도가 느림
  • 내부적으로 원형 배열 사용 -> 빠른 add, remove 등 있음
• Stack 이나 Queue 두 역할 모두 유연하게 가능
  • LickedList보다 큐 용도가 더 좋음
• null 허용 안해서 버그 방지
  • LickedList는 가능해서 실수 가능
• 스레드가 안전하지 않지만 그만큼 빠름
  • 동기화가 없다
  • 단일 스레드 환경에서는 불필요한 비용이 없어 빠름
  • 필요 시 외부에서 동기화하거나 ConcurrentLinkedQueue 등을 사용

Queue q = new ArrayDeque<>() 와 ArrayDeque q = new ArrayDeque<>() 의 차이

3-1. Queue q = new ArrayDeque<>();

• 인터페이스 타입으로 선언
• Queue 인터페이스에서 제공하는 메소드만 사용 가능
• 내부 구현을 바꿔도 코드를 많이 변경하지 않아도 됨
  • LinkedList, PriorityQueue 등으로 교체가능
• 캡슐화 강화 및 유연한 코딩이 가능

사용하면 좋을 때

• FIFO 큐 기능만 필요할 때
• 향후 다른 구현체로 교체 가능성이 있을 경우
• 인터페이스 기반 설계를 따르고 싶을 때

3-2. ArrayDeque q = new ArrayDeque<>()

• 구현체 타입으로 선언
• Deque와 ArrayDeque 고유의 모든 메소드를 사용가능
  • 스택/양방향 기능 사용 가능
• addFirst() ,pollLast() 등 편의 메소드 직접 사용 가능

사용하면 좋을 때

• Deque 고유 기능을 모두 활용하려 할 때 (addFirst(), removeLast() 등)
• 큐를 스택처럼 양방향 큐로도 강화하고 싶을 때
  • 스택처럼 사용하고 싶을 때
  • 트리 탐색, 그래프 탐색(BFS + 역방향)
  • 슬라이딩 윈도우 알고리즘
    • 특정 구간에서 최대/최소값 유지
    • LRU Cache