큐

이 주제는 여기에서 튜토리얼로 다뤄졌다.

큐는 리스트의 뒷부분에만 새로운 항목을 추가하고, 앞부분에서만 항목을 제거할 수 있는 자료구조다. 이렇게 하면 가장 먼저 추가한 항목이 가장 먼저 제거된다. 먼저 온 순서대로 처리하는 방식이다!

왜 이런 구조가 필요할까? 많은 알고리즘에서 객체를 임시 리스트에 추가했다가 나중에 다시 꺼내야 하는 경우가 있다. 이때 객체를 추가하고 제거하는 순서가 중요할 때가 많다.

큐는 FIFO(First-In, First-Out) 순서를 제공한다. 가장 먼저 추가한 항목이 가장 먼저 제거된다. 공평한 방식이다! (비슷한 자료구조인 스택은 LIFO, 즉 Last-In, First-Out 방식이다.)

다음은 큐에 숫자를 추가하는 예제다:

queue.enqueue(10)

이제 큐는 [ 10 ] 상태가 된다. 다음 숫자를 큐에 추가해 보자:

queue.enqueue(3)

이제 큐는 [ 10, 3 ] 상태가 된다. 한 번 더 숫자를 추가해 보자:

queue.enqueue(57)

이제 큐는 [ 10, 3, 57 ] 상태가 된다. 이제 큐의 앞부분에서 항목을 제거해 보자:

queue.dequeue()

이 명령은 10을 반환한다. 가장 먼저 추가한 숫자이기 때문이다. 이제 큐는 [ 3, 57 ] 상태가 된다. 모든 항목이 한 칸씩 앞으로 이동했다.

queue.dequeue()

이 명령은 3을 반환한다. 다음 dequeue 명령은 57을 반환한다. 큐가 비어 있는 상태에서 dequeue를 시도하면 nil을 반환하거나, 어떤 구현에서는 에러 메시지를 보낸다.

참고: 큐가 항상 최선의 선택은 아니다. 리스트에 항목을 추가하고 제거하는 순서가 중요하지 않다면, 큐 대신 스택을 사용할 수 있다. 스택은 더 간단하고 빠르다.

코드

Swift에서 큐를 간단히 구현한 예제다. 배열을 감싸서 enqueue, dequeue, 그리고 맨 앞의 항목을 확인하는 기능을 제공한다:

public struct Queue<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }

  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

이 큐는 잘 동작하지만 최적화되지는 않았다.

enqueue는 O(1) 연산이다. 배열의 끝에 요소를 추가하는 작업은 배열의 크기와 상관없이 항상 동일한 시간이 소요되기 때문이다.

배열의 끝에 요소를 추가하는 작업이 왜 O(1) 또는 상수 시간 연산인지 궁금할 수 있다. Swift에서 배열은 항상 끝에 여유 공간을 두기 때문이다. 다음과 같은 코드를 실행하면:

var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")

배열은 실제로 이렇게 보일 수 있다:

[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]

여기서 xxx는 예약된 메모리이지만 아직 채워지지 않았다. 배열에 새 요소를 추가하면 다음 사용되지 않은 공간을 덮어쓴다:

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]

이는 메모리를 한 곳에서 다른 곳으로 복사하는 작업으로, 상수 시간 연산이다.

배열의 끝에는 사용되지 않은 공간이 제한되어 있다. 마지막 xxx가 사용되고, 또 다른 항목을 추가하려면 배열은 더 많은 공간을 만들기 위해 크기를 조정해야 한다.

크기 조정에는 새 메모리를 할당하고 모든 기존 데이터를 새 배열로 복사하는 작업이 포함된다. 이는 O(n) 프로세스로 상대적으로 느리다. 하지만 이 작업이 가끔 발생하기 때문에 배열의 끝에 새 요소를 추가하는 시간은 평균적으로 여전히 O(1) 또는 "분할 상환" **O(1)**이다.

dequeue의 경우는 다르다. dequeue는 배열의 시작 부분에서 요소를 제거한다. 이는 항상 O(n) 연산이다. 메모리에서 나머지 배열 요소를 모두 이동시켜야 하기 때문이다.

예제에서 첫 번째 요소 "Ada"를 dequeue하면 "Steve"가 "Ada"의 위치로, "Tim"이 "Steve"의 위치로, "Grace"가 "Tim"의 위치로 복사된다:

before   [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
                   /       /      /
                  /       /      /
                 /       /      /
                /       /      /
 after   [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]

메모리에서 이 모든 요소를 이동시키는 작업은 항상 O(n) 연산이다. 따라서 이 간단한 큐 구현에서는 enqueue는 효율적이지만, dequeue는 개선의 여지가 있다...

더 효율적인 큐 구현

큐에서 요소를 제거하는 작업을 효율적으로 만들기 위해, 배열 앞쪽에 여유 공간을 확보하는 방법을 사용할 수 있다. 이 기능은 Swift의 기본 배열에서 지원하지 않기 때문에 직접 구현해야 한다.

핵심 아이디어는 요소를 제거할 때마다 배열의 내용을 앞으로 이동시키는 대신(느림), 해당 위치를 빈 공간으로 표시하는 것이다(빠름). "Ada"를 제거한 후 배열은 다음과 같다:

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]

"Steve"를 제거한 후 배열은 다음과 같다:

[ xxx, xxx, "Tim", "Grace", xxx, xxx ]

앞쪽의 빈 공간은 재사용되지 않기 때문에, 주기적으로 남은 요소를 앞으로 이동시켜 배열을 정리할 수 있다:

[ "Tim", "Grace", xxx, xxx, xxx, xxx ]

이 정리 작업은 메모리를 이동시키는 O(n) 연산이지만, 자주 발생하지 않기 때문에 평균적으로 요소 제거 작업은 O(1) 시간 복잡도를 가진다.

이 버전의 Queue를 구현하는 방법은 다음과 같다:

public struct Queue<T> {
  fileprivate var array = [T?]()
  fileprivate var head = 0
  
  public var isEmpty: Bool {
    return count == 0
  }

  public var count: Int {
    return array.count - head
  }
  
  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    guard head < array.count, let element = array[head] else { return nil }

    array[head] = nil
    head += 1

    let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }
    
    return element
  }
  
  public var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

이제 배열은 T? 타입의 객체를 저장한다. 이는 배열 요소를 빈 공간으로 표시하기 위함이다. head 변수는 배열에서 가장 앞에 있는 객체의 인덱스를 나타낸다.

새로운 기능은 주로 dequeue() 메서드에 구현되어 있다. 요소를 제거할 때, 먼저 array[head]를 nil로 설정해 객체를 제거한다. 그런 다음 head를 증가시켜 다음 요소를 가장 앞으로 이동시킨다.

이 과정은 다음과 같다:

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
  head

이후:

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
        head

이는 마치 슈퍼마켓에서 계산대 앞으로 사람들이 이동하는 대신, 계산대가 큐를 따라 이동하는 것과 같다.

앞쪽의 빈 공간을 제거하지 않으면, 요소를 추가하고 제거할 때마다 배열이 계속 커질 수 있다. 주기적으로 배열을 정리하기 위해 다음 코드를 사용한다:

    let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }

이 코드는 배열 앞쪽의 빈 공간 비율을 계산한다. 배열의 25% 이상이 사용되지 않으면, 낭비되는 공간을 제거한다. 그러나 배열이 작을 때는 매번 크기를 조정하지 않기 위해, 배열에 최소 50개의 요소가 있을 때만 정리 작업을 수행한다.

참고: 이 숫자는 임의로 선택한 값이다. 실제 애플리케이션 환경에 맞게 조정할 필요가 있다.

플레이그라운드에서 테스트하려면 다음 코드를 사용한다:

var q = Queue<String>()
q.array                   // [] 빈 배열

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2

정리 동작을 테스트하려면 다음 줄을 교체한다:

    if array.count > 50 && percentage > 0.25 {

다음과 같이 변경한다:

    if head > 2 {

이제 다른 객체를 제거하면 배열은 다음과 같이 변한다:

q.dequeue()         // "Tim"
q.array             // [{Some "Grace"}]
q.count             // 1

앞쪽의 nil 객체가 제거되고, 배열은 더 이상 공간을 낭비하지 않는다. 이 새로운 Queue 버전은 첫 번째 버전보다 복잡하지 않지만, 요소 제거 작업도 O(1) 시간 복잡도를 가진다. 이는 배열을 어떻게 사용하는지에 대한 이해 덕분이다.

함께 보기

큐를 구현하는 방법은 다양하다. 대표적으로 연결 리스트, 원형 버퍼, 힙 등을 활용할 수 있다.

이와 관련된 변형으로는 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 덱과, 가장 중요한 항목이 항상 앞에 위치하는 정렬된 큐인 우선순위 큐가 있다.

Swift Algorithm Club의 Matthijs Hollemans가 작성함