[Java/자료구조] 선형구조 - 큐(Queue) 이해하기: 일반 큐, 우선순위 큐(Priority Queue) 이해하기

반응형

 

 

해당 글에서는 자료구조에서 선형구조의 큐 중에서 ‘우선순위 큐(Priority Queue)'에 대해 이해를 돕기 위해 작성한 글입니다.

 

 

 

 

 

💡 [참고] 자료구조의 전체 구조를 확인해봅니다.

- 해당 부분은 선형 구조 중 큐 >> 일반 큐, 우선순위 큐에 대해 자세히 알아봅니다.

 

 

 

💡 우선순위 큐를 이해하기 전에 알아야 할 선형구조와 큐에 대해 간단히 알아봅니다.

 
 

1) 선형구조(Linear Structure), 큐(Queue)

---

1. 선형 구조(Linear Structure)

---

💡  선형 구조(Linear Structure)

- 데이터를 저장하기 위한 기본적인 형태로 데이터가 '일렬로 나열'되어 있을 뿐만 아니라 데이터 간에 순서가 있고 논리적으로 이어져 있는 구조를 의미합니다.

- 선형구조에는 큐(Queue), 스택(Stack), 덱(deque)이 있습니다.
- 큐는 선입선출(FIFO, First-In-First-Out)의 특성을 가지며 스택은 후입선출(LIFO, Last-In-First-Out)의 특성을 가지고 덱(deque)은 양쪽 끝에서 삽입과 삭제가 가능한 형태의 구조를 가집니다.

 

https://goodgid.github.io/DS-Linear-and-NonLinear/

 
 
 

2. 큐(Queue)

---

 💡 큐(Queue)

- 선형 구조의 형태이며 데이터를 일시적으로 쌓아두기 위한 자료구조 중 하나로 선입선출(FIFO, First-In-First-Out)의 특성을 가집니다.

- Java에서 큐는 인터페이스의 역할을 수행하며 ArrayDeque, LinkedList, PriorityQueue 등을 통해서 구현체를 구현합니다.

 
 

3. 큐의 동작 과정

---

연산	설명	Java 메서드
Enqueue	큐의 맨 뒤(rear)에서 데이터를 ‘추가'하는 연산을 의미합니다.	add(E e), offer(E e)
rear	큐의 맨 뒤에 위치한 데이터를 가리키는 포인터입니다.	remove(), poll()
Dequeue	큐의 맨 앞(front)에 데이터를 ‘추출’하는 연산을 의미합니다	element(), peek()
front	큐의 맨 앞에 위치한 데이터를 가리키는 포인터입니다.	-

💡 큐의 동작과정

- 큐에서의 Enqueue(삽입)과 Dequeue(추출) 과정은 front와 rear 포인터를 기준으로 작동합니다.
- 결론적으로 데이터가 저장되는 곳은 ‘rear’ 부분이며 데이터가 추출되는 부분은 ‘front’에서만 수행을 합니다.
(* rear와 front 부분은 포인터로 상황에 따라 바뀌게 됩니다.)


💡 큐에 데이터가 삽입되는 과정

1. 데이터를 삽입할 때는 먼저 ‘rear’가 가리키고 있는 위치에 데이터를 ‘저장’합니다.
(* 큐의 요소 중 제일 마지막 부분을 의미합니다)

2. ‘rear 위치'는 다음 데이터가 ‘삽입될 위치로 이동'됩니다.


💡큐에 데이터가 추출되는 과정

1. 데이터가 추출할 때는 먼저 ‘front’가 가리키고 있는 위치에 데이터를 ‘추출’합니다.
(* 큐 내의 요소 중 가장 첫 번째 부분을 의미합니다)

2. ‘front의 위치'는 다음 데이터가 ‘추출될 위치로 이동'됩니다.

 
 

[ 더 알아보기 ] 

💡 그러면 rear로 맨뒤에 데이터가 들어가는데 왜 먼저 추출이 되는 걸까?

- 맨 뒤에 데이터를 삽입하는 Enqueue 과정에서 rear가 이동하므로 rear로 데이터가 들어가지만, front 포인터를 가리키고 있어서 먼저 나갈 수 있습니다.


💡 그러면 결론적으로 데이터는 순차적으로 쌓이는 거지만 front, rear 포인터가 이동하는 게 맞는 건가?

- 데이터는 순차적으로 쌓이지만 가리키고 있는 front, rear 포인터가 변경되면서 삽입될 위치와 추출될 위치를 결정하여 FIFO과정이 성립됩니다.

 

💡 [참고] 이전에 작성한 선형구조에 대해 이해를 하시면 도움이 됩니다. 

[Java/자료구조론] 선형구조 이해하기 -1 : 큐(Queue), 스택(Stack), 덱(Deque)

 
 
 

2) 우선순위 큐 (Priority Queue)

---

💡 우선순위 큐(Priority Queue)

- 큐(Queue) 데이터 구조를 기반으로 데이터를 ‘일렬로 늘어놓은 다음’ 그중에서‘가장 우선순위가 높은 데이터'를 '가장 먼저 꺼내오는 방식’으로 동작하는 클래스를 의미합니다.

- Queue 인터페이스를 상속받기 때문에 Queue 인터페이스에서 정의된 메서드들도 사용할 수 있습니다.

 

💡 우선순위 동작과정

- 우선순위 큐에서도 큐와 동일하게 Enqueue(삽입)과 Dequeue(추출) 과정은 front와 rear 포인터를 기준으로 작동합니다.
- 결론적으로 데이터가 저장되는 곳은 ‘rear’ 부분이며 데이터가 추출되는 부분은 ‘front’에서만 수행을 합니다.

우선순위 큐에서 enqueue는 새로운 요소를 큐에 추가하는 과정입니다. 이때, 새로운 요소는 우선순위를 가지고 있으며, 큐 내에서 이 요소는 다른 요소들보다 우선순위가 높게 취급됩니다.

따라서, enqueue 과정은 큐의 끝에 새로운 요소를 추가하고, 우선순위를 고려하여 요소의 위치를 조정합니다. 이때, 적절한 위치를 찾기 위해 우선순위를 비교하며, 우선순위가 높은 요소가 먼저 위치하도록 합니다.



💡 우선순위 큐에 데이터가 삽입되는 과정

1. 데이터를 삽입할 때는 먼저 ‘rear’가 가리키고 있는 위치에 데이터를 ‘저장’합니다.
(* 큐의 요소 중 제일 마지막 부분을 의미합니다)

2. 우선순위를 고려하여 요소의 위치를 조정합니다.
( * 적절한 위치를 찾기 위해 우선순위를 비교하며 우선순위가 높은 요소가 먼저 위치하도록 자동으로 조정됩니다.)

3. ‘rear 위치'는 다음 데이터가 ‘삽입될 위치로 이동'됩니다.


💡 우선순위 큐에 데이터가 추출되는 과정

1. 데이터를 추출할 때는 데이터의 ‘front’를 가리키고 있는 위치에 데이터를 추출합니다.

2. 우선순위를 고려하여 요소의 위치를 조정합니다.
( * 적절한 위치를 찾기 위해 우선순위를 비교하여 우선순위가 높은 요소가 먼저 위치하도록 자동으로 조정됩니다.)

3.  ‘front’ 위치가 다음 데이터가 추출될 위치로 이동시킵니다.


3. 데이터가 우선순위를 가지는 다른 데이터보다 우선순위가 높은 데이터가 있다면 해당 데이터를 ‘front’로 이동시킵니다.

 

[ 더 알아보기 ] 

💡 우선순위 내에 동일한 숫자가 여러 개 있다면 어떤 요소가 제거되는가?

- 큐 내에 우선순위가 같은 요소가 여러 개 있다면 일반적으로 먼저 큐에 추가된 요소가 먼저 제거됩니다.


💡 큐(Queue), 우선순위 큐(Priority Queue)에 대한 차이

- 먼저 들어온 것이 먼저 나가는(FIFO) 자료구조이고, 우선순위 큐는 우선순위가 높은 것이 먼저 나가는 자료구조입니다. 즉, 큐는 먼저 들어온 것이 먼저 처리되어야 할 때 사용하고, 우선순위 큐는 처리 순서가 우선순위에 따라 결정되어야 할 때 사용합니다.

 
 

 [참고] Priority Queue API 문서에 대해서 궁금하시면 아래의 글이 도움이 됩니다.

[Java/API] Priority Queue Method API Document : Java 11

 
 

1. Queue의 주요 동작 메서드

---

메서드	리턴 값	분류	설명
add(E e)	boolean	큐 요소 삽입	지정된 요소를 이 '우선 순위 큐에 삽입'합니다.
offer(E e)	boolean	큐 요소 삽입	지정된 요소를 이 '우선 순위 큐'에 삽입합니다.
remove(Object o)	boolean	큐 요소 삭제	이 큐에서 지정된 요소의 '단일 인스턴스(있는 경우)를 제거'합니다.
poll()	E	큐 요소 삭제	큐의 head(맨 앞)에 있는 요소를 제거하고 반환합니다. 큐가 비어있는 경우 null을 반환합니다.
element()	E	큐 요소 조회	큐의 head(맨 앞)에 있는 요소를 반환합니다. 큐가 비어있는 경우 예외를 던집니다.
peek()	E	큐 요소 조회	큐의 head(맨 앞)에 있는 요소를 반환합니다. 큐가 비어있는 경우 null을 반환합니다.

 
 
 

2. 우선순위 큐의 생성자 : 오름차순/내림차순 우선순위 큐

---

💡 우선순위 큐에서는 Enqueue(추가), Dequeue(추출)의 동작이 발생하는 경우 지정한 오름차순/내림차순에 따라서 순서가 정렬이 됩니다.

💡 이 오름차순과 내림차순은 최초 객체를 생성할 때 정해집니다. 기본적으로 오름차순의 형태를 가지고 있고 기본적으로 오름차순 형태의 구조를 가지며 내림차순 형태의 구조로도 구성이 가능합니다.

생성자	설명
PriorityQueue()	기본 초기 용량 (11)으로 구성된 PriorityQueue를 생성하고 해당 요소를 Comparable에 따라 정렬합니다.
PriorityQueue(int initialCapacity)	지정된 초기 용량으로 PriorityQueue를 생성하고 해당 요소를 Comparable에 따라 정렬합니다.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)	지정된 초기 용량으로 PriorityQueue를 생성하고 지정된 comparator에 따라 해당 요소를 정렬합니다.
PriorityQueue(Collection<? extends E> c)	지정된 컬렉션의 요소를 포함하는 PriorityQueue를 생성합니다.
PriorityQueue(Comparator<? super E> comparator)	지정된 comparator에 따라 해당 요소를 정렬하며 기본 초기 용량으로 PriorityQueue를 생성합니다.
PriorityQueue(PriorityQueue<? extends E> c)	지정된 우선 순위 큐의 요소를 포함하는 PriorityQueue를 생성합니다.
PriorityQueue(SortedSet<? extends E> c)	지정된 정렬된 집합의 요소를 포함하는 PriorityQueue를 생성합니다.

// deafult: 오름차순 우선순위 큐 
PriorityQueue<Integer> ascendingQueue = new PriorityQueue<>();

// 내림차순 우선순위 큐 
PriorityQueue<Integer> descendingQueue = new PriorityQueue<>(Comparator.reverseOrder());

 
 
 
 

3) 우선순위 큐의 동작 과정

---

1. 우선순위 큐 요소 추가 : pq.add() , pq.offer()

---

💡 우선순위 큐는 큐의 특성 FIFO(선입선출) 특성으로 인해 첫 번째 요소로 계속 값이 순차적으로 들어갑니다. 그리고 출력을 할 때는 우선순위(오름차순)에 따라서 정렬이 됩니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(1);
pq.add(3);
pq.add(2);

System.out.println("우선 순위 큐 값 ::" + pq); // 1, 3, 2

while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // 1 // 2 // 3
}

 

[ 더 알아보기 ]

💡 pq 자체를 출력하면 정렬이 안 되는 이유는 무엇일까?

- Object.toString()을 이용하여 출력됩니다. 일반적으로 이 출력 결과는 요소들이 정렬되어 있지 않게 됩니다. 따라서 우선순위 큐에 저장된 요소를 정렬된 순서로 출력하려면 pq.poll()과 같은 메서드를 사용하여 하나씩 요소를 꺼내 출력해야 합니다.

 
 

2. 우선순위 큐 요소 추출 : pq.poll()

---

💡 우선순위 큐는 큐의 특성 FIFO(선입선출) 특성으로 인해 첫 번째 요소의 값을 추출합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(1);
pq.add(3);
pq.add(2);

pq.poll();
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // [2, 3]
}


pq.poll();
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // [3]
}

pq.poll();
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // []
}

 
 
 

3. 우선순위 큐 요소 조회 : pg.peek()

---

 💡 우선순위 큐에서 높은 우선순위 인 값을 조회하는 방법은 peek() 메서드를 이용합니다.
해당 예시에서는 poll()로 순차적으로 처음에 들어온 값을 추출하고 그다음 값을 조회하는 방법으로 peek() 메서드를 사용하였습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(1);
pq.add(2);
pq.add(3);

System.out.println(pq.poll()); // 1
System.out.println("peek :: " + pq.peek()); // 2
System.out.println(pq.poll()); // 2
System.out.println("peek :: " + pq.peek()); // 3
System.out.println(pq.poll()); // 3
System.out.println("peek :: " + pq.peek()); // null

 
 
 

4) [참고] 우선순위 큐를 문자열로 사용이 가능한가?

---

💡 문자열도 동일하게 이용이 가능합니다.
💡 우선순위 큐에서 문자열의 알파벳 순서를 기준으로 오름차순 정렬이 이루어집니다.

PriorityQueue<String> queue = new PriorityQueue<String>();
queue.add("apple");
queue.add("banana");
queue.add("cherry");

String firstElement = queue.peek(); // firstElement = "apple"
String removedElement = queue.remove(); // removedElement = "apple"

 
 
 

💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.

분류	주제	링크
선형구조	순차 리스트(Array, ArrayList)	https://adjh54.tistory.com/317
선형구조	연결 리스트(단순, 이중, 순환 리스트)	https://adjh54.tistory.com/319
선형구조	큐, 스텍, 덱	https://adjh54.tistory.com/135
선형구조	큐, 스텍, 덱 (문제로 이해하기)	https://adjh54.tistory.com/185
선형구조	큐(일반 큐, 우선순위 큐)	https://adjh54.tistory.com/226
비선형구조	트리(일반트리/이진트리)	https://adjh54.tistory.com/320
비선형구조	균형트리(AVL, 레드-블랙, B-트리)	https://adjh54.tistory.com/324
비선형구조	그래프(방향, 무방향 그래프)	https://adjh54.tistory.com/325

 

 

 

 
 
오늘도 감사합니다. 😀