[Algorithm] Queue 구현 Swift

Swift로 Queue 구현에 관한 두 가지 방법을 기록합니다. 

 

큐를 구현하는 이유는 다음과 같다.

1. Swift에서는 Queue를 지원해주지 않는다.

2. 배열 하나만을 이용해서 큐를 구현할 수 있지만 효율성이 떨어져 다음과 같은 방법을 사용한다.

    -> why? append()를 이용해서 enqueue하고 removeFirst()로 dequeue하는데 removeFirst()의 복잡도가 O(n)이다.

 

1. 인덱스를 이용한 큐 구현

struct Queue1<T> {
    var q = [T]()
    var index = 0
    
    var count: Int { q.count - index }
    
    var isEmpty: Bool { q.count == index }
    
    var first: T? { index < q.count ? q[index] : nil }
    
    var last: T? { index < q.count ? q.last : nil }
    
    mutating func enqueue(_ value: T) {
        q.append(value)
    }
    
    mutating func dequeue() -> T? {
        if index < q.count {
            let now = q[index]
            index += 1
            return now
        } else {
            return nil
        }
    }
}

 

배열 q에서 dequeue할 때,  removeFirst()를 이용해서 값을 꺼내지 않고 인덱스 값을 증가시키면서 인덱스가 가리키는 q의 요소를 리턴함으로써 시간을 줄이는 방법이다.

index가 가리키는 q의 요소가 큐의 첫 번째 요소가 된다. 그래서 큐의 크기를 구할 때도 q의 실제 크기에서 인덱스만큼 뺀 값을 리턴한다. isEmpty, first, last도 같은 방법이다.

 

 

2. 두 스택(배열)을 이용한 큐 구현

struct Queue<T> {
    var left = [T]()
    var right = [T]()
    
    var count: Int { left.count + right.count }
    
    var isEmpty: Bool { left.isEmpty && right.isEmpty }
    
    var first: T? { right.isEmpty ? left.first : right.last }
    
    var last: T? { left.isEmpty ? right.first : left.last }
    
    mutating func enqueue(_ value: T) {
        left.append(value)
    }
    
    mutating func dequeue() -> T? {
        if right.isEmpty {
            right = left.reversed()
            left.removeAll()
        }
        return right.popLast()
    }
}

 

두 배열을 스택으로 이용하여 구현하는 방법이다. left배열은 enqueue의 역할을 하고 right배열은 dequeue의 역할을 한다.

아래 그림과 같이 removeFirst()를 사용하지 않고 복잡도가 O(1)인 append()와 popLast()를 이용해서 구현한다.

 

또한, dequeue할 때 right가 비어있을 때 left에서 요소를 가져오는데 반대 방향으로 바꿔주어야 한다. 반대로 바꾸는게 이해가 안 간다면 직접 그려보면서 시뮬레이션하면 이해가 갈 것이다. 그리고 reversed()의 복잡도가 O(1)이어서 가능한 방법이다.

 

부족한 점은 피드백해주시면 감사하겠습니다!