[Swift] 스택

안녕하세요 ◠‿◠ 고고입니다.

 

스택

스택은 블록을 아래부터 위로 쌓아 올리는 구조를 가지고 있습니다.

LIFO(Last-in, first-out), 후입선출.

가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 됩니다.

서류를 예로 들 수 있습니다.

 

함수

(1) 삽입 (Push) : Push는 맨 위에 데이터가 저장 됩니다.

 

(2) 삭제 (Pop) : 데이터를 삭제하는 것을 Pop이라 합니다. Pop도 맨 위 데이터가 삭제됩니다.

 

(3) 읽기 (Peek) : 마지막 위치(top)에 해당하는 데이터를 읽습니다. 이 때, top의 변화는 없습니다.

 

구현

public struct Stack<Element> {
    private var storage: [Element] = []
    
    public init() { }
    
    public init(_ elements: [Element]) {
        storage = elements
    }
    
    public mutating func push(_ element: Element) {
        storage.append(element)
    }
    
    @discardableResult
    public mutating func pop() -> Element? {
        return storage.popLast()
    }
    
    public func peek() -> Element? {
        return storage.last
    }
    
    public var isEmpty: Bool {
        return peek() == nil // or storage.isEmpty
    }
}

 

시간복잡도

• 삽입 O(1)
• 삭제 O(1)
• 검색 O(n)

삭제나 삽입시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간복잡도는 늘 O(1) 의 시간복잡도를 가집니다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때까지 수행을 해야하므로 O(n) 의 시간 복잡도를 가집니다.

 

 

참고 및 이미지 출처 : https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

 

 

Extension - CustomDebugStringConvertible

CustomDebugStringConvertible을 사용하면 print()했을 때 결과를 커스텀할 수 있습니다.

비포

extension Stack: CustomDebugStringConvertible {
    public var debugDescription: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
    }
}

애프터

 

 

Extension - ExpressibleByArrayLiteral

ExpressibleByArrayLiteral를 사용하면 배열의 형태로 초기화할 수 있습니다.

비포

extension Stack: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        storage = elements
    }
}

애프터