Queue

큐 란?

큐(Queue)란, 사람 혹은 줄을 서서 기다리는 것을 의미하는데, 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조이다.

큐의 특징

• 선입선출(First In First Out, FIFO) : 먼저 들어간 데이터가 먼저 나오는 구조
• 큐의 한 쪽 끝은 front로 정하여 삭제 연산만 수행
• 다른 한 쪽 끝은 rear로 정하여 삽입 연산만 수행
• 그래프의 넓이 우선 탐색(BFS)에 사용
• 프린터 출력 대기열 or 컴퓨터 버퍼에서 주로 사용

---

큐의 작동원리

---

Queue 사용법 (Java)

1. 자바에서 큐를 사용할땐,

• java.util.Queue
• java.util.LinkedList

이 두개를 import하여 사용할 수 있다.

2. 일반적인 동작은

• offer : 큐에 데이터를 추가하는 동작
• poll : 큐에서 제일 앞의 데이터를 빼오는 동작

---

Coding (Java)

import문

import java.util.Queue;
import java.util.LinkedList;

Queue 선언

Queue<자료형> 변수명 = new LinkedList<>();

  - 위 같은 경우는 자료형에 넣은 자료형만 삽입, 삭제 가능

Queue 변수명 = new LinkedList();

  - 위 같은 경우는 어떤 자료형이든 삽입, 삭제 가능(이전에 int형을 넣었어도 String형 삽입 가능)

• 하지만, 타입세이프가 되어야 안전하기 때문에 위에껄 쓰는걸 추천한다

Queue 요소 넣기

q.add(삽입할 value);

  ㄴ 반환 값(boolean): 삽입 성공 시 true / 실패 시  Exception발생

 

q.offer(삽입할 value);

  ㄴ 반환 값(boolean): 삽입 성공 시 true / 실패 시 false 반환

Queue 요소 꺼내기

q.remove();

  ㄴ 반환 값(삭제된 value의 자료형): 삭제된 value / 공백 큐이면 Exception("NoSuchElementException") 발생

 

q.remove(삭제할 value);

  ㄴ 반환 값(boolean): 큐에 해당 value가 존재하면 해당 값 삭제 후 true / 존재하지 않으면 false 반환

 

q.poll();

  ㄴ 반환 값(삭제된 value의 자료형): 삭제된 value / 공백 큐이면 null 반환

Queue 요소 가져오기

q.element();

  ㄴ 반환 값(큐 head에 위치한 value의 자료형): 큐 front에 위치한 value / 공백 큐이면 Exception("NoSuchElementException") 발생

 

q.peek();

  ㄴ 반환 값(큐 head에 위치한 value의 자료형): 큐 front에 위치한 value / 공백 큐이면 null 반환

Queue 비었는지 확인

q.isEmpty();

  ㄴ 반환 값(boolean): 공백 큐이면 true / 공백 큐가 아니면 false 반환

Queue 사이즈

q.size();

  ㄴ 반환 값(int): 큐 사이즈 반환

Queue 시간복잡도

• 삽입 : O(1)
• 삭제 : O(1)
• 탐색 : O(N)