데크(Deque)

데크는 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 자료구조다. "덱"이라고 발음한다. 일반적인 큐는 뒤쪽에서 데이터를 추가하고 앞쪽에서 제거한다. 데크는 앞쪽에서도 추가하고 뒤쪽에서도 제거할 수 있으며, 양쪽 끝의 데이터를 확인할 수도 있다.

다음은 Swift로 구현한 기본적인 데크 예제다:

public struct Deque<T> {
  private 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 enqueueFront(_ element: T) {
    array.insert(element, at: 0)
  }

  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }

  public mutating func dequeueBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeLast()
    }
  }

  public func peekFront() -> T? {
    return array.first
  }

  public func peekBack() -> T? {
    return array.last
  }
}

이 구현은 내부적으로 배열을 사용한다. 데이터를 추가하거나 제거하는 작업은 배열의 앞쪽이나 뒤쪽에서 간단히 수행한다.

플레이그라운드에서 사용하는 예제는 다음과 같다:

var deque = Deque<Int>()
deque.enqueue(1)
deque.enqueue(2)
deque.enqueue(3)
deque.enqueue(4)

deque.dequeue()       // 1
deque.dequeueBack()   // 4

deque.enqueueFront(5)
deque.dequeue()       // 5

이 Deque 구현은 간단하지만 효율적이지 않다. 특히 enqueueFront()와 dequeue() 같은 몇몇 연산은 O(n) 시간 복잡도를 가진다. 이 예제는 데크의 기본 원리를 보여주기 위해 포함했다.

더 효율적인 버전

dequeue()와 enqueueFront()가 **O(n)**인 이유는 이들이 배열의 앞부분에서 동작하기 때문이다. 배열의 앞부분에서 엘리먼트를 제거하면, 나머지 모든 엘리먼트가 메모리에서 한 칸씩 앞으로 이동해야 한다.

예를 들어, deque의 배열이 다음과 같다고 가정하자:

[ 1, 2, 3, 4 ]

dequeue()는 배열에서 1을 제거하고, 2, 3, 4를 한 칸씩 앞으로 이동시킨다:

[ 2, 3, 4 ]

이 작업은 모든 배열 엘리먼트를 메모리에서 한 칸씩 이동시켜야 하므로 O(n) 연산이다.

마찬가지로, 배열의 앞부분에 엘리먼트를 삽입하는 것도 비용이 많이 든다. 다른 모든 엘리먼트를 한 칸씩 뒤로 이동시켜야 하기 때문이다. 따라서 enqueueFront(5)는 배열을 다음과 같이 변경한다:

[ 5, 2, 3, 4 ]

먼저 2, 3, 4를 메모리에서 한 칸씩 뒤로 이동시키고, 새로운 엘리먼트 5를 2가 있던 자리에 삽입한다.

그렇다면 enqueue()와 dequeueBack()에서는 왜 이런 문제가 발생하지 않을까? 이 연산들은 배열의 끝에서 수행되기 때문이다. Swift에서 크기 조정 가능한 배열은 배열의 끝에 일정량의 여유 공간을 확보하는 방식으로 구현된다.

초기 배열 [ 1, 2, 3, 4]는 실제로 메모리에서 다음과 같이 보인다:

[ 1, 2, 3, 4, x, x, x ]

여기서 x는 아직 사용되지 않은 추가 공간을 나타낸다. enqueue(6)를 호출하면 새로운 아이템을 다음 빈 공간에 복사한다:

[ 1, 2, 3, 4, 6, x, x ]

dequeueBack() 함수는 array.removeLast()를 사용해 아이템을 삭제한다. 이 작업은 배열의 메모리를 줄이지 않고, 단순히 array.count를 1만큼 감소시킨다. 여기에는 비용이 많이 드는 메모리 복사가 포함되지 않는다. 따라서 배열의 끝에서 수행되는 연산은 빠르며, **O(1)**이다.

배열의 끝에 빈 공간이 부족할 경우, Swift는 더 큰 배열을 할당하고 모든 데이터를 복사한다. 이 작업은 **O(n)**이지만, 가끔 발생하기 때문에 평균적으로 배열 끝에 새로운 엘리먼트를 추가하는 작업은 여전히 **O(1)**이다.

물론, 배열의 앞부분에서도 같은 트릭을 사용할 수 있다. 이렇게 하면 큐의 앞부분에서 수행되는 연산도 효율적으로 만들 수 있다. 배열은 다음과 같이 보일 것이다:

[ x, x, x, 1, 2, 3, 4, x, x, x ]

이제 배열의 시작 부분에도 여유 공간이 생겨, 큐의 앞부분에서 엘리먼트를 추가하거나 제거하는 작업도 **O(1)**이 된다.

다음은 새로운 Deque 버전이다:

public struct Deque<T> {
  private var array: [T?]
  private var head: Int
  private var capacity: Int
  private let originalCapacity:Int

  public init(_ capacity: Int = 10) {
    self.capacity = max(capacity, 1)
    originalCapacity = self.capacity
    array = [T?](repeating: nil, count: capacity)
    head = capacity
  }

  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 enqueueFront(_ element: T) {
    // 아래에서 설명
  }

  public mutating func dequeue() -> T? {
    // 아래에서 설명
  }

  public mutating func dequeueBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeLast()
    }
  }

  public func peekFront() -> T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }

  public func peekBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.last!
    }
  }  
}

기본적으로 이전과 비슷해 보이지만, 몇 가지 중요한 차이점이 있다. 배열은 이제 T 대신 T? 타입의 객체를 저장한다. 배열 엘리먼트를 빈 상태로 표시할 방법이 필요하기 때문이다.

init 메서드는 일정 수의 nil 값을 포함하는 새로운 배열을 할당한다. 이는 배열의 시작 부분에 확보된 여유 공간이다. 기본적으로 10개의 빈 공간을 생성한다.

head 변수는 배열에서 가장 앞에 있는 객체의 인덱스다. 큐가 현재 비어 있으므로, head는 배열의 끝을 넘어선 인덱스를 가리킨다.

[ x, x, x, x, x, x, x, x, x, x ]
                                 |
                                 head

앞쪽에 객체를 추가하려면 head를 한 칸 왼쪽으로 이동시키고, 새로운 객체를 head 인덱스에 복사한다. 예를 들어, enqueueFront(5)를 수행하면 다음과 같다:

[ x, x, x, x, x, x, x, x, x, 5 ]
                             |
                             head

그 다음 enqueueFront(7)을 수행하면:

[ x, x, x, x, x, x, x, x, 7, 5 ]
                          |
                          head

이렇게 head는 계속 왼쪽으로 이동하며, 항상 큐의 첫 번째 아이템을 가리킨다. 이제 enqueueFront()는 **O(1)**이다. 배열에 값을 복사하는 상수 시간 연산만 필요하기 때문이다.

다음은 해당 코드다:

  public mutating func enqueueFront(element: T) {
    head -= 1
    array[head] = element
  }

큐의 끝에 추가하는 작업은 이전과 동일하다(이전과 완전히 같은 코드다). 예를 들어, enqueue(1)을 수행하면:

[ x, x, x, x, x, x, x, x, 7, 5, 1, x, x, x, x, x, x, x, x, x ]
                          |
                          head

배열이 스스로 크기를 조정한 것을 확인할 수 있다. 1을 추가할 공간이 없었기 때문에, Swift는 배열을 더 크게 만들고 끝에 여러 빈 공간을 추가했다. 다른 객체를 추가하면, 다음 빈 공간에 추가된다. 예를 들어, enqueue(2)를 수행하면:

[ x, x, x, x, x, x, x, x, 7, 5, 1, 2, x, x, x, x, x, x, x, x ]
                          |
                          head

참고: print(deque.array)를 실행하면 배열의 끝에 있는 빈 공간은 보이지 않는다. Swift가 이를 숨기기 때문이다. 배열의 앞부분에 있는 빈 공간만 보인다.

dequeue() 메서드는 enqueueFront()의 반대 작업을 수행한다. head에 있는 값을 읽고, 배열 엘리먼트를 nil로 설정한 다음, head를 한 칸 오른쪽으로 이동시킨다:

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

    array[head] = nil
    head += 1

    return element
  }

하지만 작은 문제가 하나 있다... 앞쪽에 많은 객체를 추가하면, 언젠가는 앞쪽의 빈 공간이 부족해질 것이다. 배열의 끝에서 이런 일이 발생하면, Swift는 자동으로 크기를 조정한다. 하지만 배열의 앞부분에서는 이 상황을 직접 처리해야 한다. enqueueFront()에 추가 로직을 넣어야 한다:

  public mutating func enqueueFront(element: T) {
    if head == 0 {
      capacity *= 2
      let emptySpace = [T?](repeating: nil, count: capacity)
      array.insert(contentsOf: emptySpace, at: 0)
      head = capacity
    }

    head -= 1
    array[head] = element
  }

head가 0이면 앞쪽에 더 이상 빈 공간이 없다는 뜻이다. 이 경우, 배열에 새로운 nil 엘리먼트를 추가한다. 이 작업은 **O(n)**이지만, 이 비용은 모든 enqueueFront() 호출에 분산되므로, 평균적으로 각 enqueueFront() 호출은 여전히 **O(1)**이다.

참고: 이때마다 capacity를 2배로 늘리므로, 큐가 점점 커질수록 크기 조정이 덜 자주 발생한다. 이는 Swift 배열이 끝에서 자동으로 수행하는 작업과 동일하다.

dequeue()에도 비슷한 작업을 추가해야 한다. 대부분의 엘리먼트를 큐의 끝에 추가하고, 앞쪽에서 제거하는 경우, 배열이 다음과 같이 될 수 있다:

[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, 1, 2, 3 ]
                                                              |
                                                              head

앞쪽의 빈 공간은 enqueueFront()를 호출할 때만 사용된다. 하지만 앞쪽에 객체를 추가하는 작업이 드물게 발생한다면, 이 공간은 낭비된다. 따라서 dequeue()에 이 공간을 정리하는 코드를 추가하자:

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

    array[head] = nil
    head += 1

    if capacity >= originalCapacity && head >= capacity*2 {
      let amountToRemove = capacity + capacity/2
      array.removeFirst(amountToRemove)
      head -= amountToRemove
      capacity /= 2
    }
    return element
  }

capacity는 큐의 앞부분에 있는 원래 빈 공간의 수다. head가 capacity의 두 배 이상 오른쪽으로 이동했다면, 이 빈 공간을 정리할 때다. 이를 약 25%로 줄인다.

참고: deque는 capacity를 originalCapacity와 비교해 최소 원래 capacity를 유지한다.

예를 들어, 다음과 같은 배열:

[ x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, 1, 2, 3 ]
                                |                             |
                                capacity                      head

정리 후에는 다음과 같이 된다:

[ x, x, x, x, x, 1, 2, 3 ]
                 |
                 head
                 capacity

이렇게 하면 앞쪽에서 빠르게 추가하고 제거하는 작업과 메모리 요구 사항을 합리적으로 유지하는 사이에서 균형을 맞출 수 있다.

참고: 매우 작은 배열에서는 트리밍을 수행하지 않는다. 몇 바이트의 메모리를 절약하기 위해 이 작업을 수행할 가치가 없다.

함께 보기

덱(deque)을 구현하는 다른 방법으로는 이중 연결 리스트, 원형 버퍼, 또는 서로 반대 방향을 향한 두 개의 스택을 사용하는 방법이 있다.

Swift로 구현한 완전한 기능의 덱

Swift Algorithm Club의 Matthijs Hollemans가 작성함