[자료구조] Queue(Deque) 구현

이 글은 자료구조라고 해야하는지, 알고리즘이라고 해야하는지 모르겠지만 일단 자료구조라고 했다.

 

앞선 글에서도 많이 언급한 것처럼 Swift에는 Queue(Deque)가 없어서 구현을 직접해야한다.

알고리즘 문제를 풀 때 시간초과 같은 오류가 발생하지 않기 위해서는?

 

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? {
    	return isEmpty ? nil : array[head]
    }

    var last: T? {
    	return isEmpty ? nil : 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로 포인터처럼 작동한다.

가장 앞 쪽을 의미하며 Swift에서 removeLast()는 O(1)의 시간 복잡도를 갖기 때문에 문제가 되지 않고, 앞쪽을 삭제할 때가 주의해야한다.