Java 컬렉션 정리 for 코딩테스트

글쓰기에 앞서 해당 포스팅은 기본적인 Queue의 작동 원리에 대해 아주 짧게만 다룬다. Queue, Stack 과 같은 개념은 알고 있다는 가정하에 포스팅을 진행한다.

1. Queue란?

FIFO (First In First Out) 의 구조를 가진 자료구조. 선입선출을 생각하자.

그림을 통해 쉽게 이해해보자.

배열 안에 값이 저장되는 모습이다.

위의 상태에서 1을 삭제하고, 추가로 5,6을 삽입하면 어떻게 될까?

아래와 같은 모습이 된다.

마찬가지로 2, 3, 4 를 지우고, 7, 8, 9 를 삽입한다면 해당 배열의 앞 부분의 메모리가 낭비가 된다.

이는 Queue의 명확한 한계점이다.

자바에서는 해당 문제를 개선한 ArrayDeque, LinkedList를 구현체로 사용한다.

[ Queue의 구조 ]

이 외에도 정말 많은 구현체가 있다. ex) ArrayBlockingQueue, DeplayQueue 등등...

해당 포스팅은 코딩테스트를 위한 java의 자료구조와 Collection을 이해하는것이 목적이므로,

위의 그림에 적힌 ArrayDeque, PrioirtyQueue에 대해서만 다룬다.

2. Deque

ArrayDeque를 알기 위해선 우선 Deque를 이해해야 한다.

덱은 Queue 뿐만 아니라 Stack 또한 지원해준다. 즉 push(), pop() 메서드 사용 가능하다.

Stack은 내부적으로 Vector라는 래거시 자료구조이기에, Stack을 사용하려면 Stack 대신에 Deque로 구현하자.

덱은 양방향으로 삽입, 삭제가 가능하다. 아래 그림과 같은 모습이다.

코드를 통해서 이해해보자.

Deque<Integer> dq = new ArrayDeque<>();
dq.offer(1);
dq.offer(2);
System.out.println(dq);
// 결과값
[1, 2]

해당 코드는 일반적인 Queue와 동일하다.

다음 예시를 살펴보자.

Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(1);
dq.offerFirst(2);
System.out.println(dq);
// 결과값
[2, 1]

offerFirst()의 경우 해당 배열의 맨 앞 부분에 삽입하기 때문에 결과값이 [2, 1] 로 나오는 것을 확인할 수 있다.

다음 예시를 살펴보자.

Deque<Integer> dq = new ArrayDeque<>();
dq.offerFirst(1);
dq.offerFirst(2);
dq.offerLast(3);
dq.offerLast(4);
System.out.println(dq);
// 결과값
[2, 1, 3, 4]

이해가 잘 되지 않는다면 해당 그림을 참고하자.

마지막으로 Deque를 간단하게 정리하자면

Queue, Stack을 사용할 수 있는 자료구조
Queue와 달리 양방향으로 삽입, 삭제가 가능한 자료구조

로 이해하면 좋을 것 같다.

3. [ ArrayDeque ]

Deque의 구현체 중 하나다.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

자바에서 ArrayDeque는 원형 큐(Circular Queue)를 사용한다.

원형 큐는 뭘까?

1번 (Queue)에서 설명하다시피 Queue는 메모리 낭비라는 단점이 존재한다.

이 단점을 개선하기 위해 원형 큐를 사용한다.

예시를 통해 원형 큐를 이해해보자.

1, 2, 3, 4를 차례대로 삽입했을때 원형큐의 모습이다. 여기까지는 이해하는 데 어려움이 없을 거라 생각한다.

이제 1,2,3 삭제 후 5,6,7을 삽입해보자.

마지막으로 4,5 삭제, 8,9 삽입을 해보자.

위와 같은 식으로 계속해서 front, rear을 추적하면서 빙글빙글 돌아가는 모습을 볼 수 있다.

정적 메모리를 사용하기에 메모리 낭비 또한 없다.

위의 설명을 보면서 아, 원형큐가 이런 것이구나. 이해를 했지만 한 가지 의문점이 들었을 것이다.

front와 rear 추적은 어떻게 하는걸까?

새 위치 = (현재 위치 + 1 ) % 배열 크기

해당 배열에서 5를 삽입한다고 해보자.

삽입이기에 rear의 새 위치 = (3 + 1) % 8 = 4가 된다.

반대로 poll을 통해 맨 앞 원소를 삭제했을 경우,

(0+1) % 8 = 1이 된다.

해당 배열에서 8, 9 를 삽입한다고 해보자.

8의 자리는

(6+1) % 8 = 7

(7+1) % 8 = 0

이런식으로 계속 빙글빙글 돌아간다.

만약 원형큐가 꽉찬다면 어떻게 하면 좋을까?

위와 같은 그림을 원형큐가 가득찼다고 표현한다. index 7 남아있는거 아닌가요? 할 수 있는데

원형큐에서는 한 칸 비워둔다. 왜 그럴까?

기본적으로 front == rear 일 경우 배열이 비어있다고 판단한다. 만약 rear가 index7까지 사용한다면,

(7+1) % 8 = 0 이므로 front == rear가 되어버린다.

즉, 큐가 꽉 찬 상태도 front == rear이고, 큐가 비어있는 상태도 front == rear 이기 때문에 두 상태를 구분할 방법이 없기에

한 칸을 비워놓는다.

예시를 하나 더 보자

해당 배열에 index 2에 또 값을 넣는다고 가정해보자.

(10 + 1 ) % 8 = 3 , 즉 rear=3의 값이 나오고 front 또한 3의 값이 나온다.

원형큐에서 front == rear는 empty를 의미하는데 이러면 구분할 수가 없어 한 칸을 비워놓는다는걸 다시 한 번 설명하고,

해당 예시를 통해 이해했으면 좋겠다.

[ 원형큐의 한계 및 Java의 ArrayDeque ]

원형큐의 한계점은 뭘까? 위의 그림에서 바로 파악할 수 있다시피 정적 배열이다.

배열의크기가 10이라면, 9개 값 삽입을 하면 이후에는 overflow가 발생한다.

자바의 ArrayDeque는 정적으로 배열을 생성해 해당 문제를 해결한다.

public ArrayDeque() {
    elements = new Object[16 + 1];
}

public ArrayDeque(int numElements) {
    elements =
        new Object[(numElements < 1) ? 1 :
                   (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                   numElements + 1];
}

ArrayDeque의 내부 코드다.

기본생성자로 크기 17의 배열이 할당되는걸 알 수 있고, 매개변수를 받는다면 해당 크기의 배열을 생성한다.

만약 17의 배열을 초과할 경우, 배열 크기를 조정해 추가로 값을 저장할 수 있다.

정리하자면, Java의 ArrayDeque는 원형큐를 사용하되, 동적으로 배열 크기를 조정하는 자료구조임을 알 수 있다.

다만, 이미 늘어난 크기는 자동으로 조절이 안 되는것으로 파악했다. 만약 크기 조정을 하고싶다면 새로운 ArrayDeque를 만들어 값 복사를 해보자.

3. Deque의 메서드

Deque의 메서드보다는, queue의 메서드가 올바른 표현인 것 같다.

필자는 queue에 삽입을 할 때 offer() 메서드를 주로 사용하는데, add() 메서드도 존재하더라.

그래서 비슷한 메서드를 정리해보려고 한다.

[ 삽입 메서드 비교 ]

add : 메서드 실패시 예외를 던진다.

offer() : 메서드 실패시 false를 반환한다.

코드를 통해 확인해보자.

public static void main(String[] args) {
    Queue<Integer> q = new ArrayBlockingQueue<>(3);
    System.out.println(q.add(1));
    System.out.println(q.add(2));
    System.out.println(q.add(3));
    System.out.println(q.add(4));
}
// 결과값
true
true
true
Exception in thread "main" java.lang.IllegalStateException: Queue full

public static void main(String[] args) {
    Queue<Integer> q = new ArrayBlockingQueue<>(3);
    System.out.println(q.offer(1));
    System.out.println(q.offer(2));
    System.out.println(q.offer(3));
    System.out.println(q.offer(4));
}
// 결과값
true
true
true
false

출력문을 찍어야 false가 나오기 때문에, 에러 체킹을 하기 위해서는 add보다 offer()를 사용하는게 더 좋아보인다.

[ 삭제 메서드 비교 ]

remove : 배열이 비어있으면 예외를 발생시킨다.

poll : 배열이 비어있으면 null을 반환한다.

삽입 메서드와 동일하다. null 반환 음... 상황에 맞게 메서드를 사용해야 하지 않을까

[ 큐의 첫 번째 요소 조회 비교 ]

element: 큐가 비어있다면 예외를 발생시킨다.

peek : 큐가 비어있다면 null을 반환한다.

이하동문

4. ArrayDeque vs LinkedList

Deque의 구현체는 2개다. ArrayDeque, LinkedList

이 둘의 차이점은 ArrayList, LinkedList의 차이점과 비슷하다.

ArrayDeque, LinkedList 전부 앞 뒤 입력 모두 O(1)의 성능을 제공한다.

이론적으로는 LinkedList가 삽입 삭제가 자주 발생할 때 더 효율적일 수 있지만, 인프런의 김영한 선생님의 강의에 따르면

CPU 캐시 최적화, 메모리 접근 패턴 등을 고려하면 ArrayDeque가 더 나은 성능을 보여준다고 한다.

속도가 중요할 땐 ArrayDeque를, 메모리 낭비가 싫다면 LinkedList를 사용하면 좋을 것 같다는

개인적인 결론을 내렸다.

이 부분에 대해 자세히 알고싶으면, 아래의 글을 참고해보자.

https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/

5. PriorityQueue

우선순위 큐다. PriorityQueue는 Deque의 구현체가 아닌, Queue의 구현체이다.

PriorityQueue는 우선순위가 높은 원소들을 삽입과 동시에 정렬한다. 즉, Heap 구조를 가지고 있고,

min-heap, max-heap 을 선택할 수 있는데, 기본적으로 최솟값인 min-heap으로 구성되어 있다.

코드를 통해 알아보자.

public static void main(String[] args) {
    Queue<Integer> q = new PriorityQueue<>();
    q.offer(10);
    q.offer(5);
    q.offer(3);
    q.offer(9);
    q.offer(6);

    for (int i=0; i< 5; i ++) {
        System.out.println(q.poll());
    }
}
// 결과값
3
5
6
9
10

숫자가 낮은 값, 즉 우선순위가 낮은 값이 큐의 상단에 위치하는걸 알 수 있다.

public static void main(String[] args) {
    Queue<Integer> q = new PriorityQueue<>();
    q.offer(10);
    q.offer(5);
    q.offer(3);
    q.offer(9);
    q.offer(6);

    System.out.println(q);
}
// 결과값
[3, 6, 5, 10, 9]

출력을 했을 때는 아래와 같이 결과값이 나온다.

이제, min-heap이 어떻게 큐에 저장되는지 그림을 통해 이해해보자.

10, 5, 3, 9 6 을 순서대로 ProrityQueue에 삽입했을 때의 진행과정이다.

최소힙은 루트 노드가 가장 작은 값이고,

자식이 부모보다 값이 작다면 부모와의 위치를 바꿔주면 된다.

글을 통해 이해하는 것 보다는, 상단의 사진으로 이해하는게 훨씬 편할것이라고 생각한다.

최대힙은 최소힙의 반대다.

루트노드가 가장 큰 값이고, 자식이 부모보다 값이 크다면, 부모와의 위치를 바꿔주면 된다.

Java의 ProirotyQueue는 기본적으로 최소힙으로 구현되어 있기에, 최대힙을 사용하고 싶다면,

Queue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());

다음과 같이 구현체를 만들자.

최솟값/최댓값을 찾는 과정은 O(1) 시간복잡도를 가지지만,

힙 구조를 사용하기에 삽입과 삭제는 O(logN) 시간복잡도를 가진다.

삽입과 동시에 최솟값/최댓값을 찾거나, 우선순위로 값을 구해야 한다면 PriorityQueue를 적극 활용해보자.

저작자표시 비영리 동일조건 (새창열림)

'java' 카테고리의 다른 글

Thread(2) - 스레드의 상태 (6)	2025.01.15
Thread(1) - java의 메모리 구조, 프로세스의 메모리 구조 (4)	2025.01.14
Java 컬렉션 정리 for 코딩테스트 - Map (7)	2024.12.23
Java 컬렉션 정리 for 코딩테스트 - Set (1)	2024.12.22
Java 컬렉션 정리 for 코딩테스트 - List (5)	2024.12.21

성우의 기록

Java 컬렉션 정리 for 코딩테스트 - Queue

1. Queue란?

이는 Queue의 명확한 한계점이다.

[ Queue의 구조 ]

2. Deque

3. [ ArrayDeque ]

새 위치 = (현재 위치 + 1 ) % 배열 크기

[ 원형큐의 한계 및 Java의 ArrayDeque ]

3. Deque의 메서드

[ 삭제 메서드 비교 ]

[ 큐의 첫 번째 요소 조회 비교 ]

4. ArrayDeque vs LinkedList

5. PriorityQueue

'java' 카테고리의 다른 글

티스토리툴바

Java 컬렉션 정리 for 코딩테스트 - Queue

1. Queue란?

이는 Queue의 명확한 한계점이다.

[ Queue의 구조 ]

2. Deque

3. [ ArrayDeque ]

새 위치 = (현재 위치 + 1 ) % 배열 크기

[ 원형큐의 한계 및 Java의 ArrayDeque ]

3. Deque의 메서드

[ 삭제 메서드 비교 ]

[ 큐의 첫 번째 요소 조회 비교 ]

4. ArrayDeque vs LinkedList

5. PriorityQueue

'java' 카테고리의 다른 글

관련글

티스토리툴바