스택

스택은 한 쪽에서만 자료를 넣고 뺄 수 있는 자료구조이다. 스택의 연산은 LIFO(Last In First Out, 선입선출)을 따른다.

스택은 2가지 필수적인 연산이 있다.

• push: 스택의 최상위에 요소를 추가하는 연산
• pop: 스택의 최상위의 요소를 제거하는 연산

인터페이스를 두가지 연산으로 제한한다는 것은, 자료의 추가와 제거를 자료구조의 한 쪽에서만 할 수 있도록 제한한다는 것을 의미한다.

스택은 프로그래밍 전반적으로 눈에 띄게 사용되는데 다음과 같은 경우가 있다.

• iOS에서, 내비게이션 스택은 뷰컨트롤러를 뷰에서 push, pop을 통한 화면전환을 사용한다.
• 메모리 할당에서 스택은 아키텍처적인 수준으로 사용된다. 지역 변수 할당이 스택에 의해 관리된다.
• 탐색과 정복 알고리즘, 미로에서 길찾기 같은 알고리즘에서, 스택은 백트래킹을 하는데 사용된다.

구현

import Foundation

public struct Stack<T> {
    private var storage: [T] = []
    
    public init() { }
    
    public var isEmpty: Bool {
        return storage.isEmpty
    }
    
    public var count: Int {
        return storage.count
    }
    
    public mutating func push(_ element: T) {
        storage.append(element)
    }
    
    @discardableResult
    public mutating func pop() -> T? {
        storage.popLast()
    }
    
    public var top: T? {
        return storage.last
    }
}

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

// Example

var stack = Stack<Int>()

stack.push(5)
stack.push(7)
stack.push(9)

print(stack)

if let poppedElement = stack.pop() {
    assert(9 == poppedElement)
    print("Popped: \(poppedElement)")
    print(stack.top)
}

스택은 트리, 그래프의 탐색에서 중요하게 다뤄진다. 미로를 탐색하는 방법을 생각해보자. 매 시간마다 왼쪽, 오른쪽, 직진 할지 결정해야 한다. 우리는 모든 가능한 결정을 스택에 푸시해 둘 수 있다. 만약에 길이 가로막힌다면, 스택을 통해 지금까지 왔던 길을 백트래킹 할 수 있고, 계속해서 길을 찾을 때 까지 탐색해 나갈 수 있다.

| 참고: Raywenderlich