큐: 큐 인터페이스와 활용

YeongJun Son·2024년 1월 15일

자료구조 큐

알고리즘을 배우다

목록 보기

6/6

들어가며

최초 작성일(yy/mm/dd): 24/01/15 최초 작성

학습 목표

자바8에서의 큐 이용법을 학습한다.
큐가 어떤 상황에서 활용되는지 간략하게 살펴본다.

학습 상황

자바에 내장된 큐 클래스를 이용할 때의 주의사항을 기억하고, Problem Solving 시에 효율적이고 적절하게 쓸 필요가 있다.

스택: Java.util.Queue

큐 인터페이스 뜯어보기

Fig 1. Java.util.Queue의 상속과 설명

출처: geeksforgeeks.com

큐와 상속

큐는 Collection 프레임워크를 직접적으로 상속하고 있습니다. 그런데 큐는 기본 Collection에 더해 삽입하고, 제거하고, 확인하는 추가적인 연산을 갖고 있습니다.

두 연산은 연산이 실패했을 때 (1) 에러를 내보내느냐 (2) 다른 값(null, false)을 내보내느냐에 따라 나뉩니다.

Collection에서 상속 받은 좌측 메서드는 에러를, 추가된 우측 메서드는 특정한 값을 내보냅니다. 이는 용량이 고정된 큐(capacity-fixed queue)을 위해 고안되었습니다. Java 8 공식 문서를 살펴보면 그 이유를 알 수 있습니다.

큐 메서드

Fig 2. Java.util.Queue의 메서드

출처: geeksforgeeks.com

add(E e)

용량 제한을 넘어서지 않는다면, 요소를 큐에 추가합니다. 성공하면 true를 반환하고, 요소가 들어갈 공간이 없다면 IllegalStateException 에러를 띄웁니다.
element()

큐의 head에 있는 값을 가져오지만, 제거하지는 않습니다.
offer(E e)

용량 제한을 넘어서지 않는다면, 요소를 큐에 추가합니다. 성공하면 true를 반환하고, 실패하면 false를 반환합니다.
peek()

큐의 head에 있는 값을 가져오지만, 제거하지는 않습니다. 큐가 비어있다면 에러를 띄우는 대신 null을 반환합니다.
poll()

큐의 head에 있는 값을 가져오고 제거합니다. 만약 큐가 비어있다면 null을 반환합니다.
remove()

큐의 head에 있는 값을 가져오고 제거합니다. 실패한다면 에러를 띄웁니다.
clear()

큐를 초기화합니다.

왜 큐는 메서드가 추가되었는가?

크기가 고정된 큐를 떠올려 봅시다.

만약 큐가 가득 차 있어 자료 삽입에 실패하는 상황이 일반적일 때, 에러를 매번 띄운다면 성능이 저하될 것입니다.

마찬가지로 큐가 비어 있어 자료 삭제에 실패하는 상황이 일반적이라면, 수고롭게 매 번 에러를 띄울 필요가 없습니다.

⇒ offer(E e), poll(), peek()은 모두 실패를 가정하는 상황에서 유용하게 쓰입니다.

큐의 장점과 단점

큐의 장점

큐는 대용량의 데이터를 효율적이고 간편히 관리할 수 있습니다.

여러 사용자가 동시에 이용하는 서비스를 관리하기에 유용합니다.

데이터의 순서가 유지되는 작업에서 편리합니다.

순서를 유지해야 하는 다른 데이터 구조를 구현할 때 쓰입니다.

큐의 단점

head나 rear가 아니라 큐의 중간 위치 기준 요소 삽입이나 삭제는 시간이 오래 걸립니다.

크기가 고정되어 있으면 새로운 요소가 삽입될 수 없습니다.

또한, 기본 큐에서 새로운 요소는 기존 요소가 삭제될 때에만 추가될 수 있습니다.

검색 역시 O(N) 시간복잡도를 가집니다.

큐: 어디에 쓰일까?

자바에서 큐 이용하기

import java.util.LinkedList;
import java.util.Queue;

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

큐의 활용

멀티 프로그래밍 / 업무 스케쥴링

여러 프로그램이 메인 메모리에서 돌아갈 때, 큐를 이용할 수 있습니다. 프로세스는 우선 순위에 따라 역시 우선 순위가 다른 여러 큐에 나뉘어집니다.

LRU 캐시(LRU Cache)

LRU 캐시(Least Recently Used Cache)는 메모리가 가득차 있을 때, 최근에 쓰이지 않은 데이터부터 제거합니다. 우선순위 큐나 일반 큐를 LRU 캐시 구현에 이용할 수는 있으나, 효율적이라고는 말 할 수 없습니다. 사실 LRU 캐시에는 이중연결리스트와 해시맵이 일반적으로 쓰입니다.

네트워크