[Java] ArrayDeque 가 Stack 보다 좋은 이유

hoonssac·2025년 4월 18일

ArrayDeque Java algorithm coding test stack

Java

목록 보기

8/8

🧐 발단

평소에 자바로 코테 문제를 풀면서 스택을 종종 사용해 왔습니다.
"스택 자료구조를 쓸 거니까, Stack 이라는 클래스를 이용해야지~"라는 생각과 함께 말이죠.
그런데, 오늘 알고리즘 강의를 듣다가 Stack 클래스 대신 ArrayDeque를 쓰는 게 성능적으로 더 좋다는 정보를 얻었습니다.
ArrayDeque라.. 예전, 자료구조 시간에 배웠던 기억 속에는 그저 "앞뒤로 삽입/삭제가 가능한 자료구조"로 남아있었습니다. 그런데, 이 ArrayDeque를 Stack 대신에 사용하는 게 보편적이고, 심지어 성능까지 더 좋다는 말에 호기심 버튼이 눌렸습니다.

그래서 오늘은 ArrayDeque와 Stack에 대해, 그리고 둘의 성능에 대해 한 번 알아보겠습니다.

💩 Stack은 구리다

ArrayDeque를 알아보기 전에, Stack이 왜 안좋은지 한 번 파해쳐보겠습니다.
Java의 Stack에 대한 문서에는 이런 구절이 존재합니다.

The Stack class represents a last-in-first-out (LIFO) stack of objects.
It extends class Vector with five operations that allow a vector to be treated as a stack.

여기에서 알 수 있는 점은, Stack은 Vector를 상속하고 있다는 것입니다.
그렇다면, Vector에 대해 알아봐야겠죠?

🔐 Vector

Vector는 멀티스레드 환경에서의 안전을 보장하기 위해 설계된 클래스입니다.
이 녀석의 가장 큰 특징은 "모든 메소드가 synchronized 처리되어 있다"는 점입니다.

그래서 모든 메소드(add(), remove(), get(), set(), 심지어 size()까지)에서 메소드를 시작할 때마다 잠금을 걸죠.
예를 들어, add(E e)의 메소드 내부를 보면, synchronized 키워드가 걸려 있는 걸 볼 수 있습니다.

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityInternal(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

그럼 이런 의문이 듭니다.

" 아니, 동기화를 진행하니까 멀티스레드 환경에서 안전하고 좋은 거 아님? 🤔 "

맞습니다. 스레드 간 데이터 충돌을 막는데는 효과가 있죠.
하지만, 그 효과를 보기 위해서는 여러 메소드를 호출 하는 과정을 거칩니다.
그리고, 그 과정에서 lock을 획득하고 해제하는 비용이 발생하죠.

중요한 점은, 그 비용이 우리가 주로 Stack을 사용하는 싱글스레드 환경에서도 똑같이 발생한다는 점입니다.

즉, 혼자 Stack을 쓰는데도

push 하나 할 때마다 -> lock 획득 -> 배열에 넣기 -> lock 해제

pop 하나 할 떄마다 -> lock 획득 -> 배열에서 꺼내기 -> lock 해제

이런 식으로 불필요한 비용이 발생한다는 것입니다.

👾 ArrayDeque와 실행 시간 비교

반면에, ArrayDeque는 그런 과정도 비용도 발생하지 않습니다.
그래서 직접 싱글스레드 환경에서 이 둘의 실행 시간을 한 번 비교해봤습니다.

public class UseVector {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        Instant startStack = Instant.now();
        for (int i = 0; i < 100_000_000; i++) {
            stack.push(i);
        }
        Instant finishStack = Instant.now();
        System.out.println("Stack 걸린 시간: " + Duration.between(startStack, finishStack).toMillis() + "ms");

        Instant startDeque = Instant.now();
        for (int i = 0; i < 100_000_000; i++) {
            deque.push(i);
        }
        Instant finishDeque = Instant.now();
        System.out.println("ArrayDeque 걸린 시간: " + Duration.between(startDeque, finishDeque).toMillis() + "ms");
    }
}