iOS Swift의 자료 구조, 알고리즘에 대해서 알아보자 (4)

 

Stacks

이번에는 기초 자료구조 중에서도 어디에서도 사용되고 있는 개념인 스택에 대해서 알아보도록하자.

스택은 예시를 들어보면 사진과 같이 팬케익이 쌓여있는 느낌으로 볼 수 있다.

 

Stack의 자료구조는 개념적으로 객체의 물리적 스택과 동일하다. 어떤 항목을 스택에 넣으면 스택의 맨 위에 놓이게 되고 스택의 어떤 항목을 제거한다면 항상 가장 위에 있는 항목이 제거된다.

 

스택은 두가지 필수 작업이 존재한다.

• Push : 스택의 최상단에 요소 추가
• Pop : 스택의 최상단 요소를 제거

인터페이스를 이 두가지 작업으로 제한하는 것은 자료구조의 한 방향에서만 추가하거나 제거할 수 있다는 것이다. CS에서 스택은 LIFO(후입선출) 자료구조로 알려져 있다. 가장 마지막에 Push된 요소가 가장 먼저 Pop되어 나가지게 된다.

 

iOS는 네비게이션 스택을 사용해 뷰컨트롤러의 뷰 안밖으로 푸시하거나 팝하는 것으로 사용되고 메모리할당은 아키텍처레벨에서 스택을 사용한다. 지역변수를 저장하는 메모리도 스택을 사용해서 관리하게 된다.

public struct Stack<Element> {
	private var storage: [Element] = []
	public init() { }
}

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

이 코드는 스택의 백업 스토리지를 정의한 내용이다. 스택에 적합한 스토리지 유형을 선택하는 것은 매우매우 중요하다. 배열은 append와 popLast 를 이용해 한쪽 끝에서 한쪽 끝까지 상수시간의 삽입과 삭제가 이루어진다. CustomDebugStringConvertible 프로토콜에 필요한 debugDescription의 함수 호출 체인을 위해 3가지 작업을 해야한다.

• stroage.map { ”\\($0)” } 로 문자열에 매핑하는 배열 만들기
• reversed()를 이용해 이전 배열을 뒤집는 새로운 배열을 만들기
• joined(separator:)를 이용해 배열을 문자열로 병함, “\\n” 개행 문자를 이용해 배열의 요소를 분리한다.
  
  

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

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

이를 바탕으로 이렇게 값을 넣으면

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

상단의 내용과 같이 출력되게 된다. 이 경우 push 와 pop은 둘 다 시간복잡도가 O(1) 입니다.

스택을 더 쉽게 사용할 수 있는 유용한 작업들이 있는데

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

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

스택 인터페이스는 종종 peek 작업이 포함된다. peek은 안의 콘텐츠를 변경하지 않고 스택의 상단요소를 살펴보는 것이다.

 

스택의 목적은 데이터에 접근하는 방법의 가짓수를 제한하는 것이다. Collection과 같은 프로토콜을 채택하는 것은 반복자(iterator)와 아래 첨자(subscript) 를 통해 모든 요소를 노출하므로 스택의 목적에 반하는 내용이다.

 

private 저장소를 설정하는 생성자를 작성할 수 있으니 아래와 같이 스택 구현에 추가해보자

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

위 코드는 문자열 스택을 생성하고 최상단 요소인 “D”를 내보낸다. 스위프트 컴파일러는 배열로부터 요소의 타입을 추론할 수 있으므로 Stack<String>대신 Stack을 사용할 수 있다.

 

한단계 더 나아가서 배열 리터럴을 통해 스택을 초기화할 수 있도록 만들 수 있다.

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

example(of: "initializing a stack from an array literal") {
	var stack: Stack = [1.0, 2.0, 3.0, 4.0]
	print(stack)
	stack.pop()
}

위 코드는 Double 스택을 생성하고 최상단의 4.0 값을 내보낸다. 다시 말하면 타입추론을 통해 Stack<Double>를 입력하지 않아도 된다는 것이다!

 

스택은 트리와 그래프를 검색하는 문제에 매우 중요하다. 미로에서 길을 찾는 것을 상상해볼 때 왼쪽, 오른쪽, 직진을 선택해야할 때 마다 할 수 있는 모든 결정을 스택에 저장할 수 있다. 막다른 골목에 도달하면 스택에서 마지막 결정을 pop 하므로써 역 추적할 수 있고, 다른 막다른 골목에 도달하거나 탈출하기 전까지 이를 계속할 수 있다.

 

핵심 요약 Key points

• 스택은 LIFO, 후입선출 자료구조이다.
• 매우 단순하지만 스택은 많은 문제들의 핵심 자료구조이다.
• 스택의 두가지 필수 작업으로, 요소를 추가하는 push 메서드와 요소를 제거하는 pop 메서드가 있다.
  
  

오늘은 아주 기초적인 스택을 조금 더 깊게 앞아보는 내용을 기록해봤다 🙂 요즘 날씨가 안춥고 따듯해서 그런지 마음이 싱숭생숭하다.. 그치만 잘 맘을 다 잡고 다시 가보자!!! 빠이팅