[Swift] 큐(Queue) 구현하기

큐

선입선출(FIFO) : 먼저들어온 놈이 먼저 나가는 자료구조

Swift 에서의 구현

struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

그러나 이 방법은 dequeue시에 element들이 자리를 당기는 과정에서 O(n)의 시간복잡도가 발생한다.

 

Dequeue에 효율적인 큐

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

이 큐는 dequeue시 반환되어야 하는 element의 index를 들고 있으며, 당겨오는 과정이 없기 때문에 O(1)의 시간 복잡도를 가진다.

그리고 queue의 50개 쌓였을 때 dequeue된 element들을 remove해준다.

 

출처 : https://babbab2.tistory.com/84 (소들이님 티스토리)

 

---

간단한 큐 구현

추가로, 좀 더 간단한 큐 구현을 소개한다.

push, pop 둘다 시간복잡도 O(1)이다.

struct Queue<T> {
    var array: [T] = []
    var index = 0
    
    mutating func push(_ element: T) {
        array.append(element)
    }
    
    mutating func pop() -> T? {
        guard index < array.count else {
            return nil
        }
        let element = array[index]
        index += 1
        return element
    }
}