Java 에서 Stack 구현체로는 무엇을 사용해야할까?(feat_Java로 코딩테스트 문제 풀기)

Stack

• LIFO -> 처음 넣었던 원소는, 마지막에 꺼낼 수 있다. "끝" 에 대한 삽입과, 제거만을 허용한다

Stack 은 Array, LinkedList 등등을 사용하여 구현할 수 있다.

사실 자료구조상, 양 쪽(out,in 하는 곳) 이 모두 뚫려 있더라도, 제공하는 작업이 pop, push 이기만 해도 stack 으로 제공가능하다.

따라서 Queue 도 스택으로 사용이 가능하다.

---

Java 에서 Stack 을 위해 어떤 구현체를 사용해야할까?

그렇다면 Java 에서 Stack 으로 사용할 자료구조에는 무엇이 있을까?

 

그냥 Stack 사용하면 안됨??  

흠.. 가장 먼저, "Stack" 클래스를 살펴보자!

 

Java 의 Stack 에 대한 문서에는 이런 구절이 존재한다

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>();

Deque 는 새로운 원소는 "시작" 또는 "끝" 에만 추가되거나, 삭제 될 것을 요구한다. 여기에 적합한 자료구조는 무엇일까?

가장 먼저 떠오르는 것은 LinkedList 다. 연결리스트는 랜덤한 위치에 대한 삽입과 삭제가 가능하다 (위치를 찾는데에는 O(n) 이 걸리기는 한다 ) . 그리고 Java 의 LinkedList 는 Deque 를 구현하고 있다.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

또한 이중연결리스트이기 때문에( Node 클래스를 살펴보면 next, prev 를 저장하고 있다) Last, First 에 대한 추적을 하고 있음을 확인할 수도 있다. ( Deque )

하지만 Java 에서는 ArrayDeque 라는 자료구조 또한 제공해주고 있다. 이 자료구조는 ArrayList 와 유사한 특징을 가지고 있다

• Array 라는 이름에서 볼 수 있듯이, "배열을 기반" 으로 하고 있다
• 고정 길이 자료구조가 아니다 -> 필요시 (ex, add) 저장공간을 늘린다
  • 64보다 작은 크기였던 경우에는 2를 증가시키고, 그 외의 상황에서는 2배 증가한다.

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

• stack 으로 사용시 Stack 클래스보다 빠르다
• queue 로 사용시 LinkedList 보다 빠르다.

• 단, Stack 은 스레드 세이프한 반면, ArrayDeque 는 non-thread-safe 하다.

---

Stack 자료구조가 존재하는데... 문서에서도 Stack 을 사용하느니 Deque 를 사용하라고 한다. 왜 그럴까?

추측건데 "Stack 은 Vector 를 상속하는 구체 클래스" 라는 이유도 존재할 것 같다.

Stack 은 Vector 를 "상속" 하고 있다. Vector 에서는 index 를 사용한 랜덤 접근(상수시간 으로 특정 원소에 대한 탐색이 가능) 이 가능하다. Deque 에서는 단지 front, end 에 대한 insert, remove 만을 public 하게 제공하고 있다. 위치 기반 접근을 public 하게 제공하지는 않는다. 그리고 Stack 자료구조를 사용하려고 하는 상황이라면, 이런 위치 기반 접근 기능이 필요하지는 않을 것이다.

하지만 Stack 은 JDK1.0 부터 존재했기에 "자바의 하위 호환성" 때문에 이러한 상속관계를 계속 유지하고 있다. 사실상 Java에 새롭게 등장했던 Collection 프레임워크로 인해, 잔재로 남은 클래스라고 볼 수 있다.

또한 Stack 은 인터페이스가 아니다.

Stack 에 대한 연산이 필요할 경우, 구체클래스인 Stack 을 사용하게 되는 것이다. 반면 Deque 는 인터페이스이기 때문에 여러가지 구현체를 사용할 수 있다.

Deque<Integer> queue = new LinkedList<>();
Deque<Integer> queue = new ArrayDeque<>();

참고로, Deque 와 Stack 의 iteration 순서는 정 반대이다

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(new ArrayList<>(stack)); // prints 1, 2, 3

Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(new ArrayList<>(deque)); // prints 3, 2, 1

그렇다면 어떤 구현체를 사용하는 것이 좋을까?

이 주제에 대한 시작은 사실 "코딩테스트"에서 어떤 자료구조를 사용할지에 대한 고민이었다.

Stack 연산이 필요한 상황이라면 어떤 것을 사용하는 것이 좋을까?

사실 코딩테스트만을 위해서라면, 동시성을 고려하지 않는 경우가 대부분이라고 생각한다. 이 경우에는 non-thread-safe 하지만,queue, stack 이 필요한 상황에서 더 빠른 속도를 제공하는 ArrayDeque 를 사용하는 것이 좋을 것 같다.

성능

아직 성능테스트를 직접 해보진 않았으나, 코딩테스트 문제를 풀 때 구현체를 변경하여 제출해보았다

ArrayDeque, LinkedList, Stack 을 사용해보았는데, LinkedList, Stack 은 비슷한 성능을 보여주었다. 아무리 다른 자료구조를 사용해도 변하지 않던 성능이 ArrayDeque 를 사용하니 확연히 빠른 속도를 보여주었다.