Section II: Elementary Data Structures - Stack

스택 데이터 구조는 개념상 객체의 물리적 스택과 동일합니다. 스택에 항목을 추가하면 스택 맨 위에 배치됩니다. 스택에서 항목을 제거하면 항상 맨 위에 있는 항목이 제거됩니다. LIFO 라고 하죠 Last In First Out

 

책에서는 아래 4개를 예시로 두었네요. 

• pancakes
• books
• paper
• cash

Stack operations

스택은 두 가지 필수 작업만 수행합니다.

- push : 스택 맨 위에 요소를 추가합니다.

- pop : 스택 맨 위 요소를 제거합니다.

 

한 쪽에서만 요소를 추가하거나 제거할 수 있습니다. LIFO(후입선출) 데이터 구조입니다.

 

- iOS 기준으로는 Navigation 에서 stack 구조를 사용합니다.

- 메모리 할당은 아키텍처 수준에서 스택을 사용합니다. 지역 변수에 대한 메모리도 스택을 사용하여 관리됩니다.

- 미로에서 경로 찾기와 같은 검색 및 정복 알고리즘은 스택을 사용하여 역추적을 용이하게 합니다.

 

라고 되어 있는데 저는 네비게이션 말고는.. 와닿지가 않네요 일단.. 계속 공부해 보겠습니다.

 

 

Implementation

스택을 구현해봅니다.

 

플레이 그라운드에 아래 소스코드를 적습니다.

public struct Stack<Element> {

  private var storage: [Element] = []

  public init() { }
}

extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

 

이때 스토리지를 어떤 타입으로 선택하는 것이 중요합니다.

배열은 append 및 popLast를 통해 한쪽 끝에서 일정한 시간에 삽입 및 삭제를 제공하기 떄문에 적합합니다.

이 두가지로 LIFO 를 구현할 수 있습니다.

 

debugDescription를 정의해 줌으로써 스택의 구조를 표현합니다. map 으로 String으로 전환 후 리버스로 배열을 뒤집어 주고 스트링 배열을 \n사용하여 병합하여 한번에 출력합니다.

 

 

push 와 pop 구현

public mutating func push(_ element: Element) {
  storage.append(element)
}

@discardableResult
public mutating func pop() -> Element? {
  storage.popLast()
}

 

여기서 @discardableResult 은 결과에 대해서 리턴이 있는데 사용하지 않을 때 warning 을 띄웁니다.

그걸 warning 하지말라고 할 때 사용합니다.

 

 

 

예제를 구현해 봅니다.

 

example(of: "using a stack") {
  var stack = Stack<Int>()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.push(4)

  print(stack)

  if let poppedElement = stack.pop() {
    assert(4 == poppedElement)
    print("Popped: \(poppedElement)")
  }
}

 

아웃풋

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4

 

push, pop 은 시간복잡도 O(1)를 갖습니다.

 

 

Non-essential operations

스택을 더 쉽게 사용할 수 있도록 하는 몇 가지 기능들이 있습니다.

public func peek() -> Element? {
 storage.last
}

public var isEmpty: Bool {
  peek() == nil
}

peek 은 내용을 변경하지 않고 스택의 맨 위 요소를 리턴합니다.

 

 

Less is more

기존 어레이를 스택으로 변환하는 초기화 함수를 추가합니다.

public init(_ elements: [Element]) {
  storage = elements
}

 

예제

example(of: "initializing a stack from an array") {
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
}

 

더 나아가서 배열 리터럴에서 스택을 초기화할 수 있도록 만들 수 있습니다.

추가

extension Stack: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    storage = elements
  }
}

 

 

스택은 트리와 그래프를 검색하는 문제에서 중요합니다.

미로를 통해 길을 찾는 것을 상상해보세요.

왼쪽, 오른쪽 또는 직선 결정 지점에 올 때마다 가능한 모든 결정을 스택에 푸시할 수 있습니다.

막다른 골목에 도달하면 스택에서 튀어 나와 탈출하거나 다른 막 다른 골목에 닿을 때까지 계속해서 뒤로 물러나세요.

 

 

요즘 갤러리 에디터 기능을 개발하고 있는데 히스토리 기능에 스택 데이터 구조를 사용하면 딱일 것 같습니다.!

그럼 스택은 이제 마무리 하겠습니다.

수고하셨습니다.