Stack

- 선형 자료구조
- LIFO (후입선출)

 

선형 자료구조의 일종. Last In First Out (LIFO) 방식으로, 나중에 들어온(push) 원소가 먼저 나온다.(pop)

접시를 위로 쌓아놓은 형태를 떠올리면 쉽다. 따라서 스택의 앞에 원소를 넣는 것은 O(n)이고 스택의 뒤에 추가하는 것은 O(1)의 시간복잡도를 갖는다.

참고로 CPU는 function 이나 method의 return 주소를 스택에 넣는데, 재귀 함수 등과 같이 함수가 종료되기 전에 너무 많은 함수를 호출해 CPU의 스택이 부족해지면 "stack over flow"가 발생한다.

Implement

Swift는 사실상 내부적으로 Stack을 이미 지원하고 있다고 볼 수 있다.

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
  }
}

참고

JaeYeopHan/Interview_Question_for_Beginner