목차
큐의 특징
큐(Queue)이란 데이터를 차곡차곡 쌓아 올리는 데이터 관리 방식이다.
-
FIFO(First in First Out)구조
FIFO는 먼저 들어온 데이터가 제일 먼저나가는, 쉽게 말해 선착순과 같은 구조이다.
또한 큐은 Java에서 제공하는 내장 자료구조를 사용하여 구현없이 사용이 가능하다.
큐의 특징
-
선입선출
가장 먼저 들어온 데이터가 가장 먼저 나간다 -
단방향 접근 방식
데이터의 삭제는 큐의 맨 앞, 데이터의 삽입은 큐의 맨 뒤에서 이루어진다 중간의 데이터에는 직접 접근이 불가능하다
큐의 장점
- 구현이 간단
큐는 기본적인 연산이 단순하고, 삽입 삭제가 일정 위치에서 이루어 지기 때문에 구현이 간단하다. - 순서 보장
데이터의 순서가 보장되며, 작업의 우선순위를 관리할때 용이하다. - 효율적인 메모리 사용
순차적인 데이터를 처리하는것에 효율적이다.
큐의 단점
- 접근성의 제한
데이터의 추가 및 삭제가 큐의 양끝에서만 일어나기 때문에, 연산 속도는 빠를지라도 중간 데이터에 직접 접근하는등의 작업이 불가능하다. 즉, 데이터의 특정 위치에 접근하는 작업이 스택을 활용하기엔 부적합하다. - 메모리 관리의 어려움
큐를 배열로 구현할 경우 크기를 지정해야하기 때문에 확장이 어렵다.
단, 연결 리스트를 사용하여 이를 해결할 수 있다.
큐를 활용하는 방식
스택은 기본적으로 순서를 정해서 실행하는 구조이다. 이러한 특징을 활용할 수 있는 방식으로는,
1.너비 우선 탐색(BFS): 그래프나 트리구조에서 주로 활용하며, 최단 경로 찾기등과 같은 알고리즘을 해결할때 용이하다.
2.작업 스케줄링: 여러 작업을 순차적으로 처리해야 할때 순위를 매겨 작업을 처리하게 할 수 있다.
선형큐와 원형큐
선형 큐
큐는 기본적으로 front와 rear를 가지고 있다.
선형큐는 새로 들어온값을 rear의 위치에 집어넣고, 삭제는 front의 위치에서 수행된다.
이 방식은 큐의 개념에 대해 이해하기엔 좋지만 False Overflow라는 단점이 있다.
실제로는 배열에 빈 공간이 있어도 rear가 배열 끝에 도달하게 되면 더 이상 삽입이 불가능하다.
이를 해결하기 위해선 데이터를 삭제할때 front와 rear를 빈자리 만큼 앞으로 당기는
Shifting과 원형 큐를 사용할 수 있다.
원형 큐
원형큐의 원리는 간단하다. 기본적인 틀은 선형큐와 유사하지만, rear을 연산할때 rear+1이 아닌 (rear+1)%size //배열의 크기 만큼 증가 시키면 된다. 실제로는 선형 배열이지만, 논리적으로는 rear의 마지막과 시작부분이 맞닿아 있기 때문에 원형처럼 사용된다.
큐 응용 예시
작업 스케줄링
최근 작업을 기억하고, 새로운 작업이 추가될때 가장 오래된 작업을 삭제시켜주는 코드이다.
접근방법:
- 큐의 FIFO 특성을 활용하여 작업 순서 관리
- 최대 크기를 지정하여 오래된 작업 자동 제거
- 새로운 작업이 들어올 때마다 크기 체크
세부구현:
1. 새 작업 추가 시
1-1. 큐가 최대 크기에 도달했는지 확인
1-2. 최대 크기라면 가장 오래된 작업(큐의 첫 번째 요소) 제거
1-3. 새 작업을 큐의 끝에 추가
2. 작업 목록 조회 시
2-1. 현재 큐에 있는 모든 작업 반환
3. 작업 개수 확인 시
3-1. 현재 큐의 크기 반환import java.util.ArrayDeque;
import java.util.Queue;
class RecentTaskManager {
private int maxSize; // 최대 저장 가능한 작업 수
private Queue<String> tasks; // 작업을 저장할 큐
public RecentTaskManager(int maxSize) {
this.maxSize = maxSize;
this.tasks = new ArrayDeque<>();
}
// 새로운 작업 추가
public void addTask(String task) {
// 1. 새 작업 추가 시
// 1-1. 큐가 최대 크기에 도달했는지 확인
if (tasks.size() >= maxSize) {
// 1-2. 최대 크기라면 가장 오래된 작업(큐의 첫 번째 요소) 제거
tasks.poll();
}
// 1-3. 새 작업을 큐의 끝에 추가
tasks.offer(task);
System.out.println("작업 추가: " + task);
System.out.println("현재 작업 목록: " + tasks);
}
// 2. 작업 목록 조회 시
// 2-1. 현재 큐에 있는 모든 작업 반환
public Queue<String> getTasks() {
return tasks;
}
// 3. 작업 개수 확인 시
// 3-1. 현재 큐의 크기 반환
public int getSize() {
return tasks.size();
}
public static void main(String[] args) {
RecentTaskManager manager = new RecentTaskManager(3);
// 테스트 케이스
String[] testCases = {
"작업1", // [작업1]
"작업2", // [작업1, 작업2]
"작업3", // [작업1, 작업2, 작업3]
"작업4", // [작업2, 작업3, 작업4]
"작업5" // [작업3, 작업4, 작업5]
};
// 테스트 실행
for (String task : testCases) {
manager.addTask(task);
}
}
}