[DataStructure] 스택

0. 들어가기

프로그램의 자동 메모리, 네트워크 프로토콜, 여러 테스트 프로그램 등 여러 곳에서 공통적으로 쓰이는 자료구조를 알고 계신가요?
바로 스택입니다! 오늘은 스택을 직접 구현해보도록 하겠습니다.

1.  구조

재귀함수가 어떻게 동작하는지 궁금하신 적 없으신가요? 이미 알고 계시다구요?
재귀함수는 현재 실행 중인 서브루틴에 관한 정보를 저장하는 콜스택을 사용하여 루틴을 처리하고, 상위 루틴으로 돌아갑니다.
이때 사용하는 콜 스택이 스택과 같은 구조를 사용하고 있죠!

스택(stack)은 뭔가를 쌓아놓은 '더미'를 뜻합니다. 건초더미, 서류더미, 옷더미 등을 예로 들수 있겠습니다.
시각적으로는 제일 먼저 들어온 데이터가 제일 밑에에 위치하고, 제일 나중에 들어온 데이터가 제일 위에 위치합니다.
데이터가 오가는 통로는 제일 위에 하나만 존재하고, 이를 push/pop으로 관리합니다.
하나의 구멍에 데이터를 밀어넣고, 구멍에서 데이터가 튀어나오는 모습이 그야말로 push와 pop 입니다.

2. 구현

스택 뭐 어려울 것 있겠습니까 바로 가보겠습니다.

struct Stack<T>{
    private var stack: [T] = []
    var count: Int{
        return self.stack.count
    }
    var isEmpty: Bool{
        return stack.isEmpty
    }
    var top: T?{
        return stack.last
    }
}

제네릭을 채택한 구조체를 정의하고, swift의 기본 자료형인 Array를 private로 생성하였습니다.
현재 데이터의 갯수를 반환하는 count, 비어있는지를 확인하는 isEmpty, 최상위 요소를 반환하는 top를 프로퍼티로 가집니다.

    ///새 노드를 스택 위에 올림
    mutating func push(_ data: T){
        self.stack.append(data)
    }
    ///스택 최상단 노드의 데이터를 반환 후 노드 삭제
    mutating func pop()->T?{
        return self.stack.popLast()
    }

 

구조체이기 때문에 mutating func로 배열을 조작하고 있습니다. (Swift의 키워드는... 나중에 제대로 정리할게요...!)
Array는 O(1)인 append와 popLast를 사용하여 모든 연산이 상수시간 안에 동작합니다.

popLast와 removeLast의 차이를 알고 계신가요?
두 메소드는 공통적으로 Array의 마지막 요소를 제거하고, 제거한 요소를 반환합니다.
그러나 removeLast는 사용에 전제조건이 있습니다. 반드시 비어있지 않아야 한다는 것이죠!

이러한 특징으로 당연하게도 두 메소드는 반환 타입이 다릅니다.

removeLast는 옵셔널이 아닙니다.

popLast는 옵셔널입니다.

(여담으로 코테하는 사람들은 removeLast가 좀 더 빠릅다고 합디다)

전체 소스코드는 다음과 같습니다.

struct Stack<T>{
    var count: Int{
        return self.stack.count
    }
    var isEmpty: Bool{
        return stack.isEmpty
    }
    var top: T?{
        return stack.last
    }
    private var stack: [T] = []
    ///새 노드를 스택 위에 올림
    mutating func push(_ data: T){
        self.stack.append(data)
    }
    ///스택 최상단 노드의 데이터를 반환 후 노드 삭제
    mutating func pop()->T?{
        return self.stack.popLast()
    }
}

마무리

간단하게 스택을 구현해보았습니다. 이미 Array에 필요한 메소드가 다 구현되어있어 래핑한것에 불과합니다만...

Swift를 사용하는 입장에서 스택은 정말 요긴한 점이, 자료의 삽입과 삭제가 상수시간에 이루어진다는 점에서 다양하게 활용할 수 있습니다.
큐를 내장하고있지 않은 Swift에서, 스택 두개를 사용하면 나쁘지 않은 성능의 큐를 빠르게 구현할 수 있습니다.
또한 해당 큐를 다시 2개를 사용하여 양방향 입출력을 지원하는 큐인 덱도 간단하게 구현할 수 있죠!

큐와 덱으로 다음 포스팅에서 만나요!