기록/JAVA

[JAVA] Queue 인터페이스 구현하기 (3) ArrayDeque

5월._. 2023. 7. 11.

728x90

Queue라는 인터페이스를 구현하는 방식 중 ArrayDeque에 대해서 알아본다. add - offer이 완전히 동일한 것을 제외하면 나머지는 queue 추상메서드의 의도대로 구현되었다.

ArrayDeque

ArrayDeque은 내부적으로 다음의 변수를 사용한다. 이 변수들은 transient를 사용해서 직렬화되지 않는다.

Object[] elements	deque의 요소가 저장되는 배열. 항상 2의 거듭제곱이 배열의 길이가 된다. deque요소를 보유하지 않는 모든 배열 셀은 항상 null이다.
int head	deque의 head 요소의 "인덱스". deque가 비어있는 경우 tail과 같은 임의의 숫자가 저장된다.
int tail	deque의 다음요소가 추가될 "인덱스".
private int MIN_INITIAL_CAPACITY	새로 만들어지는 elements 배열의 최소 크기.

add

맨 끝에 더한다.

public boolean add(E e) {
    addLast(e);
    return true;
}

요소 e가 null이라면 예외를 발생시킨다.

elements[tail]에 새로운 요소를 저장한다.

tail에 (tail+1)&(elements.length-1)을 저장한다. 이 방식은 원형 버퍼에서 인덱스를 계산하는 방식이다. 이 계산방식 때문에 항상 elements의 크기는 항상 2의 제곱수여야 하는 것이다. 배열 길이가 2의 제곱수인 경우, elements.length-1은 모든 비트가 1로 구성된 숫자다. 비트 AND 연산자를 사용해 tail+1을 elements.length-1과 AND연산해 인덱스를 계산한다.

만약 elements.length=8이고 tail이 7이었다면 이런 계산이 된다.

(tail+1)&(elements.length-1) = 8 & 7 = 1000(2) & 0111(2) = 0

새로 저장된 tail=0이 head와 동일하다면 배열 크기를 늘린다.

public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

왜인지 모르겠지만 assert문이 살아있다. head!=tail이면 AssertionError예외가 발생한다.

elements의 끝과 head 인덱스 사이에 몇 개의 요소가 있는지 체크하고 r에 저장한다.

newCapacity는 현재 elements.length를 2배한 값이다.

만약 2배한 값이 오버플로우가 일어나서 int 범위를 벗어나면 newCapacity가 0보다 작아진다. 이때 IllgalStateException을 발생시킨다.

newCapacity크기의 새 배열을 만들어서 elements의 head부터 r개를 새 배열 0번부터 하나씩 저장한다.

elements의 0부터 p(head위치)개를 새 배열 r번부터 하나씩 저장한다.

이렇게 두 번에 걸쳐서 새 배열에 값을 저장한 뒤, elements를 새 배열로 교체한다.

head를 0으로, tail을 n(elements.length)로 저장하고 끝낸다.

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1;
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

offer

offerLast 값을 반환한다.

public boolean offer(E e) {
    return offerLast(e);
}

addLast를 실행시키고 그 결과와 상관없이 true를 반환한다.

여기서 의문인게 두 가지 있다.

1) 큐 인터페이스에서는 offer가 삽입 실패하면 false를 반환하도록 하고 있다.

ArrayDeque의 offer가 삽입 실패할때 예외를 발생시키도록 한다면 add메서드와 다른 게 없는 것 아닌가?

2) 만약 최대 크기의 elements 배열에 마지막 요소를 추가해서 배열이 꽉 찬 상태라고 가정해보자. 그러면 요소는 추가됐지만 크기는 두 배가 되지 못해서 tail==head인 상태일 것이다.

여기서 또 요소 e를 추가시키려고 한다면 ArrayDeque의 addLast 로직 상 먼저 tail위치에 요소를 추가한 다음에 (tail+1)&(elements.length-1)==head 조건문으로 doubleCapacity 메서드를 실행킨다.

그러면 결국 최대 크기를 가진 elements에 요소를 추가하면 이미 있는 요소를 덮어씌우는게 되는 것인가?

아무튼 코드를 뜯어본 결과 ArrayDeque의 offer과 add는 완전히 동일한 동작을 수행하는 것으로 보인다.

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

remove

첫번째 요소를 지우고 반환한다.

public E remove() {
    return removeFirst();
}

x에 pollFirst 값을 저장하고 null이라면 exception, 아니라면 x를 반환한다.

public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

제네릭 형변환 경고를 무시하는 어노테이션(SuppressWarnings)가 사용되었다.

result에 elements[h(=head)]를 저장한다.

만약 result가 null이라면 큐가 비어있는 것이다. null을 반환한다.

elements[h]에 null을 저장하고 head위치를 한 칸 뒤로 옮긴다.

result를 반환한다.

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

poll

remove, poll의 차이는 null을 반환하는지, 예외를 발생시키는지의 차이다. remove는 pollFirst()의 값이 null이면 예외를 발생시켰지만, poll()은 그대로 반환한다.

public E poll() {
    return pollFirst();
}

그 외의 내부 동작은 동일하다.(당연하다 같은 메서드를 쓰니까)

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

element

첫번째 요소를 반환한다.

public E element() {
    return getFirst();
}

result에 head인덱스가 가리키는 값을 저장한다.

null이라면 예외를 발생시키고, 아니라면 result를 반환한다.

public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}

peek