Ring Buffer를 이용한 Queue 자료구조 구현, Swift

Queue를 구현하는 방법은 일반적으로 4가지가 있다.

1. 배열을 이용하는 방법

2. 이중 연결 목록을 이용하는 방법

3. 링 버퍼를 이용하는 방법

4. 이중 스택을 이용하는 방법

 

이 중에서 배열을 이용하는 방법의 경우 데이터 삽입의 경우는 O(1)이나 데이터를 출력할 때는 앞에서 부터 데이터가 제거되므로 배열이 공간을 재 배열하는 만큼의 비용이 발생한다. Swift에서는 그 동작이 O(n)이다.

 

또 이중 연결 목록을 이용하는 방법은 노드 하나당 가지는 데이터가 value, next, previous 3개의 속성을 가지고 있기도 하고 아무래도 직관적이지도 않다. 데이터의 삽입, 출력에서 이론상 성능은 O(1)이지만 높은 오버헤드를 가지고 있다.

 

따라서 4가지 방법 중 가장 좋은 성능을 가지고 있고 구현이 쉬운 방법은 링 버퍼를 이용하는 법이다.

 

Swift 에서 링 버퍼를 구현하는 방법은 아래 링크를 참고

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Ring%20Buffer

이미지 썸네일 삭제

swift-algorithm-club/Ring Buffer at master · raywenderlich/swift-algorithm-club

Algorithms and data structures in Swift, with explanations! - swift-algorithm-club/Ring Buffer at master · raywenderlich/swift-algorithm-club

github.com

public struct QueueRingBuffer<T> {
  private var ringBuffer: RingBuffer<T>
  
  public init(count: Int) {
    ringBuffer = RingBuffer<T>(count: count)
  }
  
  public var isEmpty: Bool {
    ringBuffer.isEmpty
  }
  
  public var peek: T? {
    ringBuffer.first
  }
  
  public mutating func enqueue(_ element: T) -> Bool {
    ringBuffer.write(element)
  }
  
  public mutating func dequeue() -> T? {
    ringBuffer.read()
  }
}

extension QueueRingBuffer: CustomStringConvertible {
  public var description: String {
    String(describing: ringBuffer)
  }
}