[Swift] Stack이란?

Stack이란 무엇인가에 대해 배워보며, Swift를 활용하여 알고리즘/자료구조에 대해 알아볼 예정입니다.
기존에 강의들은 C++혹은 Python, JAVA로 많이 구현되어있어 자료 찾기가 어려웠으나, 금번에 괜찮은
페이지를 찾아 번역을 해보면서, 그 내용들도 습득해볼 예정입니다.

https://github.com/raywenderlich/swift-algorithm-club

raywenderlich/swift-algorithm-club

Stack이란?

Stack이란 배열과 같다. 다만 기능이 좀 제한된 배열이라고 볼 수 있다. 왜냐하면 Stack의 경우는 오직 세 가지 일 밖에 처리하지 못한다.

• Push : Stack의 맨 뒤(top)에 새 원소를 추가한다.
• Pop : 맨 뒤의 원소를 제거한다.
• peek : 제거하지 않고, 맨 뒤 원소를 추출해낸다.

그렇다면 왜 배열이 아닌 제한된 Stack을 사용할까? 왜냐하면 많은 알고리즘들에서는 어느 시점에 임시 List에 객체를 추가한 다음, 나중에 이 List에서 객체를 다시 꺼내는 일이 필요하기 때문이다. 또한 이러한 객체들을 추가/삭제하는데 순서가 중요할 때가 많다.

Stack은 LIFO(Last In - Frist Out)의 방식을 제공한다. 가장 먼저 추가한 요소가, 제거할 때에 처음으로 해당되게 되는 것이다. (유사한 자료구조로는 FIFO(First in - First Out)을 따르는 queue가 있다.)

예를 들어, Stack에 숫자를 push하여 추가해보자.

stack.push(10)

지금까지 Stack은 [ 10 ] 이다. 다음 숫자를 넣어보자.

stack.push(3) 

이제 Stack은 [ 10, 3 ] 이다. 숫자를 계속 넣어보자.

stack.push(57)

이제 Stack은 [ 10, 3, 57 ] 이다. 새로 추가 되는 원소들이 뒤에 붙는 것을 확인해볼 수 있다.
이제 pop하여 숫자를 꺼내보자.

stack.pop()

위 코드를 실행하면 57을 반환한다. 왜냐하면 가장 최근에 push된 숫자이기 때문이다.
pop을 수행했기 때문에 stack은 [ 10, 3 ]이 되게 된다. 한 번 더 실행해보자.

stack.pop()

이번에는 3을 반환한다. 만약 stack이 비어있을 경우에 pop을 실행하게 되면 nil 혹은 에러 메시지리를 표시한다.

Stack은 Swift에서 쉽게 만들 수 있다. Stack은 그저 배열 주변을 덮고 있는 것으로 push,pop 등 stack의 맨 뒤(top) 요소들에 대해 접근이 가능하도록 해준다.

Stack의 정의에 대해서 보고 이해해보자.

public struct Stack<T> { fileprivate var array = [T]() public var isEmpty: Bool { return array.isEmtpy } public var count: Int { return array.count } public mutating func push(_ element: T) { array.append(element) } // T일수도 있고 앞서 말한 것 처럼 nil 반환이 가능하기에 옵셔널로 표현 public mutating func pop() -> T? { return array.popLast() } public var top: T? { return array.last } }

우선 stack이 빈 값인지 아닌지를 나타내는 isEmpty가 있고, 갯수를 셀 수 있는 count 프로퍼티가 있다.
추가적으로 mutating이 들어간, 즉 Stack의 값을 바꾸겠다는 것을 의미하는 push와 pop을 볼 수 있다.
push의 경우 새 element를 받아 appending한다. 어디에? 맨 앞이 아니라 맨 뒤에! 배열의 시작 부분에 값을 추가하는 것은 O(n) 만큼의 비용이 든다. 왜냐하면, 기존에 존재하는 배열 원소들을 메모리로 옮겨두어야 하기 때문이다. 끝에 붙이는 경우는 O(1) 만큼의 비용이 소요된다. 배열의 크기에 상관 없이 항상 동일한 시간이 소요된다.

pop의 경우는 push와 달리 전달인자가 없다. 왜냐? 꺼낼 수 있는 것은 Stack의 마지막 값이기 때문이다.
또한 빈 Stack에 대해서 pop을 실행할 수 도 있기에 ?를 붙여 옵셔널로 표현한 것을 볼 수 있다.

그리고 마찬가지로 Stack의 가장 끝 값을 보여주는 top또한 내부에 값이 없을 수 있기에 ?를 붙여 옵셔널로 표현해준 것을 확인해볼 수 있다.

Stack에 대한 재밌는 사실이 있다. 함수나 메서드를 사용할 때, CPU는 반환 주소(retrun adress)를 stack에 배치한다. 그리고 호출이 종료되면, CPU는 반환 주소를 사용하여 다시 호출자에게 응답한다. 그렇기 때문에 끝이 없는 재귀 함수(recursive function)을 사용하면 CPU 스택의 공간이 부족해짐에 따라, 이른바 "Stack overflow"가 발생하게 된다.

스택오버플로..? 항상 우리가 질문을 많이하고 답변을 많이 받는 곳이기도 하다. 질문을 하면(메서드 사용) 글이 생기고(반환주소) 그리고 그 글에 답변을 하여(반환주소 사용하여 호출자에게 응답) 문제를 해결하는 것이 stack 구조와 유사하고, 너무 많은 질문들이 있어 stack overflow라는 이름으로 짓지 않았을까 싶다...! 그저 추측일 뿐이고, 항상 stack overflow나 구글에 많은 도움을 받고 있다..!


끄읕