큐 Queue

큐 Queue

큐는 오로지 뒤에서만 새로운 아이템을 삽입할 수 있으며 앞에서 아이템을 제거할 수 있는 리스트입니다. 이러한 규칙은 큐에 삽입한 제일 첫 아이템이 가장 먼저 꺼낼 수 있도록 합니다. 가장 먼저 들어간 것이 가장 먼저 나오는 것이죠!

왜 우리들은 큐가 필요로 할까요? 많은 알고리즘에서 여러분은 객체를 임시 리스트에 넣고 나중에 꺼내는 경우가 많을 것입니다. 또한 여러분이 객체를 추가하고 꺼내고 순서가 중요할 때 그렇습니다.

큐는 FIFO(first-in, first-out) 순서입니다. 여러분이 제일 처음에 삽입한 아이템이 가장 먼저 나오게 된다는 의미입니다.

여기에 숫자를 삽입(enqueue) 하는 예제가 있습니다.

queue.enqueue(10)

큐는 이제 [10]이 됩니다. 다음 숫자를 큐에 추가해봅시다.

queue.enqueue(3)

큐는 이제 [10, 3] 이 되었습니다. 하나를 더 추가해봅시다.

queue.enqueue(57)

큐는 [10, 3, 57]입니다. 큐에서 가장 앞에 있는 원소를 가져와봅시다.

queue.dequeue()

이 메서드는 10을 반환합니다. 왜냐하면 가장 첫 번째로 삽입했던 값이기 때문입니다. 큐는 이제 [3, 57]입니다. 이제 큐의 모든 값은 한 자리씩 이동했습니다.

queue.dequeue()

이번에는 3을 반환합니다. 57이 있던 자리의 옆입니다. 만약 큐가 비었다면, dequeue()메서드는 nil을 반환합니다. 또는 구현에 따라 에러 메시지를 던집니다.

주의 : 큐는 항상 최선의 선택이 아닙니다. 만약 리스트로부터아이템을 넣거나 제거하는 순서가 중요하지 않다면, 큐 대신에 스택(stack)을 사용하세요. 스택은 훨씬 간단하고 빠릅니다.

코드 예제

여기에 스위프트에서 구현한 큐의 예제가 있습니다. 배열을 감싸는 래퍼가 가장 앞의 아이템을 가져옵니다.

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) 만큼의 시간이 소모되는지를 궁금해 하실 것입니다. 왜냐하면 스위프트에서 배열은 항상 마지막에 빈 공간을 가지고 있기 때문입니다.

만약 아래처럼 작성한다면 :

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)이라고합니다.

큐에서 값을 빼내는 것은 이야기가 다릅니다. 값을 빼내기 위해, 우리들은 배열의 앞에서부터 값들을 제거합니다. 이것은 항상 O(n)입니다. 왜냐하면 제거 후에 남은 배열의 원소들이 메모리 상에서 한 칸씩 옆으로 옮겨지게 되기 때문입니다.

이 예제에서는, 첫 원소인 "Ada" 을 빼고 "Steve"를 "Ada" 자리에 복사합니다. 그리고, "Tim"을 "Steve" 대신 위치합니다. 마지막으로, "Grace"가 "Tim"을 대신합니다.

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

메모리 상에서 모든 원소를 이동하는 것은 항상 O(n) 연산입니다. 가장 간단한 큐의 구현 예제에서, 값을 삽입하는 것은 빠르지만 값을 빼내는 것은 여전히 아쉽습니다.

조금 더 효율적인 큐

디큐잉(값을 빼내는 것)을 효율적으로 하기 위해서, 배열의 앞에 여분의 공간을 남겨둘 수 있습니다. 스위프트의 내장 배열이 이러한 기능을 제공하지 않으므로, 직접 코드를 구현해야 합니다.

주요 원리는 이렇습니다. 아이템을 디큐잉 할 때, 배열의 컨원소들을 이동하지 않고, 아이템의 위치를 빈 상태로 둡니다. "Ada"를 디큐잉 할 때 배열은 :

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

"Steve"를 디큐잉 한다면, 배열은 이렇습니다:

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

이러한 빈 공간이 절대 재 사용되지 않기 때문에, 우리들은 주기적으로 배열에 있는 원소들을 이동하는 손질을 해줘야 합니다.

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

손질 작업은 메모리 시프팅으로 O(n) 연산입니다. 이것은 가끔 한번씩 발생하므로 평균적으로 O(1)입니다.

완성된 큐의 구현 코드는 다음과 같습니다 :

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

이것은 마치 슈퍼마켓에서 사람들이 계산 대를 기다리는 것과 같습니다. 하지만 계산원이 큐에서 한 칸씩 이동하는 것만 제외하고 말입니다.

만약 우리가 앞의 비어있는 공간을 제거한다면 인큐와 디큐를 거듭할수록 배열은 계속해서 커질 것입니다. 주기적으로 배열을 정돈하기 위해 다음과 같이 작성합니다 :

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                   // [] 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)의 연산입니다.

더 알아보기

큐를 만드는 방법에는 여러가지가 있습니다. 또 다른 구현 방식으로는 링크드 리스트 (linked list), 순환 버퍼(circular buffer) 또는 힙(heap)이 있습니다.

덱은 큐의 변형입니다. 더블-엔디드 큐는 양 끝단에서 원소를 인큐하고 디큐할 수 있습니다. 우선순위 큐는 정렬된 큐로서, 가장 중요한 아이템을 앞에 둡니다.

---

출처: Written for Swift Algorithm Club by Matthijs Hollemans