[Java 파헤쳐보기] Stack 대신 ArrayDeque를 써야하는 이유

 

ArrayDeque (Java Platform SE 8 )

 

java 공식 문서에서 ArrayDeque를 보면, 아래와 같은 문구를 확인할 수 있습니다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

 

ArrayDeque는 stack으로 사용될 때는 Stack보다 빠르고, queue로 쓸 때는 LinkedList 보다 빠르다.

 

 

지난 포스팅에서 LinkedList와의 비교를 통해 LinkedList보다 빠른 것을 확인했습니다. 그럼 Stack은 어떻게 구현이 되어있길래, ArrayDeque보다 느린지 확인해보고 싶어졌습니다.

 

 

JCF에서의 Stack

public
class Stack<E> extends Vector<E> {

    public Stack() {
    }

 

JCF에서 Stack이 어떻게 구현되어있는지를 살펴보면 Vector 클래스를 상속받는 것을 볼 수 있습니다.

 

 

그런데 LIFO 구조를 만들때에는, 사실 Vector 구조가 적합하지는 않습니다. 왜냐하면 Vector는 ArrayList와 기능적으로 거의 동일하고 배열의 형태로 구현을 하는데, LIFO와는 다소 맞지 않기 때문입니다.

 

 구글링을 해보니, Stack 클래스가 자바 초기 버전부터 존재하다 보니 자바에서 잘못 상속을 한 경우라고 합니다.

 

 

 우선 Stack의 메서드를 통해 구현이 어떻게 되어있는지부터 살펴보았습니다.

 

stack.push()

//Stack.java
public E push(E item) {
    addElement(item);

    return item;
}

//Vector.java
public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

 

Stack의 기본 메서드인 push() 메서드를 확인해보면 내부의 addElement가 Vector에서 구현된 것을 볼 수 있습니다. 그리고 입력 값은 배열의 형태로 저장되는 것을 볼 수 있습니다.

 

 그리고 Vector의 문제점은 이전 포스팅에서 다루었습니다. 완벽하지 않은 동기화와, 동기화로 인한 성능 저하로 Vector 사용을 지양해야한다는 내용입니다.

 

Stack의 단점

그래서 Stack 클래스도 Vector 클래스를 상속하기 때문에 생기는 문제를 짚어보면 아래와 같습니다.

 

1.  동기화로 인한 성능 저하가 나타난다.

 

2. Vector 클래스를 상속받았기 때문에, LIFO 구조를 유지하는 것이 아닌 중간에서 데이터를 삽입하고 삭제할 수 있다.

 

3. 초기 용량을 설정할 수 없다. (Vector의 초기 용량 10을 그대로 사용)

초기 용량을 설정할 수 없다면, 요소를 추가할 때마다 내부 배열의 크기를 동적으로 조정해야하는데, 이는 추가적인 메모리 할당과 복사 작업이 필요하기 때문에 성능에 영향을 줄 수 있습니다.

 

이러한 단점을 보완하기 위해 ArrayDeque를 사용하는 것이 권장됩니다. 

 

 

ArrayDeque

ArrayDeque에 대한 내용은 이전 포스팅에서 다루었습니다.

 

ArrayDeque는 불필요한 동기화 없이 offerLast 메서드와 pollLast 메서드로 Stack의 기능을 완벽히 대체할 수 있습니다.

 

 

하지만 ArrayDeque는 스레드 안전하지 않다는 단점이 있습니다. 그래서 멀티 스레드 환경에서 사용하기 위해 아래와 같이 데코레이팅을 통해 ArrayDeque를 만들 수 있습니다.

public class DequeBasedSynchronizedStack<T> {

    private ArrayDeque<T> dequeStore;

    public DequeBasedSynchronizedStack(int initialCapacity) {
        this.dequeStore = new ArrayDeque<>(initialCapacity);
    }

    public DequeBasedSynchronizedStack() {
        dequeStore = new ArrayDeque<>();
    }

    public synchronized T pop() {
        return this.dequeStore.pop();
    }

    public synchronized void push(T element) {
        this.dequeStore.push(element);
    }

    public synchronized T peek() {
        return this.dequeStore.peek();
    }

    public synchronized int size() {
        return this.dequeStore.size();
    }
}

 

 

 

 

 

참고자료

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html

https://devlog-wjdrbs96.tistory.com/245

https://jaehee329.tistory.com/27