[JAVA] Queue, PriorityQueue 구현 및 시간복잡도

Queue란?

- Java Queue는 Java Collection 인터페이스의 일부이며, Java List와 같이 순서가 지정되지만 용도가 약간 다르다. 

큐의 끝에 삽입요소를 갖도록 설계하는 데이터 구조이고, 요소는 큐의 선두로부터 제거된다.

- FIFO(First In First Out) 방식 (LIFO인 큐와는 반대)

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

- 삽입, 삭제 작업이 용이하다

- 컴퓨터 버퍼에서 주로 사용된다

 

http://tutorials.jenkov.com/java-collections/queue.html

 

 

 

Queue 구현

https://www.javatpoint.com/collections-in-java

• java.util.LinkedList
• java.util.PriorityQueue

큐를 구현하는 방법은 2가지가 있는데

 

1. 연결 리스트 (LinkedList)

- 시간복잡도

add             : O(1)
remove          : O(1)
get             : O(n)
Contains        : O(n)
iterator.remove : O(1)
java 1.2에 추가, thread-safe 보장 안함
특징 : 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다.
   - 데이터 추가/삭제시 빠름
   - 데이터 검색시 처음부터 노드를 순화해야 되기 때문에 느림

 

- Queue 인터페이스 형태로 LinkedList를 통해서 생성한다. 사이즈가 가변적이고, 쉽게 늘어난다는 특징이 있다.

// import 문
import java.util.LinkedList; 
import java.util.Queue; 

// Queue<Element> queue = new LinkedList<>()와 같이 선언해주면 된다
Queue<Integer> queue = new LinkedList<>(); 
Queue<String> queue = new LinkedList<>();

// queue에 값을 추가하고 싶다면 add(value)또는 offer(value) 메서드를 활용
queue.add(1);
queue.offer(2);

// queue의 첫번째 값 참조
queue.peek();

// queue에서 값을 제거하고 싶다면 poll() 이나 remove 메서드를 활용
// poll()함수는 큐가 비어있으면 null을 반환한다
queue.poll(); // 첫번째 값을 반환하고 제거, 비어있다면 null
queue.remove(); // 첫번째 값 제거
queue.clear(); // queue 초기화

 

2. 우선순위큐 (Priority Queue)

- 시간복잡도

시간복잡도
offer(입력)   : O(log n)
peek(get)     : O(1)
poll(반환)    : O(log n)
size          : O(1)
natural order : JVM에서 제공하는 일반적인거와 다를수 있음 순서 ex) 문자는 ASCII 순서로 정렬
java 1.5 에서 나옴
특징 : 일반적은 큐는 FIFO의 구조를 가지지만 자연 네추럴 오더에 따라 정렬
      - Null을 허용하지 않는다.

 

- 말그대로 큐의 성질은 가졌으나, 각 데이터가 우선순위를 갖고 있어 우선순위가 높은 순서대로 나온다

(우선순위가 동일할 경우는 큐의 순서대로)

- 내부 요소는 힙으로 구성되어 이진트리의 구조로 이루어져 있다. 시간복잡도는 O(NLogN)

- Min Heap으로 데이터를 정렬하고 데이터를 출력한다

- 값 추가, 삭제 등은 연결 리스트 (LinkedList)와 동일

// import
import java.util.PriorityQueue;

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();//큐 생성

//int형 우선순위가 낮은 숫자 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 우선순위가 높은 숫자 순
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 우선순위가 낮은 숫자 순
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 우선순위가 높은 숫자 순
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

 

시간복잡도 참조

- https://www.grepiu.com/post/9