Stack

---

Stack은 가장 마지막에 들어간 값이 가장 먼저 나오는 자료구조이다.

📌 LIFO : Last-in, First-out 선입선출 구조, 마지막에 들어온 값이 먼저 나가는 구조

push로 배열의 마지막에 데이터가 추가되고 pop으로 배열의 마지막 데이터가 삭제된다.

구현방법

push()

Stack 배열의 맨 뒤에 값을 삽입한다.

pop()

Stack 배열에서 맨 뒤의 값을 삭제한다.
가장 마지막에 들어온 값을 삭제한다.

isEmpty()

Stack 배열이 비어있는지를 검사한다.
pop()을 하는 경우 배열이 비어있다면 에외처리를 해주는 등의 역할에 사용된다.

☝🏻 Swift에서는 popLast()라는 메소드를 자체적으로 지원하므로 popLast() 를 사용하여 쉽게 구현할 수 있다.

popLast() 말고도 removeLast() 를 사용할 수도 있다.
이때 차이점은 만약 Stack에서 삭제하고자 하는 데이터가 없다면 popLast()는 옵셔널이기 때문에 nil을 리턴한다.
그러나 removeLast()는 컴파일 에러가 발생하게된다.
따라서 popLast()를 사용하면 따로 isEmpty()를 활용한 예외처리를 해줄 필요가 없어진다.

코드

struct Stack<Element> {
    var stack: [Element] = []
    
    var count: Int {
        stack.count
    }
    var isEmpty: Bool {
        stack.isEmpty
    }
    mutating func push(_ i: Element) {
        stack.append(i)
    }
    mutating func pop() -> Element? {
        return isEmpty ? nil: stack.popLast()
    }
}

위 경우에는 popLast()가 removeLast()로 대체되어도 상관이 없다.
그러나 popLast()만을 사용하는 경우 아래와 같은 코드도 가능하다.

struct Stack<Element> {
    var stack: [Element] = []

    var count: Int {
        stack.count
    }
    mutating func push(_ i: Element) {
        stack.append(i)
    }
    mutating func pop() -> Element? {
        return stack.popLast()
    }
}

Stack의 시간 복잡도

Stack의 시간복잡도는 push, pop 모두 O(1)을 가진다.
push, pop을 하게되면 맨 뒤의 데이터를 push 또는 pop하기 때문에 늘 O(1)을 갖게된다.

참고

---

Apple Developer Documentation