이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.
스택은 배열과 비슷하지만 기능이 제한적이다. 스택의 맨 위에 새 엘리먼트를 추가하려면 push를 사용하고, 맨 위의 엘리먼트를 제거하려면 pop을 사용하며, 맨 위의 엘리먼트를 제거하지 않고 확인하려면 peek을 사용한다.
왜 이런 기능이 필요할까? 많은 알고리즘에서 특정 시점에 임시 목록에 객체를 추가하고 나중에 다시 제거해야 하는 경우가 있다. 이때 객체를 추가하고 제거하는 순서가 중요한 경우가 많다.
스택은 LIFO(Last-In First-Out) 순서를 제공한다. 가장 마지막에 push한 엘리먼트가 다음 pop에서 가장 먼저 제거된다. (매우 유사한 자료구조인 큐는 FIFO(First-In First-Out) 순서를 따른다.)
예를 들어, 스택에 숫자를 push해 보자:
stack.push(10)
스택은 이제 [ 10 ]
이다. 다음 숫자를 push하자:
stack.push(3)
스택은 이제 [ 10, 3 ]
이다. 한 번 더 숫자를 push하자:
stack.push(57)
스택은 이제 [ 10, 3, 57 ]
이다. 스택의 맨 위 숫자를 pop해 보자:
stack.pop()
이렇게 하면 57
이 반환된다. 가장 최근에 push한 숫자이기 때문이다. 스택은 다시 [ 10, 3 ]
이 된다.
stack.pop()
이렇게 하면 3
이 반환된다. 스택이 비어 있으면 pop은 nil
을 반환하거나, 어떤 구현에서는 "stack underflow"라는 오류 메시지를 반환한다.
스택은 Swift에서 쉽게 만들 수 있다. 단순히 배열을 감싸는 래퍼로, push, pop, 그리고 스택의 맨 위 엘리먼트를 확인하는 기능만 제공한다:
public struct Stack<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
push는 새 엘리먼트를 배열의 끝에 추가한다. 배열의 시작 부분에 삽입하는 것은 O(n) 연산으로 비용이 많이 들지만, 끝에 추가하는 것은 O(1) 연산이다. 배열의 크기에 관계없이 항상 동일한 시간이 소요된다.
스택에 대한 재미있는 사실: 함수나 메서드를 호출할 때마다 CPU는 반환 주소를 스택에 저장한다. 함수가 종료되면 CPU는 그 반환 주소를 사용해 호출자로 돌아간다. 그래서 너무 많은 함수를 호출하면(예: 끝나지 않는 재귀 함수) CPU 스택의 공간이 부족해져 "스택 오버플로우"가 발생한다.
Swift Algorithm Club의 Matthijs Hollemans가 작성함