[Swift][알고리즘][꿀팁] Queue 구현하기

Queue 따로 구현해야 하는 이유?

보통 우리가 Swift에서 Queue를 구현 할 때는 하나의 배열에서 removeFirst()를 이용해 앞에서 빼고 append()를 이용해 뒤로 넣는 방식으로 구현합니다.

하지만, removeFirst()의 경우에는 O(n)의 시간복잡도를 갖기 때문에 많은 양의 원소가 왔다갔다하는 Queue에서 아주 비효율적입니다.

(저는 초반에 큐를 이용하는 BFS문제들에서는 시간초과가 안나오다가 갈수록 모든 문제에서 시간초과가 발생하더라구요!)

자, 우선 전체 코드를 한번 읽어보세요!

보통 일반적인 경우에는 큐를 push, pop, empty()정도만 사용하는 것 같아서 저는 3가지만 간단하게 구현해보았습니다.

아래 코드를 완벽하게 이해하기 위해서 Swift Generic T와 Swift mutating을 구글에서 검색해보고 오시길 권장드립니다.

struct Queue<T>{
    var enqueue: [T] = []
    var dequeue: [T] = []
    
    mutating func push(_ element: T){
        enqueue.append(element)
    }
    mutating func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    func empty() -> Bool{
        return enqueue.isEmpty && dequeue.isEmpty
        
    }
    
}

큐를 생성하는데 왜 2개의 인스턴스변수를 만들어줬을까?

enqueue에는 큐를 삽입할 것이고, dequeue에는 삽입되어 있는 큐들을 거꾸로 저장해 줄 예정이랍니다 ^^

var enqueue: [T] = []
var dequeue: [T] = []

Push()

위에서 말씀드렸듯이 enqueue에 간단하게 삽입해줍니다

mutating func push(_ element: T){
        enqueue.append(element)
    }

Pop()

자, 여기서 헷갈리시는 분이 많으실거 같습니다.

dequeue의 용도는 위에서 말씀드렸듯이 enqueue에 있는 원소들을 거꾸로 저장해줄 것입니다.

왜 거꾸로 저장하는걸까요?

바로, 시간복잡도를 최소화하기 위해서입니다.

swift에서 reversed()함수의 경우 시간복잡도가 O(1)입니다.

이와 같은 점을 이용하기 위해서 우리는 원소들을 거꾸로 저장해줄 것입니다.

저희는 enqueue에만 큐를 삽입해줬기 때문에 처음에는 dequeue가 비어있을 것입니다.

혹은 dequeue에 있는 원소를 모두 꺼냈을 경우에도 dequeue는 비어있을 것입니다.

비어있는 dequeue를 그냥 pop하면 nil을 리턴하게 됩니다.

enqueue에 원소가 더이상 없다면 상관없지만, 만약 있다면 enqueue에 있는 원소들을 거꾸로 가져와야합니다.

그래서 dequeue가 비어있다면 dequeue에 enqueue의 원소들을 거꾸로 저장해주고, enqueue를 비워줍니다.

enqueue를 비워주는 이유는 원소를 빼는 작업은 dequeue에서만 할 것이기 때문에 enqueue에서는 dequeue로 옮긴 원소가 더 이상 필요 없습니다. 그리고 비워주지 않는다면 dequeue에 똑같은 원소가 계속해서 들어가는 대참사가 벌어지겠죠..

mutating func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }

Empty()

마지막으로, 큐의 원소가 비어있으려면 enqueue와 dequeue 모두 빈 상태여야합니다.

func empty() -> Bool{
        return enqueue.isEmpty && dequeue.isEmpty
    }

개발자 조안이