[data structure] Queue(큐) - 1 - WhiteHyun's Develop Blog

Goal

자료구조 Queue에 대해 설명할 수 있다.

Swift 언어로 Queue를 구현해낼 수 있다.

Queue의 연산 중 dequeue의 시간복잡도를 설명할 수 있다.

들어가기에 앞서

본 글은 raywenderlich의 Swift Algorithm Club에서 설명하는 예시 코드 일부를 가져와 설명합니다.^[1]

Queue

큐(Queue)는 자료구조의 개념 가운데 하나로 여러 데이터에 대해 먼저 들어간 요소가 먼저 나가는 방식(First In, First Out)입니다. 나중에 넣은 데이터가 먼저 나오는 스택구조와는 정반대되는 개념이죠.

입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용합니다.

BFS
Cache
통신 패킷모델링
콜센터 대기시간
프린터 출력 처리
프로세스 관리
수강신청

Queue의 기본적 연산 종류

isEmpty

큐가 비어있는지 확인

count

큐의 요소의 개수

enqueue

큐에 요소를 삽입

dequeue

큐에 요소를 제거, 큐에 요소가 없을 시 nil 반환 (Swift 기준)

Queue 유형

큐의 앞 부분은 front, 뒷 부분은 rear라고 지칭합니다.

큐는 유형이 다양하며, 기본인 선형 큐, 원형 큐, 덱, 우선순위 큐 등이 존재합니다. 본 글에서는 선형 큐에 대해서만 설명합니다.

선형 큐

queue

큐의 기본형이라고 할 수 있으며, 배열을 이용하여 Swift 코드로 다음과 같이 구현 가능합니다.

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

완벽하게 잘 동작하지만, 배열의 특성상 dequeue를 진행하게 되면 O(n)의 시간이 걸리게 되기 때문에 최적(Optimal)은 아닙니다.

배열은 데이터가 이어지는 특성이 있습니다. 따라서 첫 번째 원소를 가져오게 되면, 데이터를 앞당기는(shift) 작업이 추가로 진행됩니다.

queue-time-complexity

Optimal Queue

보다 효율적인 Dequeue 연산을 위해 데이터 쉬프팅(data shifting)을 사용하지 않고 데이터를 빼오는 아이디어를 생각해보아야합니다.

해결 방법 가운데 하나는 큐에서 요소를 제거할 때마다 nil로 데이터를 삭제했다는 것으로 표시하는 겁니다. 그러면 데이터를 앞으로 당겨오지 않고 값만 nil로 바꾸면서 O(1)의 속도를 가져올 수 있게 됩니다. 대신에 이를 사용하기 위해서는 첫 번째 요소의 위치를 가리키는 변수를 하나 추가해주어야 합니다. 다음과 같이 말이죠.

하지만 해당 아이디어로 큐를 수행할 때 dequeue 연산을 실행하면 head는 뒤로 가면서 앞의 요소들은 전부 nil이 될 겁니다. 이렇게 되면 점점 dequeue 연산이 잦아질수록 앞의 데이터는 쓰레기가 되어버릴 겁니다. 따라서 어느정도 head가 뒤로 가게 되었다면 앞쪽으로 다시 당겨오는 작업을 추가로 해주어야합니다. 다음은 기존의 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) // O(n)
      head = 0
    }

    return element
  }

  public var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

위 작성된 코드는 배열의 크기가 50 이상이면서 nil로 처리되어 있는 데이터의 비율이 전체의 25% 이상이 되는 경우 배열의 값을 시프팅하게 만들어두었습니다. 비록 이 과정이 O(n)일지라도, 가끔 발생하는 과정이기 때문에 평균적으로 O(1)이 소요됩니다.

References

swift-algorithm-club, Queue

[data structure] Queue(큐) - 1