> [JAVA 자료구조] Queue(큐) 개념과 사용

         

■

1. 개념

먼저 집어 넣은 데이터가 먼저 나오는 선입선출(First In First Out; FIFO)의 자료구조. 
목록에 대한 모든 추가가 한쪽 끝에서 이루어지고 목록의 모든 삭제가 다른 쪽 끝에서 이루어진다.

ex. '표를 사기 위해 줄을 서는 사람들'

 

 

(1) 용어

- Front : 큐를 나타내는 배열에서 첫 번째 요소가 저장되는 인덱스로 데이터가 나가는 위치이다.

- Rear/ Back :  대기열을 나타내는 배열에 마지막 요소가 저장되는 인덱스로 데이터가 들어오는 위치이다.

- Enqueue : 입력 동작

- Dequeue : 출력동작

 

 

(2) 특성

- 대기열은 여러 데이터를 처리할 수 있다.

- 우리는 양쪽 끝 모두에 접근할 수 있다.

- 빠르고 유연하다. 

 

 

(3) Queue 종류 

 1. 원형큐

: 마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 된다. 

 

2. 데크

양쪽에서 모두 삽입/인출이 가능한 스택과 큐의 특징을 모두 갖고 있다. 

 

3. 우선순위 큐 (Priority Queue)

: 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조이다.

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

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

priorityQueue.offer(2);     // priorityQueue에 값 2 추가
priorityQueue.offer(1);     // priorityQueue에 값 1 추가
priorityQueue.offer(3);     // priorityQueue에 값 3 추가
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

 

 

※ Priority Queue의 특징
1. 힙으로 구성되어 이진트리 구조로 이루어져 있음   
2. 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)

3. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임

 

 

 

 

■

2. 사용법 

 

(1) 선언 

Queue<Integer> queue = new LinkedList<>();

 

 

(2) 값 추가

q.add(x);

q.offer(x);

 

	add()	offer()
삽입 위치	맨 뒤에 값 삽입	맨 뒤에 값 삽입
값 추가 성공시	값 추가 성공 시 true 반환	값 추가 성공 시 true 반환
값 추가 실패시	큐가 꽉 찬 경우 IllegalStateException 에러 발생	false 반환

 

 

(3) 값 제거 

q.remove();
q.poll();
q.clear(); // 큐 비우기

 

	remove()	poll()
	맨 앞에 있는 값 반환 후 삭제	맨 앞에 있는 값 반환 후 삭제
실패시	큐가 비어있는 경우 NoSuchElementException 발생	큐가 비어있는 경우 null 반환

 

 

(4) 값 확인  

q.element();
q.peek();

 

	element()	peek()
반환 값	맨 앞에 있는 값	맨 앞에 있는 값
실패시	큐가 비어있는 경우 NoSuchElementException 발생	큐가 비어있는 경우 null 반환

 

※ (add, remove, element) vs (offer, poll, peek) 

문제 상황에서 에러를 발생 = > (add, remove, element)

문제 상황에서 null 혹은 false를 반환 => (offer, poll, peek)

 

 

 

 

 

■ 더 알아보기

 

PriorityQueue.toString이 잘못된 요소 순서를 반환하는 이유는 무엇입니까?

Why does PriorityQueue.toString return the wrong element order?

 

 

 

참고

https://coding-factory.tistory.com/603

https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%81%90

https://cocoon1787.tistory.com/774

https://www.geeksforgeeks.org/queue-data-structure/