큐(queue)

queue의 정의

FIFO(First In First Out) 구조로 저장하는 자료구조

FIFO: 먼저 집어 넣은 데이터가 먼저 나오는 것

시간복잡도

삽입/삭제: O(1)

java에서의 queue

Collection을 상속받는다.

Interface이기 때문에 LinkedList를 통하여 구현한다.

add: 원하는 요소를 삽입하는 메소드. 현재 사용 가능한 공간이 없으면 exception을 던진다.

offer: add와 하는 일은 똑같다. 하지만 현재 사용 공간이 없으면 false를 return한다. 값을 추가할 때는 offer() 추가하길 권장하고 있다.

remove와 poll: 요소를 삭제하는 역할을 한다. 차이점은 remove는 queue가 비어있다면 exception을 던지고, poll은 null을 던진다는 점이다.

element와 peek: queue에 head에 있는 요소를 보여준다. element는 queue가 비어있다면 exception을 던지고, peek은 null을 return한다.

PriorityQueue

알고리즘을 풀 때나, 여러 방면으로 자주 사용하는 queue인 거 같다.

이름은 queue이지만, 실제 구현에 사용되는 방식은 heap이다.

queue와의 가장 큰 차이점은 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.