[메이드 인 스위프트] 자료구조 - 스택 Stack 구현해보기

개요

이번에 알고리즘 공부를 할 참이었는데,

자료구조도 다시 공부하고 Swift로는 구현을 안 해본 거 같아서

Swift로 구현해보고 이를 함수형을 지키며 불변성 & 순수 함수로 구현해보려 한다.

 

그냥 문뜩 Swift로 함수형 프로그래밍을 하고 싶어졌다.

지난 번 Linked List를 함수형으로 만들었을 때 함수형으로 해볼 기회가 있었는데,

거기서 매력을 느껴서 그런 것 같다.

 

---

코드 구현

public struct KJStack<Element> {
    private let stack: [Element]

    public var count: Int { stack.count }
    public var isEmpty: Bool { stack.isEmpty }
    public var peek: Element? { stack.last }

    public init(_ stack: [Element] = []) {
        self.stack = stack
    }

    public func push(_ value: Element) -> KJStack {
        return KJStack(stack + [value])
    }

    public func pop() -> KJStack {
        guard !stack.isEmpty else { return self }
        return KJStack(Array(stack.dropLast()))
    }
    
    public func popLast() -> Element? {
        return stack.last
    }
}

// MARK: Equatable
extension KJStack: Equatable where Element: Equatable {
    public static func == (lhs: KJStack<Element>, rhs: KJStack<Element>) -> Bool {
        lhs.stack == rhs.stack
    }
}

// MARK: CustomStringConvertible
extension KJStack: CustomStringConvertible {
    public var description: String {
        "Current KJStack: \(stack)"
    }
}

 

실행 코드

var stack = KJStack<Int>()
print(stack) // KJStack: []

stack = stack.push(5)
print(stack) // KJStack: [5]

stack = stack.push(10)
print(stack) // KJStack: [5, 10]

print("Peek Value: \(stack.peek ?? -1)") // Peek Value: 10
print("Current Stack Count: \(stack.count)") // Current Stack Count: 2

let lastValue = stack.popLast()
print("Popped Value: \(lastValue ?? -1)") // Popped Value: 10

stack = stack.pop()
print(stack) // KJStack: [5]

// Equatable 테스트
let stack1 = KJStack([1, 2, 3])
let stack2 = KJStack([1, 2, 3])

print(stack1 == stack2) // true

 

구현 후 느낀점

위와 같이 작성을 해봤는데, 지금 구조는 메모리 관점에서는 많이 비효율적이다.

아무래도 함수형의 단점이기도 하다고 생각한다.

 

지금 push든 pop이든 전체 복사를 하고 새로 객체를 반환해주는데,

그래서 그런지 백준 문제를 위 Stack으로 풀면 시간초과가 발생한다.