[PS] Stack와 Queue로 ArrayDeque를 사용하는 이유(Stack과 LinkedList가 아니라)

기타 공부/JAVA

SemInDev 2025. 3. 28. 17:25

<코딩테스트 합격자되기 자바편>에서 Queue는 ArrayDeque를 사용할 것을 권장했다.

또한, 자바 백준 해답을 참고하다보면 Stack을 ArrayDeque로 사용하는 경우를 줄곧 보았다.

찾아보니 실제로 Java 진영에서도 이를 권장한다고 한다.

오늘 문득 PS를 하며 얻게 된 이러한 궁금증을 해소해보고자 했다.

1. PS에서 Stack 대신 ArrayDeque를 권장하는 이유: 불필요한 동기화

Stack 클래스는 Vector를 상속하여 구현된 클래스로,

동기화가 필요하지 않은 상황(단일 스레드 환경인 PS)에서 불필요한 오버헤드가 발생할 수 있다.

이와 달리 ArrayDeque는 불필요한 오버헤드가 발생하지 않는다.

Vector 클래스는 동기화(synchronized)된 클래스로 멀티스레드 환경에서 안전하게 사용될 수 있도록 설계되었다.

동기화란, 여러 스레드가 동시에 접근할 때 발생할 수 있는 문제를 예방하기위한 설계이다.

특정 코드 블록이나 메서드가 한 번에 하나의 스레드만 접근할 수 있도록 하는 메커니즘이다.

(뮤텍스락, 세마포어와 비슷한 개념을 자바에서 구현하여 동기화 문제를 해결한 것)

하지만 PS는 (대부분) 단일 스레드 환경이다.

단일 스레드 환경에서 Stack을 사용한다면, 모든 메서드 호출이 동기화 메커니즘을 거치기때문에 오버헤드가 발생한다.

따라서, (멀티스레드 환경과 같은)일반적인 경우에는 Vector 기반이라는 사실이 Stack의 장점이지만,

단일 스레드 환경의 PS에서는 오히려 불필요한 오버헤드만 발생한다는 단점이 된다.

멀티스레드 환경에서 안전성을 위해 동기화 기능을 구현한 Vector를 상속받은 Stack 구조는

단일 스레드 환경에서 오히려 오버헤드가 발생해서 ArrayDeque를 사용하는 것이 더 좋다

ArrayDeque는 Queue의 서브인터페이스인 Deque의 구현체이고,

LinkedList는 List와 Queue의 구현체이다.

따라서 LinkedList는 List의 특징을 가지고 있고, ArrayDeque은 배열의 특성을 가지고 있다고 할 수 있다.

ArrayDeque은 양끝 삽입/삭제 연산의 시간 복잡도가 O(1)이고

배열의 특징인 Random access를 사용하여 원소 조회 속도가 빠르다.

반면, LinkedList도 삽입/삭제 연산 성능이 좋지만

List의 특징인 순차적 접근을 사용하여 원소 조회 속도가 ArrayDeque에 비해 느리다.

또한 ArrayDeque는

LinkedList에 비해 cache-locality에 더 친숙하여 연산 속도가 더 빠르고,

LinkedList와 달리, 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.

출처