큐(Queue)

큐는 FIFO 선입선출(First In First Out)의 구조를 가진다.

즉, 큐에서는 먼저 들어온 데이터가 가장 먼저 나가는 구조이다.

큐는 입력 순서대로 데이터 처리가 필요할 때 사용

그래프의 넓이 우선 탐색(BFS)에서 사용된다.

Enqueue : 큐 맨 뒤에 데이터 추가

Dequeue : 큐 맨 앞쪽의 데이터 삭제

위의 그림에 나온 것처럼 큐는 앞뒤가 다른 역할을 수행한다. 큐의 앞부분은 front는 삭제 연산만 수행하고 큐의 뒷부분은 rear는 삽입 연산만 수행한다. 보통 컴퓨터 버퍼에서 주로 사용되고, 여러 개가 한꺼번에 입력이 들어올 때 대기열을 만들어 순차적으로 처리할 때 사용된다.

큐(Queue)의 연산

메서드	설명
boolean add(Object)	큐에 데이터 추가성공하면 true 반환, 단 저장공간이 부족하면 IllegalStateExcepetion 발생
Object remove()	큐에서 객체를 꺼내 반환비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어옴peek과 달리 큐가 비어있으면 NoSuchElement 발생
boolean offer(value)	큐에 데이터 추가성공하면 true, 실패하면 false 반환
Object poll()	큐에서 객채를 꺼네 반환비어있으면 null 반환.
Object peek()	삭제 없이 요소를 읽어옴큐가 비어있으면 null 반환

큐 사용 시 예외발생이 나지 않으려면 add, remove, elemant 대신 offer, poll, peek을 사용하는게 좋다.

큐(Queue) 사용법

Queue는 Collection 프레임워크의 일부이고 java.util 패키지에 소속되어 있기 때문에 Queue를 사용하려면 먼저 다음과 같이 import를 해야 한다.

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

Queue는 연결 리스트로 보통 구현되기 때문에 LinkedList도 import 해야 된다.

만약에 이렇게 import 하는 걸 두 줄 쓰기 싫다면 다음과 같이 해도 된다.

import java.util.*;

java.util.* import 하면 java.util 패키지 전부를 import 한 거와 같다.

Queue 선언

Queue<타입> queue = new LinkedList<타입>();// 타입 Queue 선언
Queue<타입> queue = new LinkedList<>();// new <> 타입 생략 가능

Queue 값 추가

Queue<Integer> queue = new LinkedList<>();
queue.add(1);// 1 추가
queue.offer(2);// 2 추가
queue.offer(3);// 3 추가

Queue 값 삭제

Queue<Integer> queue = new LinkedList<>();
queue.add(1);// 1 추가.  [1]
queue.offer(2);// 2 추가 [1, 2]
queue.offer(3);// 3 추가 [1, 2, 3]
queue.offer(4);// 4 추가 [1, 2, 3, 4]

queue.remove();// 1 반환 [2, 3, 4]
queue.peek();// 2 꺼내질 데이터 확인
queue.size();// 3 
queue.poll();// 2 반환   [3, 4]
queue.contains(3);// true 반환
queue.isEmpty();// false 반환
queue.poll();// 3 반환
queue.clear();// 모든 데이터 삭제 []

queue.remove();// NoSuchElementException 발생
queue.offer();// null 반환

시간 복잡도 (Time complexity)

Operation	Average	Worst
Access	O(n)	O(n)
Search	O(n)	O(n)
Insert (add)	O(1)	O(1)
Delete (remove)	O(1)	O(1)