스택이란 무엇일까?
스택이란 나중에 들어온 요소가 먼저 나오는 선형 자료구조이다. 즉 LIFO(last-in first-out, 후입선출)을 만족한다. 여기서 선형 자료구조란 데이터들 간의 앞뒤 관계가 1:1의 선형관계로 되어 있는 자료구조이다.
스택을 구현하려면 일반적으로 다음과 같은 메소드를 구현해야 한다.
- push() : 데이터 삽입
- pop() : 가장 위쪽에 있는 데이터 즉, 가장 나중에 넣은 데이터 꺼내서 반환
- peek() : 가장 위쪽에 있는 데이터 반환
- size() : 스택에 있는 데이터의 개수
- isEmpty() : 스택이 비어있는지 여부
Java 에서 제공하는 java.util.Stack 클래스는 디자인이 잘못되어, 보통의 엔터프라이즈 환경에서는 잘 사용하지 않는다. 왜 그럴까?
엔터프라이즈 환경에서 java.util.Stack 클래스를 잘 사용하지 않는 이유
Java 에서 제공하는 java.util.Stack 클래스는 실제 서비스 환경에서는 잘 사용하지 않는다고 한다. Java 11버전의 소스코드를 살펴보면서 그 이유를 생각해 보았다.
우선 java.util.Stack은 클래스이며 Deque이나 Queue와 같은 다른 자료구조처럼 인터페이스가 아니고 클래스로 되어 있고, Vector 클래스를 상속한다. Stack 클래스를 사용하지 않는 대부분의 이유가 java.util.Stack의 이러한 구조적인 문제로 발생한다.
첫번째 문제점은 스택에서 구현하지 않아도 되는 기능, 즉, Vector의 기능을 사용할 수 있다는 점이다. Stack은 Vector를 상속받기 때문에, Vector의 모든 메소드를 사용할 수 있다. 이는 의도하지 않은 버그나 성능저하를 일으킬 수 있다.
초보 개발자가 java.util.Stack에서 사용할 수 있는 메소드를 찾다가, 다음과 같이 첫번째 요소를 지우는 방법을 적용시켰다고 하자.
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < 10000 ; i++) {
stack.push(i);
}
for (int i = 0; i < 6000; i++) {
stack.remove(0);
}우선 stack.remove(0) 첫번째 인덱스의 요소를 삭제하기에 스택의 LIFO원칙에 어긋난다. 이러한 스택 자료구조에서 지켜야 할 원칙을 배제하더라도, 잘 작동하기는 하나 속도 측면에서 비효율적이다. 일단 remove(int index)의 경우, Vector에서 구현된 메소드를 사용하게 된다. Vector는 내부적으로 배열을 이용하는데 첫번째 요소를 배열에서 삭제할 경우 시간 복잡도는 O(n)이다. 삭제가 빈번하게 일어나는 경우, 연결리스트를 구현체로 이용한다면 좀 더 빠른 속도로 같은 작업을 처리할 수 있을 것이다. 연결리스트의 경우, 첫번째 요소를 삭제할 때 시간 복잡도가 O(1)이기 때문이다. Stack의 사용자는 stack.remove(0)이 Vector의 메소드를 이용한다는 것을 예상하지 못하지만 실제로는 Vector의 메소드를 이용하는 것이고 예상치 못한 문제를 발생시킨다.
Deque<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000 ; i++) {
list.add(i);
}
for (int i = 0; i < 6000; i++) {
list.removeFirst();
}Stack이 인터페이스 였다면, remove(int index)와 같은 불필요한 메소드는 아예 사용하지 못하게끔 방지할 수 있고, 비즈니스 로직에 맞춰서 적합한 구현체를 선택할 수 있었을 것이다.
두번째 문제점은 상위클래스 Vector의 구현에 Stack의 동작이 의존한다는 점이다.
그 증거로 java.util.Stack의 메소드가 Thread safe한지 바로 알아보기 어려운데 그 이유는 Thread safe인지 나타내는 부분이 Vector 구현부에 의존하기 때문이다.
public E push(E item) {
addElement(item);
return item;
}다음은 Stack의 메소드 중 push() 메소드이다. 언뜻 보면 이 메소드가 Thread safe하지 않은 것처럼 보인다. 하지만 addElement라는 Vector에서 구현된 메소드를 보면
public synchronized void addElement(E obj) {
modCount++;
add(obj, elementData, elementCount);
}synchronized를 써서 메소드 블록에 쓰레드 1개만 접근할 수 있기 때문에 Thread safe함을 알 수 있다. Vector라는 내부 구조를 살펴봐야 Thread safe함을 알 수 있기 때문에 캡슐화가 되지 않는다. 만약에 Vector의 addElement 메소드가 synschronized 처리가 되어 있지 않았다면, Stack의 push 메소드도 Thread safe 하지 않았을 것이다. 또한 만약 Vector에서 addElement의 구현이 바뀌게 되면, Stack 클래스 또한 영향을 받게 된다. Stack 클래스를 사용하기 위해서는 Vector 내부 구조까지 봐야하는 문제가 생기게 되는 것이다.
그럼에도 불구하고 java.util.Stack이 라이브러리에 계속 남아있는 이유는?
Vector는 ArrayList와 동일한 구조를 가지고 배열의 크기가 늘어나고, 줄어듬에 따라 자동으로 크기가 조절이 된다. 이는 Stack의 LIFO를 고려한다면, Vector에 속해서는 안된다. 삽입과 삭제가 빈번하게 일어날 때, 배열을 이용하면 메모리를 많이 사용하기 때문이다. 그렇지만 자바의 하위 호환성을 위해서 상속관계를 계속 유지하고 있다.
Stack 클래스 사용 대신 어떤 방법을 써야할까?
자바 공식 API에 의하면 다음과 같이 나와 있다.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();즉, 좀 더 완전하고 일관된 Stack의 LIFO 연산 집합을 Deque 인터페이스와 그 구현체들에서 제공하고 있으니, Stack 클래스보다는 Deque과 Deque 구현체들을 사용하라고 되어 있다.
덱(Deque)도 선형 자료구조로 맨 앞과 맨 뒤의 데이터의 삽입과 삭제가 가능한 선형 자료구조이다. 자료구조 스택의 기능을 확장한 자료구조이다. API에서 제안한 방식을 채택하면, 사용자가 비즈니스 로직에 맞게 구현방식을 선택할 수 있고, 구현체가 클래스가 아닌 인터페이스를 상속받아서 구현체 말고 다른 클래스의 내부구조를 살펴보지 않아도 되기 때문에 캡슐화가 보장된다는 장점이 있다.
정리
1. 스택이란? LIFO(후입선출)의 선형 자료구조이다.
2. java.util.Stack 클래스를 사용하지 않는 이유?
- Stack에서 불필요한 기능인 Vector 메소드로 접근이 가능하여 예상치 못한 문제가 발생할 수 있기 때문이다.
- Stack의 동작이 Vector의 구현에 의존하여 캡슐화와 유연성이 깨진다.
참고자료
'(컴퓨터 언어)Java' 카테고리의 다른 글
| JVM이란?. (3) | 2024.09.15 |
|---|---|
| 데이터 불일치 문제 피하기 : 자바에서 스레드 동기화를 하는 3가지 방법 (0) | 2023.08.14 |
댓글