[Java] Queue (By ArrayDeque) 따라 구현해보기

 

---

ArrayDeque 클래스 특징

① 자바 1.6 추가

② 내부적으로 가변길이 배열(Resizable-array)로 데이터 관리, 용량 제한 없음

③ Thread-safe 하지 않음

④ Null element 금지

⑤ Stack 으로 사용할시 Stack 클래스 빠르고, Queue로 사용할 시 LinkedList 클래스보다 빠르다

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

 

 

ArrayDeque를 Queue로 활용하는 경우 아래의 네가지 장점을 생각해 볼 수 있다

① 더 높은 성능 지원 

- 내부적으로 배열을 사용하여 큐를 구현하기 때문에 빠른 접근 시간을 제공한다

- 특히 큐의 양 끝에 요소 추가 및 제거 작업에 있어서는 매우 효율적이다

② 메모리 효율성

- 가변길이 배열을 사용하므로, 메모리 할당 및 해제의 오버헤드가 줄어듦

(LinkedList에서 각 노드가 포인터를 가지고, heap 메모리에 저장되는 것과 비교해보면 될 듯하다)

- 요소가 연속적인 메모리 공간에 저장되므로 캐싱 히트 성능이 향상될 수 있다

③ 간결한 API 

- ArrayDeque는 자바 컬렉션 프레임워크의 일부이고, Queue 인터페이스를 구현하고 있다. 

- 따라서 Queue의 모든 기능과 함께 간결하고 사용하기 쉬운 API를 제공한다

④ 선입선출 (FIFO) 지원 

 

ArrayDeque 클래스 참고하여 Queue 직접 구현해보기

public class MyArrayDeque<E> {

    Object[] elements;

    int head;

    int tail;

    public MyArrayDeque() {
        this.elements = new Object[16]; // default capacity
    }

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

    public void addLast(E e) {
        // ..
    }

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

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

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

    public E pollFirst() {
       // .. 
    }

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

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

        return e;
    }


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

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

    static final int dec(int i, int modulus) {
        if(--i < 0) i = modulus - 1;
        return i;
    }

    public E peek() {
        return elementAt(this.elements, this.head);
    }

    public Object[] toArray() {
        return Arrays.copyOfRange(this.elements, this.head, this.tail, Object[].class);
    }

}

 

 

add(E e) , offer(E e) - 데이터 추가 

- add()나 offer()나 내부적으로 addLast(..) 호출하여 데이터를 추가한다

- 데이터 추가 후 tail 포인트를 +1 증가 시킨다

- 이때 head 와 tail 위치가 같아진 경우 배열의 사이즈 증가시키고, 데이터를 복사시킨다(생략)

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

public void addLast(E e) {
    if(e == null)
        throw new NullPointerException();

    final Object[] es = elements;
    es[tail] = e;
    tail = inc(tail, es.length);

    // head == tail 인 경우, 배열 사이즈 증가 (생략)
}

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

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

 

 

poll() - 데이터 꺼내기

- 내부적으로 pollFirst() 메소드 통해 데이터를 꺼낸다 

- 이때 요소가 null이 아닌 경우 해당 인덱스를 null 처리하고, head 포인터를 +1 증가시킨다

- Queue method로 remove()도 있는데, 동일하게 내부적으로 pollFirst() 호출하여 값을 반환한다

 

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

public E pollFirst() {
    final Object[] es = elements;
    final int h;

    E e = elementAt(es, h = head);
    if(e != null) {
        es[h] = null;
        head = inc(h, es.length); // head 포인터 증가
    }

    return e;
}

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

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

    return e;
}

 

 

테스트 결과

public static void main(String[] args) {
    MyArrayDeque<Integer> queue = new MyArrayDeque<>();
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    System.out.println(queue.peek()); // 1
    System.out.println(Arrays.toString(queue.toArray())); // [1, 2, 3]

    System.out.println(queue.poll()); // 1
    System.out.println(Arrays.toString(queue.toArray())); // [2, 3]
    System.out.println(queue.poll()); // 2
    System.out.println(Arrays.toString(queue.toArray())); // [3]
}