[Swift] Queue 구현해보기

[Swift] Queue 구현해보기

---

Swift에서는 Queue 자료구조를 기본적으로 지원하지 않는다.

Array의 배열의 맨 앞 원소를 지워주는 removeFirst()를 지원하긴 하지만 O(N) 시간복잡도를 갖는다.

 

제네릭 타입을 가지고, 시간 복잡도가 O(1)인 Queue를 구현해보자.

 

struct Queue<T> {
    private var inputStack = [T]()
    private var outputStack = [T]()
    
    mutating public func append(_ x: T) {
        inputStack.append(x)
    }
    
    mutating public func pop() -> T? {
        var top: T?
        while !(inputStack.isEmpty) {
            let x = inputStack.popLast()!
            outputStack.append(x)
        }
        top = outputStack.popLast()
        return top
    }
    
    mutating public func head() -> T? {
        while !(inputStack.isEmpty) {
            print("head() - inputStack = \(inputStack)")
            let x = inputStack.popLast()!
            outputStack.append(x)
            print("head() - outputStack = \(outputStack)")
        }
        return outputStack.isEmpty ? nil : outputStack[outputStack.endIndex-1]
    }
    
    public func isEmpty() -> Bool {
        return inputStack.isEmpty && outputStack.isEmpty
    }
}

Queue는 구조체로 선언했으므로, 내부의 inputStack/outputStack 프로퍼티를 함수에서 변경시키기 위해선 <mutating> 키워드가 필요하다.

 

앞서 말했듯, removeFirst()는 O(N)의 시간복잡도를 가진다.

요소를 append(_:) 시킨 뒤, pop()을 할 때 inputStack에서 역순인 popLast() 한 값을 outputStack에 넣어준다.

자연스럽게 outputStack에 들어가게 되는 순서는 역순으로 되니, 가장 최근 값이 마지막 outputStack에 담기게 된다.

 

즉, queue에 [1,2,3,4] 데이터가 있다고 하면

queue.head() 함수 호출 시 시간에 따라 inputStack / outputStack을 출력해보면

 

outputStack에 역순으로 쌓이게 되어 head를 가지기 위해 popLast()만 수행해도 되는 것을 알 수 있다.