스택 구현시, ArrayDeque을 사용해야 하는 이유
결론
LIFO(후입선출) 자료구조를 사용하고자 한다면, Stack 클래스를 사용하기보다는 ArrayDeque, Linked Blocking Deque, Concurrent Linked Deque을 사용하는 것이 거의 모든 면에서 효율적이다.
자바 공식 문서를 읽어보던 중, 충격적인 문장을 만났습니다.
“A more complete and consistent set of LIFO stack operations is provided by the
Dequeinterface and its implementations, which should be used in preference to this class.”
다시 말해, 스택 자료구조가 필요할 때, Stack 클래스를 사용하기보다는 ArrayDeque을 사용하라는 말입니다. 별 생각 없이 Stack 클래스를 사용해왔기에, 놀랄 수밖에 없었습니다. 이 글은 왜 스택 자료구조 사용시, Stack 클래스를 지양하고, ArrayDeque 등의 다른 방식을 사용해야 하는지에 대한 내용입니다.
1. 스택 자료구조 (프링글스 / 그림)
우선 스택에 대한 정리를 하고자 합니다. 스택은 LIFO한 형태로 데이터를 저장하는 자료구조입니다. 즉, 입구와 출구가 하나인 자료구조로, 먼저 들어온 자료가 나중에 나가게 됩니다. 기본적인 자료구조의 하나로, 브라우저의 뒤로 가기, 함수의 스택 프레임이 저장되는 메모리 등에 활용됩니다. 이를 자바에서 사용하고자 한다면, Stack 클래스 혹은 Deque 인터페이스를 구현한 구현체들을 이용하면 됩니다. Stack 클래스와 Deque 인터페이스는 자바의 Collections Framework에 담겨있습니다. Stack 클래스는 이름에서 볼 수 있는 것처럼, 스택 자료구조를 위해 정의된 클래스입니다. Deque 인터페이스는 Double-ended queue라는 이름에서 알 수 있다시피 양방향으로 입출력이 가능한 큐입니다. 자바는 이를 인터페이스로 남겨두어, 필요에 따라 다양한 구현체를 이용할 수 있게 합니다. 하지만 Stack 클래스의 단점으로 인해, 공식 문서에서는 Stack 클래스의 사용을 지양할 것을 추천합니다.
2. Stack 클래스의 단점
Stack 클래스는 JDK 1.0에서부터 존재했던 클래스입니다. 당시에는 현재에는 사용되지 않는 다양한 클래스들이 있었습니다. 그 중에서 Stack 클래스는 리스트를 구현했던 Vector 클래스를 상속하여 작성되었습니다. Vector 클래스는 ArrayList로 개선되어 새로 만들어지는 프로그램에서는 쓰이지 않는 클래스입니다. 현재에는 레거시 코드들을 위해서만 존재하는 클래스입니다.
1) 모든 작업에 Lock
Vector는 주요 메서드들이 각각 동기화를 하여 성능에 저하를 불러옵니다. Vector는 동기화를 위해, sychronized 키워드를 사용하여 모든 작업에 Lock을 걸었습니다. 이는 멀티 스레드 환경에서는 thread-safe하겠지만, 단일 스레드 환경에서는 불필요한 오버헤드로 성능이 저하됩니다. 아직 코어가 하나밖에 없던 시절에는 큰 문제가 없었지만, 현재의 환경에서는 그렇지 않습니다.
다음은 Stack 클래스의 push() 메서드로 부모 클래스의 메서드인 addElement()를 사용합니다. addElement는 synchronized 키워드로 작업들에 Lock을 걸어 성능에 저하를 불러 올 수 있습니다. 각각의 작업에 동기화가 되기에 성능 튜닝에도 좋지 않습니다.
2) 초기 용량 설정
다음은 Vector 클래스를 상속한 Stack 클래스의 생성자입니다. 단일한 생성자로 매개변수를 받지 않습니다. 즉, 초기 용량을 지정할 수 없습니다. 이는 빈번한 데이터의 삽입이 발생하면, 그에 따라 배열을 복사하는 상황을 빈번하게 만들어 비효율적입니다.
대표적으로 위와 같은 이유로 Stack 클래스의 사용을 지양하는 것이 좋습니다. 대안으로 덱 구현체들을 사용하여 스택 자료구조를 사용할 수 있습니다.
3. 덱 구현체
덱의 구현체로는 대표적으로 ArrayDeque과 LinkedList가 있습니다. 이름에서 알 수 있다시피, 전자는 배열을 통해, 후자는 연결리스트를 통해 구현됩니다.
특별한 경우를 제외하고는 ArrayDeque이 LinkedList 보다 높은 속도를 보입니다. 물론 데이터가 크지 않으면 둘의 차이는 대동소이하지만, 데이터의 크기가 커질수록 ArrayDeque이 유의미하게 빠릅니다. 공식 문서에서는 큐 자료구조를 구현할 때도 ArrayDeque이 빠르다 할 정도로 빠른 속도를 보입니다. null을 담아야 할 상황이 아니라면, ArrayDeque을 사용하는 것이 효율적입니다.
4. Thread-safe가 필요할 때
앞에서 언급한 것처럼 Vector 클래스는 thread-safe하기에, Stack 클래스도 thread-safe합니다. 그래서 thread-safe가 필요한 상황에서는 Stack 클래스를 활용할 수 있을 것으로 보입니다. 물론 가능은 하겠지만 권장되지는 않습니다. 왜냐하면 Vector 클래스가 현재에는 사용되지 않는 클래스이고, thread-safe한 다른 클래스들이 있기 때문입니다.
대표적으로 LinkedBlockingDeque, ConcurrentLinkedDeque를 thread-safe가 필요한 상황에 활용할 수 있습니다. 하지만 둘은 큰 차이를 갖습니다. LinkedBlockingDeque은 lock을 사용하고, 오버헤드가 낮은 대신, 확장성은 좋지 않습니다. 반면에 ConcurrentLinkedDeque은 lock을 사용하지 않고, 오버헤드가 높은 대신, 확장성은 좋은 편입니다.
댓글남기기