스위프트 알고리즘 클럽 번역, 스택(Stack)
스택
✔︎ 이 글은 Swift Algorighm Club 의 문서를 번역한 글입니다.
스택
스택은 한정된 기능을 갖는 배열과 같다. 스택의 맨 꼭대기에 새로운 요소를 추가하기 위해서 푸시(push) 를, 꼭대기부터 요소를 제거하기 위해서 팝(pop)을, 꼭대기의 요소를 제거하지 않고 확인하기 위해서 피크(peek) 를 한다.
이게 왜 필요할까? 많은 알고리즘에서 당신은 어느 순간, 일시적인 리스트에 값을 추가하고 싶을 것이고, 나중에 그 값을 리스트로부터 꺼내오고 싶을 것이다. 때때로 이 값들을 추가하고 제거하는 순서가 중요하다.
스택은 후입선출(LIFO-Last In First Out)의 순서로 구성된다. 마지막에 푸시한 요소가 다음 팝의 첫 번째 요소가 된다. (이와 아주 비슷한 자료구조가 있는데, 선입선출-FIFO-First In First Out의 큐가 그 것이다.)
예시
예를 들어, 스택에 수를 푸시해보자.
stack.push(10)
스택은 [ 10 ] 이 된다. 하나 더 푸시해보면,
stack.push(3)
스택은 [ 10, 3 ] 이 된다. 또 하나 푸시해보면,
stack.push(57)
스택은 [ 10, 3, 57 ] 이 된다. 여기서 꼭대기 숫자를 스택에서 팝 해보자.
stack.pop()
이는 57 을 반환하는데, 우리가 가장 최근에 푸시한 값이 57이기 때문이다. 스택은 다시 [ 10, 3 ] 이 된다.
stack.pop()
이번엔 3 을 반환하고, 쭉 같은 방식으로 계속된다. 스택이 비어있을 때 팝을 한다면 nil 을 반환하거나, 어떤 구현 코드에서는 “스택 언더플로우(stack underflow)” 와 같은 오류 문자를 출력할 것이다.
구현
스위프트로 스택을 만드는 건 쉽다. 푸시 하고, 팝 하고, 맨 꼭대기 요소를 볼 수 있게 하는 배열을 보기 좋게 만든 것 뿐이다.
(원문엔 stack 이 wrapper 라고 한다. 프로그래밍에서 이 단어를 어떻게 쓰는지 검색했을 때, 일반적으로 다른 클래스의 인스턴스를 가지는 클래스를 말할 때 쓴다고 한다. 래퍼의 주요 목적은 객체를 다른 방식으로 제공하는 것이기 때문이다. 관련 링크 : https://stackoverflow.com/questions/3293752/where-and-how-is-the-term-used-wrapper-in-programming-what-does-it-help-to-do)
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) {
return array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
mutating
스위프트에서 값 타입의 속성은 기본적으로 인스턴스 메서드 내에서 수정할 수 없다. 여기서 값 타입은 구조체와 열거형이다(레퍼런스 타입은 클래스). 값 타입의 속성을 수정하려면 인스턴스 메서드에서 mutating 키워드를 붙여야 한다. 위에서 구현한 스택은 구조체, 즉 값 타입이기 때문에 인스턴스 메서드인 push 와 pop 에 mutating 을 붙여 사용 가능하게 만들었다.
여기서 주목할 점은 푸시를 통해 새로운 요소가 배열의 처음이 아닌 끝에 추가된다는 것이다. 배열의 처음에 추가하는 것은 배열에 존재하는 모든 요소들을 메모리상에서 옮겨줘야 하기 때문에 O(n) 만큼의 비용이 든다. 마지막에 추가하는 것은 배열의 크기와 관계 없이 언제나 같은 시간이 걸리므로 O(1) 만큼이 든다.
스택에 대한 재밌는 사실 : 당신이 함수나 메소드를 호출할 때마다 CPU 는 스택이라는 공간에 반환 주소를 저장한다. 함수가 끝났을 때 CPU가 그 반환 주소를 사용해 호출자에게 다시 돌아간다. 끝나지 않는 재귀함수와 같이 엄청나게 많은 함수들을 호출했을 때 CPU 스택에 공간이 없기 때문에 “스택 오버플로우”라 불리는 현상을 보게 된다.
댓글남기기