스택(Stack)

[최종 수정일 : 2017.05.19]

원문 : https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack

스택(Stack)

스택(stack)은 배열과 같지만, 기능이 제한되어 있습니다. 새로운 요소를 스택의 맨 위에 추가하는 밀어넣기(push)와, 맨 위의 요소를 제거하는 꺼내기(pop), 그리고 빼가지 않고서 맨 위의 요소를 들여다보기(peek)만 할 수 있습니다.

왜 이것을 사용할까요? 글쎄요, 많은 알고리즘 중에서 어떤 시점에 임시 목록에 객체를 추가한 다음 나중에 목록에서 객체를 꺼내는 것을 원합니다. 종종 이러한 객체들을 추가하고 제거하는 순서가 중요합니다.

스택은 LIFO(후입선출: last-in first-out) 순서를 가집니다. 마지막에 넣었던 요소가 꺼낼때 첫번째로 빠져나갑니다. (매우 비슷한 데이터 구조는 Queue이며, FIFO(선입선출: first-in first-out)입니다)

예를 들어, 스택에 숫자 하나를 밀어넣습니다.

stack.push(10)

스택은 이제 [10]입니다. 다음 숫자를 밀어넣습니다.

stack.push(3)

스택은 이제 [10, 3]입니다. 숫자 하나 더 밀어넣습니다.

stack.push(57)

스택은 이제 [10, 3, 57]입니다. 스택에서 맨 위에 있는 숫자를 꺼내 봅시다.

stack.pop()

이것은 가장 최근에 밀어 넣은 숫자이기 때문에 57을 반환합니다. 스택은 다시 [10, 3] 입니다.

stack.pop()

이것은 3을 반환합니다. 스택이 비어있으면, 가져오기는(popping) nil을 반환하거나 일부 구현에서는 오류 메시지(stack underflow)를 제공합니다.

Swift에서 스택을 만드는 것은 쉽습니다. 스택은 push, pop, 스택의 맨 위 요소를 볼수 있도록 배열을 래핑(wrapper)합니다.

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의 스택 공간이 부족하면 - 절대 종료하지 않는 재귀(recursive) 함수에서 - stack overflow가 발생합니다.