코틀린으로 배우는 자료구조: 스택(Stack) 이해하기

스택은 프로그래밍에서 매우 중요한 자료구조로, 많은 알고리즘에서 활용되고 있어요. 이 글에서는 코틀린을 통해 스택의 개념과 작동 방식을 깊이 있게 이해해 볼 거예요. 스택은 무엇인지, 어떻게 작동하는지, 그리고 코틀린에서의 구현 방법까지 다양한 내용을 다룰 예정이에요.

스택(Stack) 개념 소개

스택은 데이터를 저장하는 자료구조 중 하나로, 후입선출(Last In First Out, LIFO) 방식으로 데이터를 관리해요. 즉, 가장 마지막에 추가된 데이터가 가장 먼저 제거된다는 원리가 특징이에요. 이는 주로 함수 호출 스택, Undo 기능, 괄호 검사 등 다양한 상황에서 활용되죠.

스택의 기본 연산

스택의 기본적인 연산은 다음과 같아요:

• 푸시(Push): 스택의 맨 위에 데이터를 추가하는 연산
• 팝(Pop): 스택의 맨 위 데이터를 제거하는 연산
• 피크(Peek): 스택의 맨 위 데이터를 조회하지만 제거하지는 않는 연산
• 비어 있는지 체크(IsEmpty): 스택이 비어 있는지를 확인하는 연산

이러한 연산들을 통해 스택은 데이터를 관리해요.

코틀린에서 스택 구현하기

코틀린에서 스택을 구현하는 방법은 여러 가지가 있지만, 기본적인 배열(Array)이나 링크드 리스트(Linked List)를 이용할 수 있어요. 여기서는 배열을 사용해 간단한 스택을 구현해 볼 거예요.

배열을 이용한 스택 구현

다음은 배열을 이용하여 스택을 구현한 코드예요:

fun push(item: T) {
    if (top == capacity - 1) {
        throw IllegalStateException("스택이 가득 찼습니다.")
    }
    items[++top] = item
}

fun pop(): T {
    if (isEmpty()) {
        throw NoSuchElementException("스택이 비어 있습니다.")
    }
    return items[top--] as T
}

fun peek(): T {
    if (isEmpty()) {
        throw NoSuchElementException("스택이 비어 있습니다.")
    }
    return items[top] as T
}

fun isEmpty(): Boolean {
    return top == -1
}

fun size(): Int {
    return top + 1
}

}

코드 설명

• Stack 클래스는 제네릭 타입으로 다양한 데이터 타입을 저장할 수 있어요.
• push 메서드는 스택의 맨 위에 새로운 아이템을 추가하고, 가득 차면 예외를 던져요.
• pop 메서드는 맨 위의 아이템을 제거하고 반환해요. 스택이 비어있으면 예외를 던지죠.
• peek 메서드는 제거하지 않고 맨 위 아이템을 반환해요.
• isEmpty와 size 메서드는 각각 스택 상태를 체크할 수 있는 유용한 메서드예요.

스택의 활용 사례

스택은 다음과 같은 다양한 분야에서 사용돼요:

• 재귀 알고리즘: 함수 호출 시 스택을 사용해 호출 내용을 저장해요.
• Undo 기능: 사용자가 마지막에 진행한 작업을 취소할 수 있는 기능에서 스택을 활용하죠.
• 괄호 검사: 수식의 괄호가 올바르게 매칭되는지를 검사할 때 스택을 사용하여 처리해요.

주요 운영	설명
푸시(Push)	스택의 top에 데이터를 추가합니다.
팝(Pop)	스택의 top에서 데이터를 제거하고 반환합니다.
피크(Peek)	스택의 top에 있는 데이터를 확인만 합니다.
비어 있는지 체크	스택이 비어 있는지 확인하는 연산입니다.

스택을 활용한 문제 해결

스택을 활용해볼 수 있는 간단한 문제를 소개할게요. 예를 들어, 문자열에서 괄호가 잘 닫혀 있는지 확인하는 문제를 생각해 볼 수 있어요.

문자열 “(())”는 올바른 형식이지만, “(()”는 올바르지 않아요. 다음과 같은 코드를 통해 스택을 활용할 수 있어요.

for (char in s) {
    when (char) {
        '(' -> stack.push(char)
        ')' -> {
            if (stack.isEmpty()) return false
            stack.pop()
        }
    }
}
return stack.isEmpty()

}

코드 설명

• 스택을 생성해 괄호를 푸시하고, 닫는 괄호를 만날 때마다 팝하여 짝이 맞는지 검사해요.
• 모든 문자를 검사한 후 스택이 비어 있으면 올바른 괄호 문자열이에요.

결론

스택은 프로그래밍에서 중요한 역할을 하는 자료구조로, 다양한 상황에서 활용될 수 있어요. 코틀린에서 스택을 구현하는 것은 어렵지 않으며, 이를 통해 알고리즘을 보다 효과적으로 구현할 수 있답니다.

스택을 활용해 더 복잡한 문제를 해결해 보고, 여러분의 프로그래밍 실력을 한층 더 끌어올려 보세요! 여러분도 충분히 할 수 있어요!