[자료구조 with 코틀린] 2. Stack

1. 개념

나중에 들어간 데이터가 먼저 나오는 자료구조입니다.

이를 LIFO(Last In First Out)이라고도 합니다.

안드로이드 액티비티를 관리하는 데 사용되는 자료구조입니다.

2. 시간복잡도

1) 탐색

Random Access가 안 되며 특정 데이터를 찾을 때까지 탐색을 수행해야 하므로 O(N)의 시간복잡도를 가집니다.

2) 삽입 및 삭제

삽입 및 삭제에는 O(1)의 시간복잡도를 가집니다.

3. 공간복잡도

N개 만큼의 스택이 쌓이기 때문에 O(N)입니다.

4. 구현

구현하기에 앞서, 스택을 구현할 때에는 ArrayList를 사용하는 것이 좋습니다.

ArrayList의 경우 index를 사용하면 마지막에 데이터를 추가하고 삭제하는 데 O(1)의 시간복잡도를 갖기 때문입니다.

따라서 전 ArrayList를 사용하여 구현하겠습니다.

class Stack<E> {

    private var stack = ArrayList<E>()

    fun push(item: E) {
        stack.add(item)
    }
    fun pop() : E? {
        if (stack.size == 0) {
            return null
        }
        val lastIndex = stack.size-1
        val item = stack[lastIndex]
        stack.removeAt(lastIndex)
        return item
    }
    fun peek(): E {
        val lastIndex = stack.size - 1
        return stack[lastIndex]
    }
    fun desc() {
        for (e in stack) {
            println("$e")
        }
        println()
    }
}