Queue(ArrayDeque) - 자바 코드 뜯어보기

큐는 FIFO 자료구조이다.
처음 넣은 데이터가 처음 반환된다는 것인데,
실생활의 예를 들면, 식당에서 밥을 먹기 위해 줄을 서는것을 볼 수있다.
맨 앞에서면 맨 먼저 입장한다.

Deque는 'Double Ended Queue'의 줄임말로, 기존 Queue의 개념을 확장한 일반화된 형태다.

이 자료구조는 양쪽 끝에서 데이터의 삽입과 삭제가 가능하며, 그래서 Queue와 Stack의 기능을 모두 포함하고 있다.

이로 인해 Deque는 Queue나 Stack보다 더 유연하고 다용도로 사용될 수 있다.

이전에 Stack 자료구조에서 설명했듯이, 양 LIFO,FIFO 를 모두 구현하는 자료구조인데,  원래는 순수 FIFO의 기능을 하는  큐 구현체를 소개하려 했지만, 생각보다 순수하게 FIFO만을 구현하는 구현체가 많이 없고, 스레드 세이프한 자료구조들이 많아 소개하기 복잡할것같아, deque를 FIFO 자료구조 소개 수단으로 채택했고, 그 구현체 중 하나인 ArrayDeque로 

중심으로 설명하고자 한다.

ArrayDeque

이 ArrayDeque에는 사실 스텍과 큐의 메서드 모두가 정의되어있다.

ArrayDeque 인터페이스인 Deque의 문서를 읽어보면, 이에 대해서 다음과 같이 보여준다.

Stack, Queue에서의 메서드와 
Deque에서 동일한 기능을 하는 메서드를 소개한다.

Deque는 Stack, Queue의 메서드를 모두 사용할 수는 있지만, 코드를 뜯어보면 결국 구현로직은 아래처럼 Deque메서드를 사용하기 때문에, Deque의 메서드 중심으로 설명하고자 한다.

 

1. 생성자 

일단 생성자부터 살펴보자

/**  
 * Constructs an empty array deque with an initial capacity * sufficient to hold 16 elements. */
 public ArrayDeque() {  
    elements = new Object[16 + 1];  
}

그런데 주석을 보니, 처음부터 의문이 생긴다.
주석에서는 16개의 요소를 가지고있다고 하는데
왜 실제 구현에서는 크기가 16+1 일까?

이는 순환큐(Circular Queue)와 관련이 있다.
그럼 순환 큐는 큐와 어떻게 다르냐?
큐는 우리가 알고있는 FIFO 자료구조 형식이고,

이런 Queue는 LinkedList, ArrayDeque같이 여러 방식으로 구현이 가능하다.

Queue, Stack, List와 같은 개념적인 자료구조들은 추상 데이터 타입(ADT)으로 분류하는데,
ADT는 데이터와 그 데이터에 적용할 수 있는 연산들을 정의하지만, 
구체적인 구현 방식은 정의하지 않는다.

순환 큐 는 큐라는 자료구조의 구체적인 구현 구조라고 보면 된다.

이 순환 큐는 배열 구조로 구현되는데, 이를 위해  ArrayDeque는 head, tail을 추가적으로 선언한다.

그럼 이제 우리는 순환 큐가 큐의 구현 방식 중 하나 이고, head, tail은 순환 큐를 위한 것을 알았다. 그럼, 순환큐는 왜 이 head, tail이 필요한가? 그리고 이 head, tail은 정확히 무엇을 의미하는가?

삽입과정을 통해 알아보자.

2. 삽입

public void addLast(E e) {  
    if (e == null)  
        throw new NullPointerException();  
    final Object[] es = elements;  
    es[tail] = e;  
    if (head == (tail = inc(tail, es.length)))  
        grow(1);  
}

static final int inc(int i, int modulus) {  
    if (++i >= modulus) i = 0;  
    return i;  
}

ArrayDeque를 처음 생성하고, 첫 값을 넣을 때를 예를 들어보자.

생성자를 보면 최초 생성시 배열의 총 길이는 17이므로 내부에는 17개의 배열을 생성하며, 

실제로는 16개의 배열만 사용한다.
여기서 head,tail은 배열의 가장 앞의 요소 인덱스, 가장 마지막 요소 인덱스를 의미한다.

클레스에서 맴버변수는 자동으로 초기화되므로,
head, tail = 0이 된다.
총 17개의 배열이 있으며, 마지막 따로 표시한 배열은 값을 저장하는데 사용하지 않고, 해당 인덱스가 끝에 도달했는지 여부를 비교할때 사용한다. (빈칸은 모두 null이다.)

그럼 es[0], 즉 첫번째 배열은 "a"가 된다.

이제 head == tail ,즉 배열이 가득 찼는지 판별한다. 동일하다면,
배열이 가득 찼다는 의미이므로, 배열 크기를 늘릴것이고, 아니라면 늘리지 않는다.

inc메서드는 tail 인덱스가 마지막 배열을 넘어서는지 확인하고, 

아니라면 그대로 tail을 반환할것이고,  넘어간다면, tail을 0으로 변경한다.

현 상황에서는 1을 반환하므로 tail = 1이 되고, 
배열이 가득차지 않았으므로, grow는 호출되지 않는다.

grow는 단순하게 이야기하면 배열을 늘려주는 메서드이다.

배열의 크기를 비교해서 작으면 2배 정도를 늘리고,  크다면 원본의 절반의 크기를 늘린다.

이후 늘어난 배열 크기만큼 요소들의 위치를 재정렬한다.

private void grow(int needed) {  
    // overflow-conscious code  
    final int oldCapacity = elements.length;  
    int newCapacity;  
    // Double capacity if small; else grow by 50%  
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);  
    if (jump < needed  
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)  
        newCapacity = newCapacity(needed, jump);  
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);  
    // Exceptionally, here tail == head needs to be disambiguated  
    if (tail < head || (tail == head && es[head] != null)) {  
        // wrap around; slide first leg forward to end of array  
        int newSpace = newCapacity - oldCapacity;  
        System.arraycopy(es, head,  
                         es, head + newSpace,  
                         oldCapacity - head);  
        for (int i = head, to = (head += newSpace); i < to; i++)  
            es[i] = null;  
    }  
}

grow메서드의 로직이 잘 이해가 안된다면 이런 Deque 내부 배열이 있다고 예를 들어보자

 

현재 상황은 ArrayDeque에 1,2,3을 전부 삽입한 경우이다.

여기서 addLast 메서드는 head, tail이 동일하므로 
grow(1) 을 실행한다.

Object[] integer = {1,2,3};

배열의 크기가 3 이므로, newCapacity = 8 이 된다.

현재 head == tail && head != null 이므로, 재정렬을 시행한다.

제거되어야 할 배열을 정리한다.
동시에 head의 값도 맞게 할당한다.

3. 반환

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

public E pollFirst() {  
    final Object[] es;  
    final int h;  
    E e = elementAt(es = elements, h = head);  
    if (e != null) {  
        es[h] = null;  
        head = inc(h, es.length);  
    }  
    return e;  
}

static final <E> E elementAt(Object[] es, int i) {  
    return (E) es[i];  
}

반환은 배열 크기를 정하는 로직은 필요 없으므로 상대적으로 쉬운 구조이다.

해당 배열 요소를 가져오고, null 처리하며, head를 1 증가 시킨 후

배열 요소를 반환한다.

 

 

이러한 ArrayDeque는 싱글스레드에서 사용하도록 구현되었으므로 멀티스레드 환경에서는 사용을 주의해야한다.