[Swift 자료구조] 4. Stack 스택 (배열/연결리스트로 구현하기)

Data Structure in Swift (Stack) - Part 3

Swift Algorithm Club: Swift Stack Data Structure

이 글은 위의 두 문서를 기반으로 해석 및 정리한 글입니다.

스택 Stack

스택은 요소를 선형(linear)으로 정리하게 해 주는 자료구조입니다.
스택은 기본적으로 LIFO(Last In First Out) 매커니즘을 통해 요소를 삽입하고 삭제합니다.
이는 가장 나중에 더해진 요소가 가장 먼저 삭제됨을 의미합니다.

스택의 연산

스택은 굉장히 한정된 범위의 연산을 제공한다.

• push() : O(1). 스택에 새로운 요소를 삽입하는 연산
• pop() : O(1). 스택의 맨 위의 요소를 삭제하는 연산
• peek() : 스택의 맨 위의 요소가 무엇인지 조회하는 연산
  • 스택은 요소를 조회하는 기능을 제공하지 않는다. 예외적으로 peek()을 통해 맨 위의 요소가 무엇인지 확인하는 것만 가능하다.

Swift에서의 스택

스택은 거의 모든 프로그래밍 언어에서 사용된다. iOS에서는 다음과 같은 곳에 스택 자료구조가 사용된다.

• UINavigationController가 뷰 컨트롤러들을 push하고 pop할 때
• 지역 변수에 대한 메모리를 할당할 때

❗️ Swift는 스택 자료구조를 기본적으로 제공하지 않으므로, 직접 구현해야 한다.

Swift로 스택 구현하기 - (1) 배열 사용

주석이 없는 전체 코드는 여기에 있습니다. (배열, 연결리스트 구현방식 모두 포함)

struct Stack<Element> {
    fileprivate var array: [Element] = []

    // isEmpty : 스택이 비어있는지 확인
    var isEmpty: Bool {
        return array.isEmpty
    }

    // count : 스택이 몇 개의 요소를 가지고 있는지 확인
    var count: Int {
        return array.count
    }

    // push : 스택 맨 위에 새 요소를 추가함
    mutating func push(_ element: Element) {
        array.append(element)
    }

    // pop : 스택 맨 위의 요소를 제거함
    // 스택이 비어 있을 때 nil 반환
    mutating func pop() -> Element? {
        return array.popLast()
    }

    // peek : 스택 맨 위의 요소가 무엇인지 조회함
    // 역시 스택이 비어 있을 때 nil 반환
    func peek() -> Element? {
        return array.last
    }
}

extension Stack: CustomStringConvertible {
    var description: String {
        let topDivider = "---Stack---\n"
        let bottomDivider = "\n-----------\n"

        let stackElements = array.map { "\($0)" }.reversed().joined(separator: "\n")
        return topDivider + stackElements + bottomDivider
    }
}

• isEmpty : 스택이 비어있는지 확인
• count : 스택이 몇 개의 요소를 가지고 있는지 확인
• push() : 스택 맨 위에 새 요소를 추가함
  • 이 스택은 내부적으로 배열을 사용하므로, pop() 을 통해 배열의 맨 끝에 요소를 추가한다. 그 이유는 배열의 경우 요소를 맨 앞이나 중간에 삽입할 때(O(n)) 에 비해 맨 끝에 삽입하는 것(O(1)) 이 더 빠르기 때문이다.
  • Swift가 제공하는 메서드인 append() 를 사용한다. - O(1)
• pop() : 스택 맨 위의 요소를 제거함
  • 이 스택은 맨 끝에서부터 요소를 추가하므로, 삭제할 때도 맨 끝의 요소를 삭제해야 한다.
  • Swift가 제공하는 메서드인 popLast() 를 사용한다. - O(1)
  • 리턴값이 옵셔널이다 : 스택이 비어 있는 상태에서 pop() 을 하면 nil 을 반환한다.
• peek() : 스택 맨 위의 요소가 무엇인지 조회함
  • 역시 맨 끝의 요소가 무엇인지 조회해 반환하면 된다.
  • Swift가 제공하는 프로퍼티인 .last 를 사용한다. - O(1)
  • 리턴값이 옵셔널이다 : 스택이 비어 있는 상태에서 peek() 을 하면 nil 을 반환한다.
• extension Stack: CustomStringConvertible {...}
  • 스택을 출력(print) 했을 때 보기 쉽게 하기 위해 추가로 구현할 수 있다.
  • reversed() : 스택의 요소들이 배열에 뒤에서부터 저장되어 있으므로, 출력할 때는 최근 요소(맨 뒤의 요소)가 맨 위에 출력되게 하기 위해 사용한다.
  • .joined(separator: "\n") : 요소 사이에 줄바꿈문자(\n) 를 넣어 보기 편하게 한다.
• <Element> : 제네릭 사용
  • 특정 타입의 요소 뿐 아니라 모든 타입에 사용할 수 있게 하기 위해.

Swift로 스택 구현하기 - (2) 연결리스트 사용

연결리스트와 같이 Node의 개념을 사용해 스택을 구현해 본다.

// Node class to hold the data
class Node<T> {

    let value: T
    var next: Node?

    init(value: T) {
        self.value = value
    }
}

// Stack  class to hold the all items
class Stack<T> {

    var top: Node<T>?

    func push(_ value: T) {
        let currentTop = top
        top = Node(value: value)
        top?.next = currentTop
    }

    @discardableResult
    func pop() -> T? {
        let currentTop = top
        top = top?.next
        return currentTop?.value
    }

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

extension Node: CustomStringConvertible {
    var description: String {
        guard let next = next else { return "\(value)" }
        return "\(value)\n" + String(describing: next) // 여기서 연쇄적으로 노드를 String으로 변환
    }
}

extension Stack: CustomStringConvertible {
    var description: String {
        guard let top = top else { return "---- Stack is EMPTY ----" }
        return "---- Stack ----\n" + String(describing: top) + "\n---------------"
    }
}

var stackString = Stack<String>()
print(stackString.pop())

• top : 스택의 최상위 노드를 의미한다.
• push() : 스택 맨 위에 새 요소를 추가함
  • 기존 top 위에 새 노드를 만들어 쌓는다.
• pop() : 스택 맨 위의 요소를 제거함
  • 최상위 노드의 next(nil)를 최상위 노드로 만든 다음, 기존 최상위 노드의 값을 반환한다.
  • 리턴값이 옵셔널이다 : 스택이 비어 있는 상태에서 pop() 을 하면 nil 을 반환한다.
• peek() : 스택 맨 위의 요소가 무엇인지 조회함
  • 현재 최상위 노드 (= top) 의 값을 반환한다
  • 리턴값이 옵셔널이다 : 스택이 비어 있는 상태에서 peek() 을 하면 nil 을 반환한다.
• extension Node: CustomStringConvertible {...}
  • 노드를 출력(print) 했을 때 보기 쉽게 하기 위해 추가로 구현할 수 있다.
  • next가 있으면 value와 next를, 없으면 value를 반환
  • next 또한 Node이므로 next가 있다면 다음 Node도 연쇄적으로 출력하게 된다.
• extension Stack: CustomStringConvertible {...}
  • 스택을 출력(print) 했을 때 보기 쉽게 하기 위해 추가로 구현할 수 있다.
  • top의 값이 있으면 top의 값을, 없으면 비어있다는 문구를 반환한다.
  • top의 값이 있으면 String(describing: top) 를 출력하는데, 이때 top 이 Node이므로 Node의 CustomStringConvertible에 따라 출력된다.
• <Element> : 제네릭 사용
  • 특정 타입의 요소 뿐 아니라 모든 타입에 사용할 수 있게 하기 위해.

Swift로 스택 구현하기 - (1)배열과 (2)연결리스트 비교

import Foundation

let startTime = CFAbsoluteTimeGetCurrent()

var stackString = Stack<String>()
stackString.push("First")
stackString.pop()
stackString.push("Second")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("Third")
stackString.push("First")
stackString.pop()
stackString.push("Second")
stackString.push("Third")

let processTime = CFAbsoluteTimeGetCurrent() - startTime
print(processTime) 

// 0.004179954528808594 - (1) 배열
// 0.0066149234771728516 - (2) 연결리스트

아무 데이터나 넣어서 둘의 성능을 비교해 봤는데, 배열은 보통 0.004초대가 나왔고 연결리스트는 보통 0.006초대가 나왔다.

연결리스트가 더 빠를거라는 내 생각과는 다른 결과였다😮

그래서 큐와는 달리 스택은 반드시 연결리스트를 통해 구현할 필요는 없겠다는 생각이 들었다.

이미 연결리스트를 쓸때와 같은 시간복잡도(O(1))의 메서드를 배열의 메서드와 프로퍼티(append(), popLast(), .last)로 제공하기 때문이다.