[자료구조] Swift로 구현하는 Queue (큐)

큐의 개념

 큐는 아래의 그림과 같이 한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 자료구조이다. 이러한 특성을 가리켜 선입선출(FIFO: First In First Out)이라고 한다. 

 대표적인 예로 마켓에서 계산을 위해 계산대 앞에서 줄을 서서 기다리고 있는 사람들을 떠올리면 된다. 가장 먼저 도착한 사람이 먼저 계산을 할 수 있고 마지막에 도착하는 사람은 제일 끝에서 자신의 차례를 기다린다.

 

 큐에는 선형큐, 원형큐 그리고 우선순위 큐등 여러 종류가 있는데 여기서는 가장 기본적인 선형큐에 대해서 알아본다.

 

큐에서 사용되는 연산

  큐에서 사용되는 연산의 종류는 다음과 같다.

• count : 큐에 들어있는 자료의 개수
• isEmpty : 큐가 비어있는 지를 체크하기 위한 연산 
• enqueue : 큐에 새로운 자료를 삽입하는 연산이다. 큐의 뒤쪽에 새로운 자료를 삽입한다.
• dequeue : 큐에서 자료를 삭제하는 연산이다. 큐의 앞쪽에서 자료를 꺼내온다.

 

 스위프트의 배열은 가장 앞에 있는 자료를 삭제하는 removeFirst() 메서드와 배열의 뒤에 자료를 삽입하는 append(_:) 메서드를 제공한다. 따라서 큐는 간단하게 배열을 사용하여 구현할 수 있다.

 

Swift로 구현한 큐 

struct Queue<T> {
    private var queue: [T] = []
    
    // 큐에 담겨 있는 자료의 개수
    var count: Int {
        return queue.count
    }
    
    // 큐가 비어있는지를 체크하기 위한 연산 프로퍼티
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    // 배열의 append(_:) 연산을 사용하여 큐의 끝에 자료 삽입
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    // 큐가 비어있다면 nil을 반환 - 큐에 자료가 있다면 배열의 removeFirst() 메서드를 사용하여 앞에 있는 자료 삭제
    mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

 

 배열에 있는 메서드를 사용하면 어렵지 않게 큐를 구현할 수 있다. 하지만 여기에는 한 가지 문제점이 있다. 큐에 자료를 삽입하는 enqueue(_:)의 경우 배열의 마지막에 자료를 삽입하기 때문에 시간 복잡도는 O(1)이 된다. 그렇기 때문에 자료 삽입에는 문제가 없다.

 

 하지만 큐에서 자료를 삭제하기 위해 사용한 배열의 removeFirst()의 경우에는 시간 복잡도가 O(N)이 된다.

출처 : 애플 개발자 문서(https://developer.apple.com/documentation/swift/array/2884646-removefirst)

 배열은 메모리에 자료를 연속적으로 저장한다. 그렇기 때문에 removeFirst()를 사용하여 배열의 가장 앞에 있는 자료를 삭제할 경우 뒤에 있는 모든 자료를 앞으로 한 칸씩 이동하는 작업이 뒤따른다. 그렇기 때문에 시간 복잡도가 O(N)이 되는 것이다. dequeue 작업의 시간 복잡도를 어떻게 개선할 수 있을까?

 

 

dequeue의 효율성을 개선한 큐

 dequeue를 효율적으로 수행하기 위해 큐에 Head를 두어 실제로 데이터를 삭제하지 않고 dequeue 연산이 수행될 때마다 현재 Head가 가리키고 있는 배열의 값을 nil로 설정한 후 Head를 한 칸씩 옮겨가는 것이다. 이를 그림으로 보면 다음과 같다.

 

 이렇게 실제로는 배열에서 데이터를 삭제하지 않고 Head를 사용하여 반환해야 하는 데이터의 인덱스 값을 가지고 있음으로서 O(1)의 시간 복잡도로 dequeue() 작업을 수행할 수 있다. 

 

 하지만, 계속 배열의 nil로 설정된 부분을 가지고 있는 것은 메모리의 낭비로 이어진다. 따라서 적당한 때에 큐에서 dequeue된 자료들을 제거해주는 작업을 수행해야 한다. 이는 환경에 맞추어 적당한 때에 작업이 수행되도록 설정해 주면 되는데 여기에서는 배열에 적어도 50개의 요소가 있고(배열의 크기가 작을 경우에는 낭비되는 공간을 무시해도 크게 문제가 없기 때문에), 이 중 배열의 25% 이상이 쓰이지 않게 되면 nil로 설정된 부분들을 제거해 주는 작업을 하도록 구현할 것이다.

 

 이와 같은 개념을 사용하여 구현한 코드는 다음과 같다.

struct Queue<T> {
    private var queue: [T?] = [] // 배열에 nil을 설정할 수 있기 때문에 T에서 T?로 자료형을 변경한다.
    private var head = 0 // dequeue 연산시 사용되는 head 포인터
    
    // 큐에 담겨 있는 자료의 개수
    // 배열의 개수에서 head를 빼주어야 한다.
    var count: Int {
        return queue.count - head
    }
    
    // 큐가 비어있는지를 체크하기 위한 연산 프로퍼티
    // count 연산 프로퍼티가 0일 경우 큐가 비어있다고 볼 수 있다.
    var isEmpty: Bool {
        return count == 0
    }
    
    // 배열의 append(_:) 연산을 사용하여 큐의 끝에 자료 삽입
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    // 큐가 비어있다면 nil을 반환 - 큐에 자료가 있다면 배열의 removeFirst() 메서드를 사용하여 앞에 있는 자료 삭제
    mutating func dequeue() -> T? {
        guard head < queue.count, let element = queue[head] else { return nil }
        
        // 현재 head가 가리키고 있는 배열의 element를 nil로 설정하고 head 포인터를 이동시킨다.
        queue[head] = nil
        head += 1
        
        let percentage = Double(head) / Double(queue.count)
        if queue.count > 50, percentage > 0.25 { // 배열의 비어있는 요소가 많아질 경우 비어있는 부분을 제거해주는 작업을 한다.
            queue.removeFirst(head)
            head = 0
        }
        
        return element
    }
}

 

 배열의 비어있는 요소들이 많아지면 결국 removeFirst(_:)를 사용하여 배열의 요소들을 잘라내기 때문에 O(N)의 시간이 걸린다고 생각할 수 있겠지만 이는 매번 일어나지 않고 특정 조건을 만족시켰을 때 한 번 수행되므로 평균적으로 dequeue 작업은 O(1)의 시간복잡도를 가진다.

 

 

References

- https://babbab2.tistory.com/84

- https://github.com/raywenderlich/swift-algorithm-club/tree/master/Queue

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

- https://velog.io/@suitepotato/00004