Stack 구현 (Array, LinkedList)

Stack

• LIFO: Last In First Out
• 리스트의 제한된 형태: 넣고 빼기가 리스트의 한쪽 끝에서만 가능
• Notation
  • PUSH
  • POP
  • TOP: 맨 위의 값 리턴.
• 종류
  • Array based
  • link based

Array based Stack

struct stack<T> {
    var elemensts: [T] = []

    var isEmpty: Bool {
        elemensts.isEmpty
    }

    mutating func push(element: T) {
        elemensts.append(element)
    }

    @discardableResult
    mutating func pop() -> T? {
        elemensts.popLast()
    }

    func peek() -> T? {
        elemensts.last
    }

}

• 단순 배열을 활용한 스택 구현방법으로 아마 가장 보편적으로 많이 쓰이는 방법일 것입니다. 크게 어려운 점은 없으므로 설명을 추가로 하지는 않겠습니다.

Linked based Stack

class Node<T> { // class인 이유? next포인터를 위함.
    var value: T
    var next: Node?

    init(value: T, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

struct Stack<T> {

    var top: Node<T>?

    var count: Int = 0

    mutating func push(_ value: T) {
        count += 1
        top = Node(value: value, next: top)
    }

    mutating func pop() -> T? {
        count = max(0, count - 1)
        var popValue = top?.value
        top = top?.next
        return popValue
    }

        mutating func clear() {
        count = 0
        top = nil
    }

    func peak() -> T? {
        top?.value
    }
}

Stack & PUSH

• 앞서 말했듯이 데이터를 넣고 빼는 동작이 한쪽 끝에서만 일어나기 때문에 연결리스트로 구현했을 때에 이점이 있습니다. 연결리스트로 구현하게 되면 push, pop, top 연산이 모두 O(1)이기 때문입니다.
• PUSH를 할 때에 top에 할당할 새로운 노드를 만드는데, 이 때 next pointer에 기존 top을 가르키게끔 해서 위의 그림과 같은 과정으로 삽입이 이루어집니다.

POP

• pop은 top을 다음 것으로 넘깁니다.

top = top?.next

• 다음으로 넘기면서 기존의 top이였던 노드는 reference count가 0되는 순간 메모리에서 해제되게 됩니다.

CLEAR

• clear는 top을 nil로 바꿔버리고 count도 0으로 초기화시켜버리면 끝입니다.

COUNT

• 만약 count변수가 없다면 linked list를 통해서 모두 순회해야하기 때문에 O(n)의 시간복잡도가 생기므로, count변수로 따로 관리해주어야합니다.