Stack 이란 무엇인가?
Stack은 마지막에 들어온 값이 제일 먼저 나가는(LIFO) 특징을 가진 자료구조로, 값을 추가하고 빼내는데 O(1)의 시간 복잡도로 가능해 다양한 곳에 활용될 수 있는 자료 구조이다.
*예를 들어 안드로이드에서는 화면(Fragment) 변경 시 이전 화면의 목록을 관리하는데 Stack 자료 구조를 사용하고 있다.
한 번 Stack이 어떻게 동작하는지 그림으로 살펴보자. Stack은 값을 여러개 담을 수 있는 하나의 Container을 가지고 있으며, 값을 집어넣으면 아래와 같이 순서대로 Container에 쌓인다.
예를 들어 Element1, Element2를 Stack에 순서대로 쌓으면 아래와 같은 형태가 된다.
값을 빼낼 때는 무조건 위에 있는 값부터 빼내진다. 즉, Stack에서 자료가 빼내질 때는 Element2, Element1 순서로 빼내진다.
Kotlin에서 Stack 사용하기
Stack 생성하기
Stack Class를 사용해 생성하기
Kotlin은 Stack을 사용하기 위해 java.utils 패키지의 Stack 클래스를 사용한다. Queue가 LinkedList를 구현하는 것과 달리 Stack은 그 자체로 구현체가 있다. 따라서 아래와 같이 선언할 수 있다.
val stack : Stack<Int> = Stack()하지만 이 방법은 내부적으로 Vector을 사용하기 때문에 비효율적인 점이 있다. 이에 대해 설명하려면 길기 때문에 아래의 [Kotlin Stack Class의 한계점] 섹션에서 살펴본다.
따라서 아래 Deque 인터페이스를 구현하는 방식으로 생성하는 것을 추천한다.
Deque 인터페이스를 구현하는 ArrayDeque사용해 Stack 생성하기
Deque인터페이스를 구현하는 ArrayDeque클래스를 사용해 Stack을 생성할 수도 있다.
val stack: Deque<Int> = ArrayDeque()
Stack에 값 추가하기
Stack에 값을 추가할 때는 push를 사용한다. push를 한 순서대로 값이 들어가게 된다.
fun main() {
val stack : Stack<Int> = Stack()
stack.push(1)
stack.push(2)
println(stack) // [1, 2]
}
Stack에서 값 빼내기
Stack에서 값을 빼낼 때는 pop을 사용한다. 마지막에 push된 값이 먼저 나온다.
fun main() {
val stack : Stack<Int> = Stack()
stack.push(1)
stack.push(2)
println(stack.pop()) // [2]
println(stack.pop()) // [1]
println(stack) // []
}
Stack에서 다음에 빼낼 값 미리보기
가끔은 Stack에서 값을 빼내지 않고, 다음에 꺼낼 값을 미리보고 싶을 수 있다. 그럴 때는 peek을 사용한다. peek은 Stack의 맨 위에 있는 값(다음에 꺼내질 값)을 빼내지 않고 가져온다.
fun main() {
val stack : Stack<Int> = Stack()
stack.push(1)
stack.push(2)
println(stack.peek()) // [2]
println(stack) // [1, 2]
}
Kotlin Stack Class의 한계점
다만 Stack Class은 내부에서 데이터들을 Array로 관리하는 Vector을 구현하기 때문에 초기 사이즈가 있고, Stack에 값이 계속 추가되어 사이즈가 한계치에 달하면 사이즈를 늘려 복사하는 방식을 취한다.
public class Stack<E> extends Vector<E> {
이 때문에 Stack에 포함된 데이터의 개수가 M이라고 할 때, 값을 추가하기 위해 최악의 경우 O(M)의 시간 복잡도로 값이 추가될 수 있다. 또한 이후 추가될 값을 위해 불필요한 메모리 공간을 이미 점유하고 있는 문제가 있다.
이러한 단점을도 존재하지만 장점도 존재한다. 내부 구현이 Array로 되어 있기 때문에 메모리 공간에 일렬로 늘어서 있어서, 특정 노드가 어디에 존재하는지 알 수 있고, 메모리를 효율적으로 사용이 가능하다. Queue를 구현하는 LinkedList는 다음 노드는 메모리 공간에 랜덤으로 존재하고 이를 확인하기 위해서는 이전 노드에서 가리키는 Pointer을 통해 메모리를 조회할 수 있기 때문에 Array에 비해 탐색 속도가 느린 문제가 존재한다.
왜 Kotlin Stack은 Vector로 구현되었는가?
하지만, 보통 맨 마지막에 들어온 값에 Access하는 것을 주로 하는 Stack을 굳이 Vector로 구현하는 의미를 찾지 못할 것이다.
이 이유는 Java1.2 미만에서는 Vector만 존재했고, LinkedList가 소개된 것은 Java1.2이기 때문이다. 처음 Stack을 구현할 때 Vector로 구현했고, 이 Stack API를 사용하는 주요 프로젝트가 많았기 때문에 하위 호환성(backward compatibility)을 유지하기 위해 현재까지 유지되고 있다고 한다.
Stack의 대안 ArrayDeque
이에 대한 해결책을 위한 주석이 아래와 같이 달려 있다.
/**
* ...
* 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>();}</pre>
*
* @author Jonathan Payne
* @since 1.0
*/
public class Stack<E> extends Vector<E> {
바로 Deque<Int>를 사용하는 것이다. ArrayDeque는 내부적으로 LinkedList를 사용하지는 않지만, Stack 자료구조를 만들기 위해 더욱 효율적으로 Array를 사용하도록 수 있도록 구현되어 있다.
ArrayDeque 내부를 보면 resizable circular array을 사용해 Deque를 구현하기 때문에 배열의 끝이 배열의 처음과 연결되어 있어 처음과 끝에 데이터를 삽입하는데 더욱 효율적으로 만들어져 있다. 즉, 맨 앞의 데이터가 삭제된 상태이고, 배열의 마지막에 공간이 없을 때 데이터가 추가되면, 배열의 맨 앞에 데이터가 삽입되는 형태가 된다. 이를 통해 기존 Vector이 linear array로 구현되어 생긴 한계점인, 맨 마지막에 추가 요소를 넣을 공간이 없을 때 무조건 사이즈를 증가시키는 것에 대한 문제점을 해결하였다.
Deque 사용 예시
fun main() {
val stack: Deque<Int> = ArrayDeque()
stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.pop() // [2]
println(stack) // [1]
}
하지만, 이것이 과연 Stack Class와 비교해 이점이 있다고는 확언하기 어렵다. Stack을 쓰기 위해 사용하는 사람들은 맨 뒤 노드에서만 데이터를 빼고 더할 것이기 때문에 맨 앞의 노드가 사용될 일은 거의 없기 때문이다.
정리
ArrayDeque가 resizable circular array을 사용함으로써, StackClass의 한계점을 극복했지만, 여전히 크기가 아무리 늘어나도 전체 복사가 일어나지 않는 Doubly LinkedList에 비해서는 한계가 존재한다.
하지만, Java는 하위 호환성, 메모리 효율성, 성능(원소의 수가 많지 않을 경우)가 더 중요하다고 생각해 ArrayDeque만을 제공하는 것으로 보이며 이에 대한 강점이 분명히 있을 것으로 보인다. 이를 잘 고려해 Kotlin에서 Stack 자료구조를 사용하도록 하자.
