Stack을 만들 때는 ArrayDeque으로?

Java 표준 라이브러리에는 Stack<E>라는 스택 클래스가 있지만, 단일 스레드 환경에서는 ArrayDeque<E>를 스택 용도로 사용하는 것이 훨씬 효율적입니다. 이유를 네 가지로 정리했습니다.

---

1. 불필요한 동기화 오버헤드 제거

• Stack(Vector 기반)
  • Stack은 내부적으로 java.util.Vector를 상속받아 구현되어 있습니다.
  • Vector의 주요 메서드(add(), remove(), push(), pop() 등)는 모두처럼 synchronized 키워드를 붙여 두었습니다.
  • synchronized 메서드가 호출될 때마다 JVM은
    1. 객체의 모니터 락을 획득(lock)
    2. 실제 작업 실행
    3. 모니터 락을 해제(unlock)
       과정을 거칩니다.
  • 단일 스레드 환경이라도 락 획득·해제 비용이 매번 발생해,
    수십만 번 호출되는 알고리즘 코드에서는 눈에 띄는 성능 저하를 초래합니다.
• ArrayDeque
  • ArrayDeque는 비동기(non-synchronized) 구현체라, 락 관련 검사를 전혀 하지 않습니다.
  • 따라서 락 획득⋅해제 비용 없이 순수하게 배열 인덱스 연산만으로 빠르게 동작합니다.

// 불필요한 락 오버헤드 발생 (Vector 기반)
Stack<Integer> stack = new Stack<>();
stack.push(1);  // synchronized → lock 획득/해제
stack.pop();    // synchronized → lock 획득/해제

// 락 없이 가볍게 동작 (ArrayDeque)
Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);  // addFirst(1)
deque.pop();    // removeFirst()

---

2. 명확한 인터페이스 설계 & 유연성

• Stack
  • 오로지 스택 동작만 지원
  • 상속 구조(Vector→Stack)가 레거시 느낌
• Deque 인터페이스
  • ArrayDeque는 Deque<E>를 구현
  • 스택(push/pop), 큐(offer/poll), 덱 양방향 모두 하나의 구현체로 지원
  • 필요에 따라 스택 ↔ 큐 전환이 간편합니다

Deque<Integer> dq = new ArrayDeque<>();
// 스택처럼
dq.push(10);
dq.push(20);
System.out.println(dq.pop());    // 20

// 큐처럼
dq.offerLast(30);
dq.offerLast(40);
System.out.println(dq.pollFirst());  // 10

---

3. 메모리 & 성능 최적화

• Stack
  • Vector의 동기화 블록, 버퍼 확장 전략 등이 추가 메모리·CPU 오버헤드를 유발
• ArrayDeque
  • 내부 순수 배열 및 원형 버퍼 구조로 메모리·GC 부담 최소화
  • 락이나 불필요한 참조 없이 가볍게 동작

---

4. Java 공식 권장 사항

Oracle 공식 JavaDoc에도

“This interface should be used in preference to the legacy Stack class.”
라고 명시되어 있습니다.
(Deque JavaDoc 중)

---

결론

• 단일 스레드 환경에서 스택이 필요하다면, Stack 대신 ArrayDeque<E> 를 사용하는 것이 좋다!