큐(Queue)

[최종 수정일 : 2017.05.19]

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

큐(Queue)

큐(queue)는 뒤에 새로운 항목을 삽입하고 맨 앞의 항목을 제거만 할 수 있는 목록입니다. 이것은 큐에 추가(enqueue)한 첫번째 항목이 큐에서 빼내는(dequeue) 첫번째 항목인 것을 보장합니다. 첫번째로 들어오고, 첫번째로 사용하기!

왜 이것이 필요할까요? 글쎄요, 많은 알고리즘 중에 객체를 임시 목록에 추가하고 나중에 목록에서 꺼내는 것을 원합니다. 종종 이러한 객체를 추가하고 삭제하는 순서가 중요합니다.

큐(queue)는 FIFO(선입선출: first-in, first-out) 순서를 가집니다. 첫번째 삽입했던 요소가 제일 먼저 빠져나갑니다. 그것이 옳습니다! (비슷한 데이터 구조체는 Stack이며, LIFO(후입선출: last-in first-out) 입니다)

다음은 숫자를 큐에 넣는 예제입니다.

queue.enqueue(10)

큐는 이제 [10]입니다. 큐에 다음 숫자를 추가 합니다.

queue.enqueue(3)

큐는 이제 [10,3]입니다. 숫자 하나 더 추가합니다.

queue.enqueue(57)

큐는 이제 [10, 3, 57]입니다. 큐의 앞쪽에서 첫번째 요소를 가져오기 위해 큐에서 꺼내(dequeue)봅시다.

queue.dequeue()

처음 삽입된 숫자이기 때문에10을 반환합니다. 큐는 이제 [3, 57]입니다. 모두 한곳으로 이동됩니다.

queue.dequeue()

이것은 3을 반환하며, 다음에 큐에서 꺼내오면 57을 반환합니다. 큐가 비어있으면, 큐에서 꺼내오기는(dequeuing) nil을 반환하거나 일부 구현에서는 오류 메시지를 제공합니다.

주의
큐는 항상 최고의 선택이 아닙니다. 목록에 항목들을 추가하고 제거하는 순서가 중요하지 않는 경우, 큐(queue) 대신에 스택(stack)을 사용할 수 있습니다. 스택은 간단하고 더 빠릅니다.

코드

Swift에서 큐(queue)를 단순하게 구현하면 다음과 같습니다. 큐는 enqueue, dequeue, 맨 앞에 있는 항목을 볼수 있도록(peek) 배열을 래핑(wrapper)합니다.

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
  }
}

이 큐는 잘 동작하지만, 최적화 되어있지는 않습니다.

큐에 넣는(enqueuing) 것은 배열의 맨 끝에 추가하는 것은 배열의 크기와 상관없이 항상 동일한 시간이 소요되기 때문에O(1) 수행입니다.

배열에 항목들을 추가하는 것이 왜 O(1) 또는 일정한 시간(constant-time) 수행하는지 궁금할 것입니다. 그것은 Swift의 배열에는 항상 끝에 빈 공간이 있기 때문입니다. 다음을 수행하면 :

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

배열은 실제로 다음과 같이 보일 수 있습니다.

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

여기에서 xxx는 예약되어 있지만 아직 채워지지않은 메모리 입니다. 배열에 새 요소를 추가하면 다음에 사용되지 않은 구역(spot)을 덮어씁니다(overwrites).

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

이것은 한곳에서 다른 곳으로 일정한 시간(constant-time)동안 메모리를 복사한 결과입니다.

배열의 끝에는 사용되지 않는 구역(spots)의 수가 제한되어 있습니다. 마지막 xxx가 사용되면, 다른 항목을 추가할때, 배열은 더 많은 공간을 만들기 위해 크기를 변경해야 합니다.

크기 변경은 새로운 메모리를 할당하고 기존 모든 데이터를 새로운 배열에 복사하는 것을 포함합니다. 이것은 상대적으로 느린 O(n) 과정입니다. 이것은 가끔씩 발생하기 때문에, 배열의 끝에 새 요소를 추가하는 시간은 여전히 평균 O(1) 또는 O(1) 분할상환(amortized) 입니다.

큐에서 꺼내는 것은 다른 이야기입니다. 큐에서 꺼내는(dequeue) 것은, 배열의 시작부분(begining)에서 요소를 제거합니다. 이것은 모든 남은 배열 요소들이 메모리에서 이동되어야 하기때문에 언제나 O(n)으로 수행합니다.

예제에서, 첫번째 요소 "Ada"를 꺼내오고 "Ada"의 위치에 "Steve"를, "Steve"위치에 "Tim"을, "Tim"의 위치에 "Grace"를 복사합니다.

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

이렇게 모든 요소들을 메모리에서 이동하는 것은 언제나 O(n)으로 수행합니다. 큐를 간단히 구현하면, 큐에 넣는것은(enqueuing) 효율적이지만, 큐에서 꺼내오는것은(dequeueing) 무언가 더 원하게 됩니다..

더 효율적인 큐(A more efficient queue)

큐에서 꺼내는 것을 효율적으로 만들기 위해, 추가적인 여유 공간을 확보할 수 있지만 이번에는 배열의 앞쪽에 있어야 합니다. 우리는 Swift에 내장된 배열이 지원하지 않기 때문에 이 코드를 스스로 작성해야 합니다.

핵심 아이디어는 항목을 대기열에서 제거할때마다 이며, 배열의 내용을 앞쪽으로 (느리게) 이동하지 않지만 배열의 항목의 위치가 비어있는 것으로 표시합니다. (빠르다) 
"Ada"를 큐에서 꺼내오면, 배열은 다음과 같습니다 :

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

"Steve"를 큐에서 꺼내온 뒤에, 배열은 다음과 같습니다 :

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

앞에 있는 빈 구역(spots)이 결코 재사용되지 않기 때문에, 나머지 요소들을 앞쪽으로 이동하여 배열을 주기적(periodically)으로 정리(trim)할 수 있습니다.

[ "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대신에 T?타입의 객체를 저장합니다. head 변수는 배열의 가장 앞쪽에 있는 객체 인덱스 입니다.

새로운 기능 대부분은 dequeue()입니다. 큐에서 항목을 꺼낼때, 배열에서 객체를 제거하기 위해 제일 먼저 array[head]를 nil로 설정합니다. 그리고나서, 다음 항목이 맨 앞이 되어야 하기 때문에 head를 증가시킵니다.

다음과 같이 출발합니다.

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

이렇게 됩니다

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

그것은 슈퍼마켓에서 계산대의 사람들이 금전 등록기(cash register)를 향해 앞으로 섞이지 않는것 같지만, 금전 등록기는 큐에서 나가게 됩니다.

앞쪽의 빈 구역들(spots)을 결코 제거하지 않으며 요소를 큐에 넣고 요소들을 큐에서 꺼낼때 배열은 계속 커질것입니다. 배열을 주기적으로 정리하려면 다음을 수행합니다.

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

처음에는 빈 배열의 비율을 전체 배열 크기의 비율로 계산합니다. 배열의 25%이상이 사용되지 않으면, 낭비된 공간을 잘라냅니다. 그러나, 배열이 작으면 항상 크기를 변경하지 않으며, 배열을 정리하기 전에 배열이 최소한 50개의 요소가 있어야 합니다.

주의
이러한 숫자들은 갑자기(out of thin air) 뽑았습니다 - 이것은 앱의 동작에 따라 조절할 필요가 있습니다.

이것을 플레이그라운드에서 테스트하려면, 다음을 수행하세요.

var q = Queue<String>()
q.array                   // [] empty 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)으로 수행합니다.

이것도 보세요(See also)

큐를 만드는 많은 방법이 있습니다. linked list, circular buffer, heap을 사용해서 대신 구현합니다.

이러한 테마의 변형은 dequeue이며, 양쪽 끝에서 enqueue하고 dequeue할수 있고, priority queue는 가장 중요한 항목을 항상 맨 앞으로 큐를 정렬합니다.