Swift로 작성해보는 기본 자료구조 - Stack, Queue

Swift로 작성하는 Stack

struct Stack<T> {
    
    var isEmpty: Bool {
        return self.list.isEmpty
    }
    
    var top: T? {
        return self.list.last
    }
    
    mutating func push(_ item: T) {
        self.list.append(item)
    }
    
    mutating func pop() -> T? {
        return self.list.popLast()
    }
    
    private var list = [T]()
}

Swift로 간단히 작성해본 Stack이다.

특별히 어려운 부분은 없으며 포인트가 되는 부분은 다음 두 가지다.

1. 제네럴한 아이템을 관리할 수 있도록 제너럴 <T>를 사용하였다.

2. 값 타입인 Struct로 작성했기 때문에 push 와 pop 함수에 mutating 키워드를 붙여주었다.

---

Swift로 작성하는 Queue - Array를 사용하여

struct Queue<T> {
    
    var isEmpty: Bool {
        return self.list.isEmpty
    }
    
    var front: T? {
        return self.list.first
    }
    
    mutating func enqueue(_ item: T) {
        self.list.append(item)
    }
    
    mutating func dequeue() -> T? {
        guard self.isEmpty == false else { return nil }
        return self.list.removeFirst()
    }
    
    private var list = [T]()
}

Swift로 간단히 작성해본 Queue다.

Stack 때와 마찬가지로 Array를 사용하여 구현하였다. 특별히 눈여겨볼 곳은 dequeue 부분에서 isEmpty 체크를 선행하는 부분이다. Swift의 Array에 제공되는 removeFirst() 함수의 경우에는 만약 FirstItem이 없다면 런타임 오류가 발생하기 때문이다.

구현 자체는 간단하지만 LIFO의 Stack과 달리 FIFO의 Queue는 Array로 구현했을 때 Time complexity 측면에서 개선의 여지가 생기게 된다. Big-O를 따져보자. enqueue의 경우 배열의 가장 마지막 위치에 append할 뿐이므로 O(1)이다. 그러나 dequeue의 경우에는 first item을 삭제하고 나머지 원소들을 각각 한 칸씩 이동시키므로 O(n)이 된다. (Stack의 경우는 Array로 구현했을 때 push, pop 모두 O(1)이다.)

그렇다면 위 코드에서 어떻게 좀 더 시간 복잡도를 개선할 수 있을까? 현재의 head를 가리키는 변수를 따로 관리하며 dequeue가 발생할 때마다 그 변수만 변경해주는 방법이 있다(마치 포인터를 옮기듯). 물론 충분히 dequeue가 발생한 시점에서는 Array에서의 쓸데없는 공간(head가 가리키는 인덱스보다 앞에 위치한 인덱스들)을 비워주는 처리도 해야할 것이다.

---

Swift로 작성하는 Queue - Linked List를 사용하여

struct QueueWithLinkedList<T> {
    
    var isEmpty: Bool {
        return self.linkedList.isEmpty
    }
    
    var front: T? {
        return self.linkedList.head?.value
    }
    
    mutating func enqueue(_ item: T) {
        self.linkedList.appendValue(item)
    }
    
    mutating func dequeue() -> T? {
        guard self.isEmpty else { return nil }
        return self.linkedList.removeHead()
    }
    
    private var linkedList = LinkedList<T>()
}

이번에는 Array 대신 Linked List를 사용하여 Queue를 구현해보았다. Linked List 라는 자료구조의 특성 상 enqueue와 dequeue 모두 O(1)로 가능하다.

참고로 Swift에서 Linked List 자료구조는 기본으로 제공하지 않기 때문에, 아래와 같이 오직 Queue 구현을 위한 Linked List를 따로 작성했다.

class LilnkedListNode<T> {
    let value: T
    weak var previous: LilnkedListNode?
    var next: LilnkedListNode?
    
    init(value: T) {
        self.value = value
    }
}

struct LinkedList<T> {
    
    var isEmpty: Bool {
        return self.head == nil
    }
    
    mutating func appendValue(_ value: T) {
        let new = LilnkedListNode<T>(value: value)
        
        if self.isEmpty {
            self.head = new
        }
        
        self.tail?.next = new
        new.previous = self.tail
        
        self.tail = new
    }
    
    mutating func removeHead() -> T? {
        guard let head = self.head else { return nil }
        return self.removeNode(head)
    }
    
    mutating func removeNode(_ node: LilnkedListNode<T>) -> T {
        node.previous?.next = node.next
        node.next?.previous = node.previous
        
        if self.head === node {
            self.head = nil
        }
        if self.tail === node {
            self.tail = nil
        }
        
        node.previous = nil
        node.next = nil
        
        return node.value
    }
    
    private(set) var head: LilnkedListNode<T>?
    private var tail: LilnkedListNode<T>?
}