[자료구조] Queue 큐 with Swift

 

🔎 큐(queue)

큐(queue)는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 선형 자료 구조이다.

허나! Swift에서는 Queue를 기본 자료구조로 제공하지 않고 있다.

 

이는 array를 사용해 구현해볼 수 있다.

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()
    }
}

 

하지만 배열로 구현을 하다 보면 효율면에서 위 방식은 문제가 될 수 있다.

 

 

무슨 문제냐!

 

 

배열에서 가장 마지막 element를 삭제하는 것은 맨 뒤 자신만 삭제하면 되니까 O(1)로 문제되지 않는다.

 

하지만 만약 처음 element를 삭제한다면 element가 하나씩 앞으로 당겨지는 과정이 있다.

➡️ O(n) 효율 문제 발생!

 

 

 

 

✨ 시간 복잡도 개선해보기

dequeue시 배열 앞당기는 작업 최소화를 위해 실제 배열의 Head를 삭제하지 않고

현재 Head를 가리키고 있는 포인트를 변경 시켜서 더이상 필요 없는 dequeue된 element는 nil 로 만들기

 

struct Queue2<T> {
    private var queue: [T?] = []
    private var front: Int = 0
    
    public var frontValue: Int {
        return self.front
    }
    
    public var size: 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? {
        guard front <= size, let element = queue[front] else { return nil }
        queue[front] = nil
        front += 1
        return element
    }
}

 

 

 

 

📌 참고 : https://jeong9216.tistory.com/350