Swift로 효율적인 큐 만들기

배경

• 큐 자료구조를 사용할 일이 있어서 제네릭하게 만들던 도중, dequeue 기능을 아래와 같이 구현하였다.

func dequeue() -> T? {
  queue.removeFirst()
}

• 그런데 첫번째 인덱스를 삭제하는 것은 배열을 shift하기 때문에 O(n)의 시간복잡도를 가지지 않을까 생각했다.
  
• 함수 정의의 주석을 살펴보니 예상대로 O(n)의 시간복잡도를 가지고 있었다.
• 따라서 이대로라면 dequeue를 할 때 마다 O(n)번의 연산을 수행하게 되는... 굉장히 비효율적인 큐가 되어버린다.

해결책

• 소들님 블로그에서 힌트를 얻어 아래와 같이 구현해 보았다.
• head를 포인터로 사용해 head가 위치한 인덱스를 큐의 첫 번째 인덱스로 사용하는 방식이다.
• 그러면 dequeue시 head 인덱스만 변경해주면 되기 때문에 O(1)의 시간복잡도를 가진다.
• 다만 실제로는 사라지지 않은 값들이 남아있기 때문에, head의 값이 일정 크기 이상이 될 때 남은 값들을 제거해준다.
  • 이 연산은 O(n)의 시간복잡도를 가진다.
• 따라서 사용하고자 하는 큐의크기에 따라 적절한 값을 정해주는 것이 중요해 보인다!

final class Queue<T> {
    private var queue: [T?] = []
    private var head: Int = 0
    
    func enqueue(_ element: T) {
        guard !isFull else {
            return
        }
        queue.append(element)
    }
    
    /// O(1) 시간 안에 dequeue를 수행하기 위해 head를 포인터로 사용
    func dequeue() -> T? {
        guard !isEmpty, head < queue.count else  {
            return nil
        }
        
        let element = queue[head]
        head += 1
        
        if head > 40 {
            queue.removeFirst(head)
            head = 0
        }
        return element
    }
}