참고한 블로그 🙏

[Swift] 큐

큐를 구현하는 두 가지 방법

파이썬은 queue를 내장하고 있는 한편 Swift는 순열, 조합과 마찬가지로 직접 구현해서 사용해야 합니다.

🤔 그냥 Array을 사용하면?

dequeue (큐에서 데이터 꺼내기)를 구현하기 위해 배열에 removeFirst를 사용하게 되면 시간초과가 날 가능성이 높습니다. dequeue는 O(1)의 시간복잡도를 가져야 하는데 반해 배열의 removeFirst는 O(n)의 시간복잡도를 가집니다. 따라서 그냥 Array를 사용하면 안됩니다.

커서 큐: 내부에 dequeue될 index를 가지고 있는 방법

커서 큐는 내부에 index를 가지고 있습니다. 해당 index의 역할은 지금 dequeue될 차례인 data의 인덱스 값입니다. 해당 index는 dequeue될 때마다 1씩 증가하기 때문에 0부터 차례대로 deueue할 수 있습니다.

커서 큐의 장점은 큐에 데이터를 isEmpty, enqueue, dequeue 모두 O(1)을 보장한다는 것입니다. 단점은 data가 실제로 삭제되는 것이 아니기 때문에 데이터가 많이 들어오는 경우 메모리 사용량이 지나치게 커질 수 있습니다.

//✅ 커서 큐
struct Queue<T> {
    var data = [T]() //👉 element를 저장하는 배열
    var index = 0 //👉 queue의 맨 앞을 가리키는 커서
    
    //✅ 비었는지 확인
    var isEmpty: Bool {
        return !(data.count > index) //👉 count의 시간복잡도 O(1)
        //👉 index가 data의 갯수보다 작다면? = 아직 데이터가 있다.
            // 마지막 data가 dequeue되면 index가 data.count와 같아진다는 것을 생각하면 이해하기 쉽다.
    }
    
    //✅ 큐에 넣기
    mutating func enqueue(_ element: T) {
        data.append(element)
    }
    
    //✅ 큐에서 빼기
    mutating func dequeue() -> T {
        //⭐️ defer문을 활용해서 return된 이후에 index를 1 늘려준다.
        defer {
            index += 1
        }
        return data[index] //👉 현재 index를 return한다.
    }
}

더블 스택 큐: 스택 2개를 활용하는 방법

더블 스택 큐는 말 그대로 2개의 스택을 활용하는 방법입니다. 하나는 입력용이고 그 스택을 뒤집어서 출력용 큐를 만드는 방식이죠. 배열에서 popLast는 항상 O(1)을 보장하기에 활용할 수 있는 방법입니다.

커서 뷰와 대비해서 장점은 queue에서 빠진 데이터는 메모리서 지워지기 때문에 메모리 관리를 더 효율적으로 할 수 있습니다. 하지만 단점은 시간 복잡도가 O(n)인 removeAll가 존재한다는 것입니다.

//✅ 더블 스택큐
struct Queue<T> {
    var input = [T]() //👉 입력용 큐 (원래 큐의 순서대로 데이터가 존재)
    var output = [T]() //👉 출력용 큐 (원래 큐의 반대 순서로 데이터가 존재)
    
    // 빈 큐인지 확인
    var isEmpty: Bool {
        return input.isEmpty && output.isEmpty
    }
    
    // 큐에 남은 데이터 세기
    var count: Int {
        return input.count + output.count
    }
    
    // 큐에 데이터 넣기
    mutating func enqueue(_ element: T) {
        input.append(element)
    }
    
    // 큐에서 데이터 빼기
    mutating func dequeue() -> T {
        if output.isEmpty {
            output = input.reversed() //👉 시간복잡도 O(1)
            input.removeAll() //❗️ 시간복잡도 O(n), n의 input의 길이
        }
        return output.popLast()!
    }
}

참고로 reserve는 O(1)의 시간 복잡도를 가집니다.

what's the time complexity of swift reversed?