[Swift] Queue 구현해보기

Swift에서는 Queue에 대해서 지원을 하지 않습니다.

때문에 사용자가 직접 구현해줘야 하는데요.

Queue를 알기 전에 간단하게 Stack에서 알아보겠습니다.

Stack이란 무엇인가요?

Stack은 LIFO(Last In First Out) 방식으로 동작하는 자료구조입니다.

예를 들어 편의점 냉장고에 음료를 채울 때, 앞에서부터 채우면 나중에 채운 음료가 먼저 나가고 처음 넣은 음료가 가장 마지막에 나가게 됩니다.

Swift에서는 주로 Array를 사용하여 Stack을 대체해 사용할 수 있습니다.

Array에 데이터를 append할 때, 데이터는 배열의 뒤에 쌓이게 됩니다.

Array에서는 popLast() 또는 removeLast() 메서드를 사용하여 가장 마지막에 추가된 데이터를 제거할 수 있습니다.

Queue란 무엇인가요?

Queue는 Stack과는 다르게 FIFO(First In First Out) 방식으로 동작하는 자료구조입니다.

예를 들어 편의점 냉장고에 음료를 채울 때, 앞에서부터 채우는 것이 아니라 뒤에서부터 채워주는 건데요. 이렇게 하면 먼저 들어간 음료가 먼저 나오게 됩니다.

queue를 간단하게 구현해보면 다음과 같습니다.

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

위 코드를 보면 뭔가 이상합니다.

이렇게 구현할꺼면 그냥 Array의 removeFirst()를 사용하는것과 다를게 없어보이기 때문인데요.

Queue는 먼저 들어간 데이터를 먼저 제거해줘야 하므로 Array의 removeFirst()를 사용하면 될것 같지만 removeFirst()를 사용하면 시간복잡도가 O(n)이 되기 때문에 사실상 구현하는 의미가 퇴색됩니다.

Array에서 removeFirst()를 사용하면 0번째 배열이 제거되므로 뒤에 있는 배열을 앞으로 한 칸 씩 당겨오는 과정이 필요하고 이 때 배열의 길이만큼 계산을 하기 때문에 오버헤드가 발생하므로 다른 방식으로 Queue의 dequeue()를 구현해 줘야 합니다.

이때, dequeue()에 사용할 Array의 메서드를 선택하기 위해 메서드의 작동 방식을 살펴보겠습니다.

popLast()

mutating func popLast() -> Self.Element?
Complexity
O(1)

removeLast()

@discardableResult
mutating func removeLast() -> Self.Element
Complexity
O(1)

popLast()와 removeLast()의 시간 복잡도는 1로 매우 빠릅니다.

하지만, popLast()는 배열이 비어있을 경우 nil 값을 반환하며, removeLast()는 배열이 비어있을 경우 런타임 에러가 발생합니다. 또한, @discardableResult 속성을 적용하여 반환값을 무시할 수 있습니다.

removeFirst()

@discardableResult
mutating func removeFirst() -> Self.Element
Complexity
O(n), where n is the length of the collection.

removeFirst()의 경우 removeLast()와 마찬가지로 시간 복잡도는 1이며 리턴값을 무시할 수 있습니다.

다만, 배열이 비어있을 경우 런타임 에러가 발생합니다.

stack을 2개 사용하고, 런타임 에러가 발생하지 않는 popLast()를 사용해 queue를 구현해 보겠습니다.

struct Queue<T> {
    private var inbox: [T] = []
    private var outbox: [T] = []

    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }

    mutating func enqueue(_ input: T) {
        inbox.append(input)
    }
    
    @discardableResult
    mutating func dequeue() -> T? {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()
    }
}

inbox에 데이터를 추가해주고 dequeue 할 때 outbox가 비어있으면 inbox를 뒤집어서 outbox에 넣어주고 inbox를 비워줍니다.

이 때 reversed()와 removeAll()의 시간복잡도는 O(1)입니다.

이 방법 외에도 head를 통해 현재 head를 이동시켜주는 방법도 있는데 이 방법은 소들님께서 정리를 잘 해주셔서 링크를 첨부하겠습니다.

Uploaded by N2T

Jimmy의 개발 노트