큐(Queue)란 스택과 다르게 FIFO(First In First Out)의 구조를 가지고 있다.
그래서 먼저 들어온 데이터가 먼저 나가는 형식을 가지고 있다.
예를 들어 마트에서 줄 서는 것을 생각하면 쉽다
컴퓨터의 작업 스케쥴링, 네트워크 요청 처리, 데이터 스트림 관리 등 많은 시스템에서 큐가 활용된다.
큐(Queue)의 특징
- 선입선출(FIFO) 방식 : 큐는 가장 먼저 입력된 요소가 가장 먼저 출력되는 선입선출 방식을 따른다
- 입력과 출력이 한 방향에서 이루어짐 : 큐에서 데이터는 한쪽 끝에서만 삽입되고, 다른 한쪽 끝에서만 삭제된다.
- 데이터의 조회는 Front에서만 이루어짐 : 데이터 조회는 Front 위치에서만 이루어진다. Rear위치에서 데이터를 조회하는 건 허용되지 않는다.
- 속도와 효율성 : Queue의 이런 구조는 데이터의 삽입과 제거가 상수 시간(O(1))에 이루어져 빠르고 효율적이다
큐(Queue)의 활용
- 버퍼 : 컴퓨터의 CPU와 I/O 장치들 사이에서 데이터를 일시적으로 보관하는 버퍼(buffer)에서 Queue가 사용된다.
- 프린터 대기열 : 프린터의 작업 목록은 Queue로 관리된다. 사용자가 요청한 출력 작업이 순서대로 처리되어야 하기 때문
- 프로세스 스케줄링 : 운영 체제에서 여러 프로세스들 중 어떤 것을 먼저 처리할지 결정하는 프로세스 스케줄링에서도 사용된다
- 너비 우선 탐색(BFS) 알고리즘 : 그래프 또는 트리의 너비 우선 탐색에서 사용된다.
- 캐시 구현 : 최근에 사용된 항목을 저장해 두는 캐시에서 Queue는 자주 사용된다. 가장 오래 전에 사용된 항목을 먼저 제거하는 방법을 구현하는데 Queue가 적합하다.
큐(Queue)의 단점과 해결방법(Feat. 우선순위 큐)
큐의 단점은 주로 그 특성인 FIFO(First In, First Out)에서 기인하는 경우가 많다.
단점
- 우선순위가 없다 : 큐는 기본적으로 FIFO라는 특성을 가지므로, 특정 항목이 우선순위를 가지고 있다면 그것을 반영하기 어렵다.
해결 방법
- 우선순위 큐(Priority Queue)를 사용하면 문제를 해결할 수 있다. 우선순위 큐는 각 항목이 우선순위를 가지고 있고, 가장 높은 우선순위를 가진 항목이 먼저 제거된다.
예제코드
import java.util.PriorityQueue;
public class PriorityQueue {
public static void main(String[] args) {
// 우선순위 큐 생성
PriorityQueue<Integer> numbers = new PriorityQueue<>();
// 우선순위 큐에 4 2 1 3으로 추가
numbers.add(4);
numbers.add(2);
numbers.add(1);
numbers.add(3);
System.out.println("PriorityQueue: " + numbers);
// 가장 작은 숫자부터 제거
int number = numbers.poll();
System.out.println("Removed number: " + number);
System.out.println("Updated PriorityQueue: " + numbers);
}
}PriorityQueue는 최소 힙 구조를 가지고 있으므로 가장 작은 요소가 우선순위를 가진다. 큰 요소가 우선순위를 가지게 하려면 커스텀 비교자를 사용하면 된다.
numbers라는 PriorityQueue에 숫자를 추가하고 우선순위에 따라 가장 작은 숫자를 제거한다
PriorityQueue: [1, 3, 2, 4]
Removed number: 1
Updated PriorityQueue: [2, 3, 4]이런 식으로 처음에는 4, 2, 1, 3 순서로 숫자를 추가하였으나, 우선순위에 따라 큐는 자동으로 정렬되므로 출력된 큐는 [1, 3, 2 4]의 순서를 가지게 된다.
의문점
PriorityQueue를 출력할 때 나는 1, 2, 3, 4로 정렬된 상태로 출력이 될 줄 알았다 하지만 1 , 3, 2, 4라고 출력이 되길래 좀 더 알아봤다.
이런 식으로 작성을 해봤고
이런 식으로 출력이 되는 앞 2개만 정렬을 하는 걸 확인할 수 있었다.
이유는 우선순위 큐는 Heap 자료구조의 원리를 사용하고 있어 삭제나 조회등의 메서드를 호출했을 때, 루트 노드를 기준으로 이루어진다 그렇기 때문에 루트 노드 외에는 정렬이 되어있지 않다는 걸 알았다.
또 다른 단점에는
- 데이터 접근의 제한성 : 큐에서 데이터는 항상 한 방향으로만 이동한다. 그래서 특정 데이터에 대한 빠른 접근이 필요한 경우에는 부적합할 수 있다.
해결책 : 데이터 접근의 제한성은 큐의 기본적인 특징이라 해결하기 위해선 다른 자료구조를 사용하는 것이 적절할 수 있다.
- 스택(Stack): 스택은 LIFO(Last In First Out) 형식을 가지고 있고 데이터를 추가하는데에 O(1)의 시간복잡도를 가지지만, 큐와 마찬가지로 데이터의 접근이 제한적이다. 스택은 깊이 우선 탐색(DFS)과 같은 재귀 알고리즘에서 유용하게 사용된다.
- 연결리스트(LinkedList): 연결 리스트는 각 요소가 다른 요소에 대한 참조를 가지고 있는 구조이다. 특정 요소에 접근하는데 O(n)의 시간이 걸리지만 중간에 요소를 추가하거나 삭제하는데에는 O(1)의 시간이 걸린다
- 해시 테이블(Hash Table): 해시 테이블은 키와 값을 매핑하는 구조로, 특정 키에 대한 값의 접근, 추가, 삭제가 평균적으로 O(1)의 시간복잡도를 가집니다.
- 배열(Array): 배열은 인덱스를 통해 빠르게 데이터에 접근할 수 있지만, 배열의 크기를 변경하는 것은 일반적으로 비용이 많이 든다.
결론적으로 임의의 요소에 빠르게 접근하고자 할 때는 해시 테이블이나 배열을 사용할 수 있고 반면에 데이터의 추가와 삭제가 빈번하게 일어나는 경우 연결 리스트가 적절할 수 있다.
- 메모리 사용의 비효율성 : 데이터에 큐가 계속 쌓이는 경우, 메모리 사용이 증가하게 되어 비효율적일 수 있다.
해결책 : 메모리 사용의 비효율성은 큐의 크기와 관련이 있다. 큐가 무한히 커지면 메모리 사용량이 늘어나게 되므로 이를 제어하는 방법이 필요하다.
- 크기 제한 설정 : 큐의 크기를 제한하는게 간단한 해결책일 수 있다. 하지만 처리해야 하는 작업의 양이 큐의 크기를 초과할 경우 데이터 손실을 발생시킬 수 있다.
- 메모리 관리 정책 : 메모리 관리 정책을 도입해서 큐의 크기가 특정 한계를 초과할 경우 오래된 데이터를 삭제하거나 다른 저장소로 이동할 수 있다.
- 데이터 축소 : 데이터를 압축하거나 필요 없는 정보를 제거하여 메모리 사용을 줄일 수 있다.
- 데이터 저장 오프로드 : 큐의 데이터를 디스크 등의 오프라인 저장소에 저장하는 방법도 있지만 디스크 비용이 추가로 발생한다.
큐(Queue) 관련 메서드 정리
Queue<Integer> queue = new LinkedList<>();
//큐에 요소 추가(enqueue)
queue.add(1); //문제 상황에서 예외 발생
queue.offer(2); //문제 상황에서 false 리턴
//큐에서 요소 제거(dequeue)
queue.remove(); // 문제 상황에서 예외 발생
queue.pool(); //문제 상황에서 null 리턴
//큐 비우기
queue.clear();
//큐의 최전방 요소 확인
queue.element(); // 문제 상황에서 예외 발생
queue.peek(); // 문제 상황에서 null 리턴
//큐에 있는 요소 수 반환
queue.size();
//큐가 비어 있으면 true 를 반환
queue.isEmpty();
//큐가 특정 요소를 포함하고 있는지 확인
queue.contains(Object o);
//큐에 있는 요소들을 순차적으로 접근하는 Iterator 반환
queue.iterator();
//큐에 있는 모든 요소들을 포함하는 배열 반환
queue.toArray();