[Swift] Queue (Deque) 구현

최근 Swift로 알고리즘 문제를 해결하고 있습니다.

그런데 Swift에는 Queue(Deque)가 없어 종종 불편할 때가 있더라구요

그래서 한번 직접구현해봤습니다.

 

Swift로 구현한다는 것에 목적이 있는 포스팅이기 때문에 Queue와 Deque에 대한 설명은 생략하겠습니다.

 

참고 : https://velog.io/@seri_ous/Swift-%ED%81%90-Swift-Algorithm-Club-%EB%B2%88%EC%97%AD

---

구현

class Queue<T> {
    var array: [T?]
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    var first: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }

    var last: T? {
        if isEmpty {
            return nil
        } else {
            return array.last!
        }
    }

    init(_ array: [T?] = [T?]()) {
        self.array = array
    }

    func append(_ element: T) {
        self.array.append(element)
    }

    func removeFirst() -> T? {
        guard head < array.count, let element = array[head] else { return nil }
        array[head] = nil
        head += 1

        return element
    }

    func removeLast() -> T? {
        return array.removeLast()
    }
}

해당 Queue의 핵심은 가장 앞쪽을 의미하는 값인 head입니다.

앞쪽을 삭제해야할 일이 생기면 array[head]를 nil로 만들고 head를 1 올려서 처리합니다.

 

Swift의 Array는 기본적으로 removeLast에 대해서는 O(1)의 시간복잡도를 가지기 때문에 이부분은 따로 처리해줄 필요가 없습니다.

Array 양쪽을 O(1)로 확인하고 삭제할 수 있는 Queue(=사실상 Deque)가 완성되었습니다.

 

알고리즘 문제중에는 Queue가 필요한 문제가 많아서

Deque로서 활용하기보단 Queue로 활용하는 경우가 더 많을 것 같네요!