[Swift]Queue 자료구조를 구현해보자

들어가며

Swift는 다른 언어와 다르게 기본적인 자료구조를 제공하지 않는 경우가 많습니다. 따라서, 오늘은 Queue 자료구조를 직접 구현해보도록 하겠습니다.

Queue 자료구조

Queue는 선형적 자료구조로 원소의 삽입 삭제가 FIFO(First-In-First-Out)의 특징을 갖습니다. 대략적으로 도시화하자면 아래와 같죠.

Queue는 원소의 삽입과 삭제가 서로 다른 방향으로 이루어지며 반드시 먼저 삽입된 원소가 먼저 삭제됩니다. Queue는 동적인 메모리 크기를 가지며, 원소의 삽입 삭제는 $O(n)$의 시간복잡도를 갖습니다.

배열을 이용한 Queue 구현

기본적인 Swift의 배열로 Queue와 비슷한 특징을 갖도록 사용할 수 있습니다. 배열은 append() 메소드로 원소를 삽입하고, popFirst()로 원소를 삭제할 수 있으니까요.

struct Queue<T : Comparable> {
    private var data : [T?] = []
    
    public var count : Int {
        return data.count
    }
    
    public var isEmpty : Bool {
        return data.isEmpty
    }
    
    mutating func enqueue(_ element : T) {
        data.append(element)
    }
    
    mutating func dequeue() -> T? {
        guard let element = data[data.indices].popFirst() else { return nil }
        return element
    }
}

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
print(queue.dequeue()!)

>> 1

다만, popFirst()는 ArraySlice, Collection에서 지원하는 메소드이므로 ArraySlice 타입으로 변경해주었습니다.

data[data.indices].popFirst()

이렇게 말이죠.

이렇게 구현된 Queue는 원소 삽입은 $O(1)$이 소요되는 반면에 원소 삭제는 $O(n)$의 시간복잡도가 소요됩니다. 시간복잡도를 더 줄여볼까요??

dequeue가 효율적인 Queue 구현

이전에 구현한 Queue와는 다르게 head를 두어서 head에 해당하는 값을 dequeue로 전달하면 어떨까요?? 그렇게 되면 $O(1)$을 만족할 것입니다.

struct Queue<T : Comparable> {
    private var data : [T?] = []
    private var head : Int = 0
    
    public var count : Int {
        return data.count - head
    }
    
    public var isEmpty : Bool {
        return data.isEmpty
    }
    
    mutating func enqueue(_ element : T) {
        data.append(element)
    }
    
    mutating func dequeue() -> T? {
        guard head < data.count, let element = data[head] else { return nil }
        data[head] = nil
        head += 1
        return element
    }
}

var queue = Queue<Int>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
print(queue.dequeue()!)
print(queue.dequeue()!)
print(queue.dequeue()!)
print(queue.dequeue()!)
>> 1
>> 2
>> 3
>> 4

이렇게 되면 dequeue() 메소드를 실행하게 되면 head가 가르키는 원소가 반환됩니다. 만약, head가 data의 크기보다 작거나 head가 가르키는 원소가 없다면 nil을 반환하게 됩니다.

이렇게 삭제도 $O(n)$의 시간복잡도를 갖는 Queue를 구현했습니다. 하지만, 여전히 dequeue() 메소드를 실행하면 nil이 반환되는 원소를 대체하므로 메모리적으로는 효율적이지 못합니다. 메모리는 해제되지 않기 때문입니다.

메모리까지 효율적인 Queue 구현

dequeue()를 실행하면서 특정 head 이상이 되면 head까지 데이터를 모두 삭제합니다. 그렇게 하면 메모리까지 효율적으로 활용할 수 있습니다.

	...
    mutating func dequeue() -> T? {
        guard head < data.count, let element = data[head] else { return nil }
        data[head] = nil
        head += 1
        if head > 50 {
            data.removeFirst(50)
            head = 0
        }
        return element
    }
    ...

예를 들어, 위의 예제는 50개 이상 삭제되면 50개까지 모두 삭제하고, head를 0으로 변경하게 됩니다. 물론, removeFirst()메소드는 $O(n)$이 소요되지만, 삭제되지만 크기를 무한정으로 늘리는 것은 바람직하지 않기에 효율적으로 메모리를 사용할 수 있습니다. 게다가, 특정 크기 이하는 $O(1)$을 소요하면서 원소 삭제까지 가능합니다.

참고

https://babbab2.tistory.com/84