선형자료구조 - 큐
📌 큐
1. 선입선출(First In First Out; FIFO) 자료구조
- 먼저 들어온 데이터가 먼저 나가는 구조
2. 입력 순서대로 데이터 처리가 필요할 때 사용
- ex) 프린터 출력 대기열, BFS(Breath-First Search) 등
- 프린터 출력 대기열 : 문서 작업 요청 후 여러 개가 쌓이면 가장 먼저 요청한 작업을 수행, PC가 종료되어도 프린터 내부 Pool에서 큐 구조로 먼저 들어온 요청을 수행
- BFS(Breath-First Search) : 트리 구조, 너비 우선 탐색으로 root 상단부터 시작해 아래로 진행하는 데이터 탐색 등
큐 기본 구조
- 선입선출(FIFO) 구조를 따름
- 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐
- 큐에서 데이터가 꺼내지는 곳은 Front, 꺼내는 동작은 Dequeue
- 큐에서 데이터가 추가되는 곳은 Rear, 추가 동작은 Enqueue
큐 기본 연산
- 데이터 추가(Enqueue)
- 큐에 데이터 추가
- 큐에 데이터 추가
- 데이터 꺼내기(Dequeue)
- 큐에서 데이터 꺼내기
큐 기본 코드
import java.util.LinkList;
import java.util.Queue;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// queue queue = new Queue();
// 위 queue는 내부함수로 인터페이스로 구현이 되어있기 때문에 바로 객체를 생성해서 사용하지 못하고,
// 추상클래스나 인터페이스는 내부 자바 메서드를 추가적으로 구현해서 사용해야함
Queue queue = new LinkedList();
// LinkedList()에 queue에 필요한 연산이 포함되어있음, 다형성을 이용하여 사용
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
System.out.println(queue); // [1, 2, 3, 4, 5]
System.out.println(queue.poll()); // 1
System.out.println(queue); // [2, 3, 4, 5]
System.out.println(queue.poll()); // 2
System.out.println(queue); // [3, 4, 5]
System.out.println(queue.peek()); // 3
System.out.println(queue); // [3, 4, 5]
System.out.println(queue.contains(3)); // true
System.out.println(queue.size()); // 3
System.out.println(queue.isEmpty()); // false
queue.clear();
System.out.println(queue); // []
System.out.println(queue.poll()); // null
큐는 가장 먼저 추가된 데이터가 가장 먼저 제거되는 FIFO 원칙을 따르고,
기본 기능으로서 큐의 맨 뒤에 새로운 데이터를 추가하는 enqueue,
큐의 앞쪽(Front) 데이터를 제거하고 반환하는 dequeue,
큐의 맨 앞쪽(Front) 데이터를 제거하지 않고 반환하는 peek,
큐가 비어있는지 확인하는 isEmpty를 잘 숙지해야 되겠다.
구현 방법으로는 배열을 사용하면 고정된 크기의 큐를 만들 수 있고, 연결 리스트를 사용하면 동적으로 크기를 조절할 수 있다.
Java에서 'Queue' 인터페이스를 통해 다양한 큐 구현체 사용 가능(예 : LinkedList)
응용 분야로는 운영체제(OS)에서 프로세스를 처리할 때
대기 중인 프로세스들을 큐에 저장하고 차례대로 처리 가능한 프로세스 스케줄링,
이벤트 기반 시스템에서 발생한 이벤트를 큐에 저장하고, 순서대로 처리하는 이벤트 처리,
데이터 패킷을 큐에 저장하고 차례대로 전송할 수 있는 네트워크 데이터 전송이 있다.