큐(Queue)

• 선입 선출 구조 (FIFO, First In First Out)
• 한 쪽 끝은 Front로 정하여 삭제 연산만 수행
• 다른 한쪽을 rear로 정하여 삽입 연산만 수행
• 그래프의 너비우선 탐색(BFS)에서 사용
• 큐는 자바에서 인터페이스밖에 존재하지 않아서
  import java.util.LinkedList;
  import java.util.Queue; 후
  Queue queue = new LinkedList<>();를
  이용해 사용
  
• Enqueue : 큐 맨 뒤에 데이터 추가
• Dequeue : 큐 맨 앞쪽의 데이터 삭제

큐 기본 연산

• 데이터 추가(offer)
  queue.offer(3)로 마지막 데이터 위치에 추가
  

• 데이터 삭제(poll)
  queue.poll()로 가장 먼저 들어간 데이터 삭제
  

• 처음 저장값 출력(peek)
  queue.peek()로 남은 데이터중 처음 저장값 출력
  

• 큐가 비어있는지(isEmpty)
  queue.isEmpty()로 큐가 비어있는지 출력
  

• 큐에 특정데이터가 있는지(contains)
  queue.contains(3)로 3이 있는지 true나 false
  

• 큐의 사이즈(size)
  queue.size()로 큐에 들어있는 데이터 개수 출력
  

• 큐 비우기(clear)
  queue.claer()로 큐 비우기
  

queue의 시간복잡도

삽입 : O(1)
삭제 : O(1)
검색 : O(n)

삽입과 삭제는 데이터 개수 상관없이 가능해서 1
검색은 큐에 들어있는 데이터에따라 개수가 달라져서 n