[자료구조] Kotlin으로 자료구조 이해하기 - Stack

Stack

Stack의 사전적 의미는 '쌓다, 포개지다'라는 의미로 자료구조로서 Stack은 후입선출(LIFO : Last In First Out) 방식으로 데이터를 저장하는 구조를 의미합니다. 쉽게 말해, 먼저 들어온 데이터부터 하단에 쌓여 가장 늦게 들어온 데이터가 가장 먼저 나가는 구조를 갖게 됩니다.

예를 들어, 빈 Stack에 1,2,3,4,5의 순서로 데이터가 삽입된다면 데이터를 꺼낼 때는 5,4,3,2,1의 순서로 나오게 됩니다.

상자를 쌓을 때 먼저 쌓는 상자가 아래에 쌓이는 상황을 생각하면 될 것 같습니다.

 

Kotlin 자체적으로 Stack이 구현되어 있지는 않지만 "java.util.Stack"을 import 하여 사용할 수 있습니다.

Stack 선언 방법

Stack 클래스는 다양한 기능을 지원합니다. 키워드로 살펴보겠습니다.

• push : Stack에 데이터를 삽입합니다. Stack의 특성상 가장 위에 삽입합니다.
• pop : Stack의 가장 위의 데이터를 Stack에서 제거하고 해당 데이터를 반환합니다. 만약 Stack이 비어있다면 EmptyStackException이 발생합니다.
• peek : pop과 달리 Stack의 가장 위의 데이터를 제거하지 않고 해당 데이터만 반환합니다.
• size : Stack의 크기(원소의 개수)를 반환합니다.
• empty : Stack이 비어있는지 확인합니다. 비어있다면 true, 비어있지 않다면 false를 반환합니다.
• search : Stack에서 찾고자 하는 데이터가 있다면 해당 데이터가 몇 번째로 빠져나갈 수 있는지 반환합니다. Stack에 해당 데이터가 존재하지 않는다면 -1을 반환합니다.

Stack 사용예시

import java.util.Stack

fun main() {
    val stack = Stack<Int>()  // 빈 Stack 선언

    /* push */
    stack.push(1)    // stack = [1]
    stack.push(2)    // stack = [1, 2]
    stack.push(3)    // stack = [1, 2, 3]
    stack.push(4)    // stack = [1, 2, 3, 4]
    stack.push(5)    // stack = [1, 2, 3, 4, 5]

    /* pop */
    println(stack.pop())    // 5
    println(stack)    // stack = [1, 2, 3, 4]

    /* peek */
    println(stack.peek())    // 4
    println(stack)    // stack = [1, 2, 3, 4]

    /* size */
    println(stack.size)    // 4

    /* empty */
    println(stack.isEmpty())    // false

    /* search */
    println(stack.search(2))    // 3 (인덱스가 아니고, 위에서 3번째에 위치)

    /* 스택 비우기 */
    while (stack.isNotEmpty()) {
        println(stack.pop())    // 4, 3, 2, 1
    }

    println(stack.isEmpty())    // true
}