스택(Stack)은 데이터를 후입선출(LIFO, Last In First Out) 방식으로 저장하는 자료 구조입니다.
코틀린에서 스택을 구현할 때 주로 사용하는 두 가지 주요 데이터 구조는 MutableList와 Array입니다.
이번 글에서는 두 가지 방법으로 스택을 구현하는 코드와 함께, 각 방식의 차이점과 특징을 비교해보겠습니다.
1. MutableList를 사용한 스택 구현
MutableList는 코틀린의 동적 리스트로, 크기를 필요에 따라 자동으로 확장하거나 축소할 수 있습니다.
이를 사용하면 스택을 간단하고 유연하게 구현할 수 있습니다.
코드 예제:
val stack = mutableListOf<Int>()
fun push(data: Int) {
stack.add(data) // 스택의 끝에 데이터 추가
}
fun pop(): Int {
return if (stack.isNotEmpty()) stack.removeAt(stack.size - 1) else -1
}
fun size(): Int {
return stack.size
}
fun empty(): Int {
return if (stack.isEmpty()) 1 else 0
}
fun top(): Int {
return if (stack.isNotEmpty()) stack.last() else -1
}주요 특징:
- 동적 크기 관리: MutableList는 크기를 신경 쓸 필요 없이 자동으로 확장됩니다.
- 간결한 메서드 지원:
- add()로 데이터 추가.
- removeAt()으로 끝에서 데이터를 제거하고 반환.
- last()로 마지막 요소를 확인.
- 코드 간결성: top 변수를 따로 관리하지 않아도 stack.size로 상태를 바로 파악할 수 있습니다.
2. Array를 사용한 스택 구현
Array는 고정된 크기를 가지는 자료 구조로, 생성 시 크기를 미리 지정해야 합니다. 배열을 사용한 스택에서는 top 변수를 이용해 현재 스택의 위치를 추적합니다.
코드 예제:
val MAX_SIZE = 10000
val stack = Array(MAX_SIZE) { 0 }
var top = -1
fun push(data: Int) {
if (top < MAX_SIZE - 1) {
top++
stack[top] = data
} else {
println("Stack Overflow")
}
}
fun pop(): Int {
return if (top >= 0) {
val data = stack[top]
top--
data
} else {
-1
}
}
fun size(): Int {
return top + 1
}
fun empty(): Int {
return if (top == -1) 1 else 0
}
fun top(): Int {
return if (top >= 0) stack[top] else -1
}주요 특징:
- 고정 크기 관리: 배열은 생성 시 크기가 고정되며, 초과 시 별도 처리가 필요합니다.
- top 변수: 배열에서 현재 위치를 관리하며, 데이터를 추가/제거할 때 top을 사용해 직접 인덱스를 추적합니다.
- 직접 접근: stack[top]으로 데이터를 추가하거나 읽을 수 있습니다.
3. MutableList와 Array의 차이점
| 특징 | MutableList | Array |
| 크기 | 동적 (자동 확장 가능) | 고정 (생성 시 크기 지정 필요) |
| 데이터 추가 | add() 메서드로 자동 추가 | top 변수를 이용해 인덱스에 직접 추가 |
| 데이터 제거 | removeAt()으로 요소 제거 및 반환 | top을 감소시켜 직접 관리 |
| 효율성 | 메모리 자동 관리 (약간의 오버헤드 발생) | 메모리 고정, 관리 필요 |
| 코드 간결성 | 간단하고 직관적인 구현 가능 | 추가 로직 및 변수 관리 필요 |
| 오류 가능성 | 크기 초과 위험 없음 | 크기 초과 시 별도 처리 필요 |
4. 왜 두 가지 구현 방식이 다른가?
MutableList와 Array의 근본적인 차이
- MutableList:
- 크기가 동적으로 변경되며, 리스트의 메서드를 사용해 데이터를 쉽게 추가/제거할 수 있습니다.
- 리스트의 크기(stack.size) 자체가 스택의 상태를 나타내므로 top 변수가 필요 없습니다.
- Array:
- 크기가 고정되며, 데이터를 추가/제거할 때 현재 위치를 추적하는 top 변수가 필요합니다.
- 배열은 특정 인덱스에 바로 접근할 수 있지만, 크기 초과에 대한 처리가 필요합니다.
왜 Array 방식에서는 top 변수가 필요할까?
- 배열은 크기가 고정되어 있어, 데이터가 저장될 위치를 명확히 관리해야 합니다.
- top은 현재 스택의 최상단 요소를 추적하는 역할을 하며, 이를 통해 데이터를 추가(push)하거나 제거(pop)할 수 있습니다.
왜 MutableList에서는 top 변수가 필요하지 않을까?
- MutableList는 동적 크기 관리로 인해 리스트의 끝에 데이터를 추가하거나 제거할 수 있습니다.
- 스택의 상태를 나타내기 위해 리스트의 크기(stack.size - 1)를 활용할 수 있으므로 top을 별도로 관리할 필요가 없습니다.
5. MutableList와 Array의 사용 시나리오
MutableList가 적합한 경우
- 스택 크기가 동적으로 변해야 할 때: 크기 제한 없이 데이터를 추가할 수 있어야 할 경우.
- 간단한 구현이 필요할 때: 코드 작성과 유지보수가 간편해야 하는 경우.
Array가 적합한 경우
- 스택 크기가 고정되어 있는 경우: 알고리즘 문제에서 스택의 크기가 명확히 제한되는 경우.
- 메모리를 엄격히 관리해야 할 때: 메모리를 고정 크기로 관리해야 하는 경우(예: 임베디드 시스템).
- 성능이 중요한 경우: 동적 메모리 할당보다 고정 크기 배열을 사용하는 것이 빠릅니다.
6. 결론
- MutableList는 크기 제한 없이 간단하고 유연하게 스택을 구현할 수 있는 자료 구조로, 일반적인 코틀린 프로젝트에서 가장 적합합니다.
- Array는 고정 크기의 데이터를 처리하거나 메모리 관리를 엄격히 해야 하는 경우에 유용합니다. 그러나 추가적인 로직(top 변수 관리 등)이 필요합니다.
요약:
- top 변수는 고정 크기 배열(Array)에서 현재 위치를 추적하기 위해 필요하며, MutableList에서는 크기 관리가 자동으로 이루어지기 때문에 불필요합니다.
반응형
