구현 > BFS/DFS > 그리디 > 정렬 > DP > 이진탐색 > 최단경로 > 그래프

스택Stack

배열과 비슷하다
push, pop, peek 만 가능하다
LIFO(나중에 들어온게 먼저 나간다)

• 삽입의 시간복잡도: O(n)
• 삭제의 시간복잡도: O(1)

struct Stack {
    fileprivate var array: [String] = []

	var isEmpty: Bool {
    	return array.isEmpty
    }
    
    var count: Int {
    	return array.count
    }

    //항상 배열의 맨 뒤에 원소를 추가한다 O(1)
    mutating func push(_ element: String) {
        array.append(element)
    }

    //마지막 원소를 제거한다
    mutating func pop() -> String? {
        return array.popLast()
    }

    func peek() -> String? {
        return array.last
    }
}

var rwBookStack = Stack()
rwBookStack.push("3d game")  //Optional("3d game")
print(rwBookStack.peek())
rwBookStack.pop()
print(rwBookStack.pop())  //nil

mutating

구조체와 열거형은 값타입인데
값타입의 프로퍼티들은 인스턴스의 메소드 내에서 수정할 수 없습니다
수정하고 싶으면 mutating 키워드를 사용해야 합니다.

CustomStringConvertible

스위프트에 이미 만들어져 있는 프로토콜인데 테스트를 용이하게 해준다

extension Stack: CustomStringConvertible {
  
  //프로토콜을 따르기 위해 반드시 구현해야하는 프로퍼티 description
  var description: String {
    
    let topDivider = "---Stack---\n"
    let bottomDivider = "\n-----------\n"

	//joined(separator:)를 통해 
    //["3D Games by Tutorials", "tvOS Apprentice"] 이렇게 되어있으면
    //"3D Games by Tutorials\ntvOS Apprentice" 이렇게 바뀐다
    let stackElements = array.reversed().joined(separator: "\n")
    
    return topDivider + stackElements + bottomDivider
  }
}

var rwBookStack = Stack()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)

결과는 아래와 같다

---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------

---

방금 만든 스택 구조체에서는 문자열만 사용할 수 있다
그렇기 때문에 제네릭을 사용해서 다시 만들어보자

Generics

struct Stack<Element> {
	fileprivate var array: [Element] = []
    
    mutating func push(_ element: Element) {
    	array.append(element)
    }
    
    mutating func pop() -> Element? {
    	return array.popLast()
    }
    
    func peek() -> Element? {
    	return array.last
    }

}

제네릭으로 바뀜에 따라 수정해야하는 부분들

//description 프로퍼티를 수정해야한다.
//제네릭을 사용하게 되면 합치게 되는 값이 문자열이라는 보장이 없기 때문에 map을 통해 문자열로 변환해주는 것이다.
let stackElements = array.reversed().joined(separator: "\n")에서
let stackElements = array.map{ "\($0)" }.reversed().joined(separator: "\n")로

//String이 아니라 Person같은 사용자 정의 객체도 가능하다
var rwBookStack = Stack()에서
var rwBookStack = Stack<String>으로

재귀함수를 계속 호출하면 스택의 주소를 계속 리턴하기 때문에 스택 오버플로우가 발생한다.

총정리

struct Stack<Element> {
    fileprivate var array: [Element] = []
    
    var isEmpty: Bool {
        return array.isEmpty
    }
    
    var count: Int {
        return array.count
    }
    
    mutating func push(_ element: Element) {
        array.append(element)
    }
    
    mutating func pop() -> Element? {
        return array.popLast()
    }
    
    func peek() -> Element? {
        return array.last
    }

}

extension Stack: CustomStringConvertible {
  
  //프로토콜을 따르기 위해 반드시 구현해야하는 프로퍼티 description
  var description: String {
    
    let topDivider = "---Stack---\n"
    let bottomDivider = "\n-----------\n"
    let stackElements = array.map{ "\($0)" }.reversed().joined(separator: "\n")
    
    return topDivider + stackElements + bottomDivider
  }
}

var rwBookStack = Stack<String>()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)

---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------

출처
https://www.raywenderlich.com/800-swift-algorithm-club-swift-stack-data-structure

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