자료구조 : Queue

이번 포스팅에선 스택의 오랜 친구인 Queue (이하 큐)에 대해서 알아보는 시간을 가져보겠습니다. 

 

우선 이번 포스팅에서는 큐에 대한 개념과 핵심 메서드에 대해서 알아보고, 그 이후에는 자바에서 제공하고 있는 구현체에 대해서 알아보고 마지막으로 큐가 thread-safe한지에 대해서 알아보겠습니다. 

 

 

Queue

자바에서 큐는 일반적인 도로와 같은 느낌입니다. 제일 먼저 들어온 것이 제일 먼저 나가는 구조이지요. 이것을 FIFO (First In First Out)라고 부릅니다. 

 

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95

큐의 일반적인 느낌은 위와 같습니다. 

 

핵심 메서드

큐는 인터페이스인데요. 큐를 구현하는 모든 구현체들은 아래의 세가지 핵심 메서드를 포함해야합니다. 

 

• offer() : 큐의 뒤쪽에 새로운 값을 삽입합니다.
• poll() : 큐의 앞쪽에 값을 삭제합니다. 그리고 반환합니다.
• peek() : 큐의 맨 앞에있는 값을 반환하고 삭제하지는 않습니다. 

 

 

핵심 자식 인터페이스

일반적으로 큐 인터페이스는 3개의 자식 인터페이스를 가지고 있습니다. Blocking Queue, Transfer Queue, Deque

 

각각 하나씩 살펴보도록 하겠습니다. 

 

Blocking Queues

Blocking Queue 인터페이스는 큐안에서 스레드가 기다립니다. 스레드는 큐안에서 검색을 시도할 때나, 전부 비어있게 될 때나, 새로운 요소를 추가할때까지 기다립니다. 

 

Blocking Queue는 java.util.concurrent에 소속된 인터페이스이기 때문에 멀티스레드 환경에서 사용하기 아주 적합합니다. 

 

Blocking Queue의 구현체로는 LinkedBlockingQueue, SynchronousQueue, ArrayBlockingQueue 가 있습니다. 

 

 

Transfer Queues

Transfer Queue는 Blocking Queue 인터페이스를 상속한 인터페이스입니다. 기본적으로는 Blocking Queue와 같지만 producer-consumer의 패턴을 추가적으로 가지고 있습니다. 

 

여기서 producer-consumer 패턴이란 작업 목록을 가운데 두고, 작업을 생산해내는 주체와 작업을 처리하는 주체를 분리시키는 설계방법입니다. 작업을 생산하는 부분(producer)과 처리하는 부분(consumer)이 각각 감당할 수 있는 부하를 조절할 수 있다는 장점이 있습니다. 

 

producer는 어떤 consumer가 몇 개나 동작하고 있는지에 대해 전혀 신경 쓰지 않을 수 있습니다. 단지 새로운 작업 내용을 만들어 큐에 쌓아두기만 하면 됩니다. 반대로 consumer역시 producer에 대해서 뭔가 알고 있어야 할 필요가 없습니다. 

 

https://coding-food-court.tistory.com/81

 

이러한 관계는 느슨한 결합도를 가지기 때문에 좀 더 객체지향스러운 것 같습니다. 

 

 

Deques

위의 두개와 비교했을 때 가장 중요한 인터페이스입니다. Deque란 Double-Ended-Queue의 약자로 카드의 덱으로 비유됩니다. 데크에서는 앞쪽과 뒤쪽 모두 값이 들어갔다 나올 수 있습니다. 

 

즉, 하나의 공간에서 상황에따라 스택처럼 쓸 수도, 큐처럼 쓸 수도 있다는 것입니다. 하지만 성질은 큐쪽에 좀 더 가깝습니다. 

 

자바에서 데크는 인터페이스로 구현되어 있습니다. 데크 자료구조의 여러 연산들을 정의한 데크 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등이 있습니다. 

 

 

Deque에서의 데이터 삽입

• addFirst() : 데크의 앞쪽 element를 삽입합니다. 용량 제한이 있는 데크인 경우 용량을 초과하면 예외가 발생합니다.
• offerFirst() : 데크 앞쪽에 element를 삽입합니다. 정상적으로 element가 삽입되면 true가 리턴되며 용량 제한에 걸리는 경우 false를 리턴합니다. 
• addLast() : 데크의 마지막 쪽에 element를 삽입합니다.용량 제한이 있는 경우 용량 초과시 예외가 발생합니다.
• add() : addLast()와 동일
• offerLast() : 데크의 마지막 쪽에 element를 삽입합니다. 정상적으로 삽입된 경우 true가 리턴괴며, 용량 제한에 걸리는 경우 false를 리턴합니다. 

 

Deque의 데이터 삭제

• removeFirst() : 데크의 앞쪽에서 element를 하나 뽑아서 제거한 다음 해당 element를 리턴한다. 데크가 비어있으면 예외를 발생한다. 
• pollFirst() : 데크의 앞쪽에서 element를 하나 뽑아서 해당 element를 리턴한다. 데크가 비어있으면 null이 리턴된다. 
• removeLast() : 데크의 마지막 쪽에서 element를 하나 뽑아서 제거한 다음 해당 element를 리턴한다. 데크가 비어있으면 예외가 발생한다.
• pollLast() : 데크의 마지막 쪽에서 element를 하나 뽑아서 제거한 다음 해당 element를 리턴한다. 데크가 비어있으면 null을 반환한다. 
• remove() : removeFirst()와 동일
• poll() : pollFirst()와 동일

 

Deque의 데이터 탐색

• getFirst() : 데크의 앞쪽 element를 하나 제거하지 않은 채 리턴한다. 데크가 비어있으면 예외가 발생한다.
• peekFirst() : 데크의 앞쪽 element를 하나 제거하지 않은 채 리턴한다. 데크가 비어있으면 null이 리턴된다.
• getLast() : 데크의 마지막쪽 element를 하나 제거하지 않은 채 리턴한다. 데크가 비어있으면 예외가 발생한다.
• peelLast() : 데크의 마지막 element를 하나 제거하지 않은 채 리턴한다. 데크가 비어있으면 null이 리턴된다.
• peek() : peekFirst()와 동일

 

Deque의 데이터 가공

• removeFirstOccurrence(Object o) : 데크의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 element를 제거한다. Object o와 같은 element가 없으면 데크에 변경이 발생하지 않는다.
• removeLastOccurrence(Object o) : 데크의 뒤쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 element를 제거한다. Object o와 같은 element가 없으면 데크에 변경이 발생하지 않는다. 
• addAll(Collection <? extends E>) : 입력 받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다.
• push() : addFirst()와 동일, 데크를 스택으로 사용할 때 쓰임
• pop() : removeFirst()와 동일, 데크를 스택으로 사용할 때 쓰임

 

큐에서의 정렬

우리는 앞서 자바에서 FIFO원리를 따르는 큐에 대해서 알아봤는데 이 클래스는 예외가 있습니다. 바로 Priority Queues인데요. Priority Queue로 선언된 큐에서는 삽입되는 element들이 자연적인 순서에 맞게 정렬됩니다. 

 

PriorityQueue<Integer> integerQueue = new PriorityQueue<>();

integerQueue.add(9);
integerQueue.add(2);
integerQueue.add(4);

int first = integerQueue.poll();
int second = integerQueue.poll();
int third = integerQueue.poll();

assertEquals(2, first);
assertEquals(4, second);
assertEquals(9, third);

 

 

Thread-safe 여부

큐는 특히 멀티스레드 환경에서 사용하기 적합합니다. 큐는 스레드들 사이에서 공유되기 때문에 큐 안에서의 공간이 사용가능할 때까지 lock으로 잠궈집니다. 따라서 흔히 일어나는 멀티스레드 환경에서의 문제를 완벽히 해결할 수 있습니다. 

 

큐에 값을 삽입할 때에는 오직 하나의 스레드만이 큐에 접근할 수 있습니다. 이런식으로 하나의 스레드만 큐에 값을 적을 수 있는 상황은 멀티스레드에서의 문제를 해결해주고 쓰기속도도 엄청난 향상을 불러일으키죠. 

 

 

 

자 여기까지 큐에 대해서 알아봤습니다. 우리는 먼저 큐가 뭔지 알아봤고, 자바에서 제공하는 구현체에 대해서 알아봤었죠. 그리고 보통의 FIFO방식과 다른 형태의 큐인 Priority Queue에 대해서 알아봤습니다. 마지막으로 thread-safe 여부까지 확인했죠. 

 

큐는 생각보다 많이 사용되는 인터페이스인가 싶었습니다. 스택에 비해 구현체의 양도 다양하고 멀티스레드 환경에서 고려해야하는 점들도 다 대비가 되어있었으니까요. 

 

그래도 크게 어렵지 않게 이해하고 정리할 수 있었던 것 같습니다. 

 

오늘도 긴 글 읽어주셔서 감사합니다. 즐거운 하루 되세요~

 

 

출처

https://www.baeldung.com/java-queue

=> Queue 공식 문서

https://soft.plusblog.co.kr/24

[Java(자바)] Deque(덱/데크) 자료구조

https://coding-food-court.tistory.com/81

생산자(Producer) 소비자(Consumer) 패턴