1. 개념

• Queue 인터페이스는 일반적으로 FIFO(First In First Out) 순서를 따르는 큐 자료구조를 구현하는 데 사용된다. 그리고 큐는 많은 운영 체제, 컴퓨팅 시스템, 애플리케이션에서 중요한 데이터 구조이며, 대기열과 유사한 개념으로 대기열에 먼저 도착한 요소가 먼저 나가는 것을 보장한다.

• Java에서 Queue 인터페이스는 여러 가지 구현체를 제공한다.

  • LinkedList: 큐의 노드를 링크로 연결하는 방식으로 구현되어 있으며, 데이터의 추가나 삭제가 빈번하게 일어나는 경우에 사용하기 적합하다. 또한 큐의 크기 제한이 없는 동적인 큐를 만들 수 있다. 큐의 가장 일반적인 연산인 삽입과 삭제는 LinkedList에서 상수 시간에 수행된다. 그러나 요소를 검색하는 데는 선형 시간이 필요합니다.
  • PriorityQueue는 우선순위 큐를 구현하기 위한 클래스로, 데이터를 우선순위에 따라 저장하고 삭제한다. 우선순위는 데이터의 크기를 비교하는 Comparable 인터페이스를 구현하거나 Comparator 인터페이스를 구현하여 사용자 정의할 수 있다.
  • ArrayDeque: 동적 배열로 구현된 더블 엔드 큐이다. 큐의 삽입과 삭제는 상수 시간에 수행된다. 그러나 요소를 검색하는 데는 선형 시간이 필요하다.

2. 메소드

• *add(element): 큐의 맨 끝에 요소를 추가한다. 만약 큐에 공간이 부족하면 IllegalStateException이 발생한다.
• offer(element): 큐의 맨 끝에 요소를 추가한다. 만약 큐에 공간이 부족하면 false를 반환한다.
• remove(): 큐의 맨 앞에서 요소를 삭제하고 해당 요소를 반환한다. 만약 큐가 비어있으면 NoSuchElementException이 발생한다.
• *poll(): 큐의 맨 앞에서 요소를 삭제하고 해당 요소를 반환한다. 만약 큐가 비어있으면 null을 반환한다.
• element(): 큐의 맨 앞에 있는 요소를 반환한다. 만약 큐가 비어있으면 NoSuchElementException이 발생한다.
• peek(): 큐의 맨 앞에 있는 요소를 반환한다. 만약 큐가 비어있으면 null을 반환한다.

3. 시간 복잡도

• add() : O(1)
• offer() : O(1)
• remove() : O(1)
• poll() : O(1)
• element() : O(1)
• peek() : O(1)