큐 자료구조

간단한 큐 자료구조를 스위프트로 만들어 보면서 다음과 같은 스위프트 언어의 기능들을 어떻게 사용하는지 설명하겠습니다.

  • 밸류 타입 제네릭
  • UnsafeMutablePointer
  • 구조체의 값을 변경하는 함수
  • SequenceType과 GeneratorType 프로토콜
  • 스위프트에서의 “쓰기 시점의 복사본 생성”

큐는 잘 아시는 것처럼 REAR (혹은 꼬리(tail)라고도 하는)라고 부르는 종단부에서 부터 첫 번째 엘리먼트를 추가하고 FRONT(또는 머리(head)) 라고 하는 반대편에서 엘리먼트를 꺼내오는 순차적인 추상 자료 구조입니다. 가장 먼저 들어간 것이 가장 먼저 나온다는 의미에서 FIFO (First In First Out) 자료 구조라고 합니다.

큐에 엘리먼트를 추가하는 것을Enqueue라고 하고 꺼내오는 것을Dequeue라고 합니다.

큐 프로토콜

큐의enqueue:,dequeue,peek기능을 정의하는 프로토콜을 정의하겠습니다.mutating으로 표기된 함수들은 큐의 프로퍼티를 변경하기위해서입니다. 그리고Element로 연관된 엘리먼트의 타입을 정의합니다.

protocol QueueType {
    typealias Element
    mutating func enqueue(element: Element)
    mutating func dequeue() -> Element?
    func peek() -> Element?
}
Mutating

디폴트로 구조체(struct)와 열거형(enum)과 같은 밸류 타입의 프로퍼티들은 인스턴스 메서드에서 변경할 수 없습니다. 구조체나 열거형의 특정 메서드에서 프로퍼티의 값을 변경해야하는 경우에는 mutating 하도록 명시적으로 지정해야합니다.

큐 저장소 

final class Storage<Element> {

 private var pointer: UnsafeMutablePointer<Element>
 private let capacity: Int

 init(capacity: Int) {
   pointer = UnsafeMutablePointer<Element>.alloc(capacity)
   self.capacity = capacity
 }

 static func copy(storage: Storage) -> Storage<Element> {
   let storageNew = Storage<Element>(capacity: storage.capacity)
   storageNew.pointer.initializeFrom(storage.pointer, count: storage.capacity)
   return storageNew
 }

 func add(element: Element, at index: Int) {
   (pointer + index).initialize(element)
 }

 func removeAt(index: Int) {
   (pointer + index).destroy()
 }

 func itemAt(index: Int) -> Element {
   return (pointer + index).memory
 }

 deinit {
   pointer.destroy(capacity)
   pointer.dealloc(capacity)
 }
}

큐 엘리먼트를 저장할 제네릭 클래스를 정의하였습니다. 이 클래스는 생성자에서 주어진 크기의 변경이 가능한 포인터를 생성하며 이 메모리 포인터의 특정 인덱스를add,remove할 수 있는 기능을 제공합니다.

함수

  • init(capacity:Int)

    pointer에 큐의 엘리먼트를 저장하기위한capacity만큼의 메모리를 할당합니다.

  • func add(element: Element, at index:Int)

  • func removeAt(index:Int)

  • func itemAt(index:Int) -> Element

    지정한 위치에 엘리먼트를 추가하고 제거하고 반환하는 기능을 합니다.

    스위프트의 stdlib에서 포인터를 지정한 만큼 증가하도록+연산자를 오버로드하고 있기 때문에(ptr + position).memory가 정상적으로 동작합니다.

public func +<Memory>(lhs: UnsafeMutablePointer<Memory>, rhs: Int) 
    -> UnsafeMutablePointer<Memory>

  • deinit

    pointer에 할당되었던 메모리를 해제하고 반환합니다.

  • static func copy(storage: Storage) -> Storage<Element>

    큐 자체를 복사하기 위한 기능을 합니다.

큐 

struct Queue<Element> : QueueType {

  private var storage: Storage<Element>
  private var rear: Int = 0
  private var front: Int = 0
  private var count: Int = 0
  private let capacity: Int

  init(capacity: Int) {
    self.capacity = capacity
    storage = Storage<Element>(capacity: capacity)
  }

  private mutating func makeUnique() {
    if !isUniquelyReferencedNonObjC(&storage) {
      storage = Storage.copy(storage)
    }
  }

  mutating func enqueue(element: Element) {
    guard count < capacity else {
      print("Queue is full.")
      return
    }
    makeUnique()
    storage.add(element, at: rear)
    rear = (rear + 1) % capacity
    count = count + 1
  }

  mutating func dequeue() -> Element? {
    guard count > 0 else {
      print("Queue is empty.")
      return nil
  }

   makeUnique()
   let item = storage.itemAt(front)
   storage.removeAt(front)
   front = (front + 1) % capacity
   count = count - 1
   return item
  }

  func peek() -> Element? {
   guard count > 0 else {
     print("Queue is empty.")
     return nil
   }
   return storage.itemAt(front)
  }
}

Queue는 구조체로 구현되어 있으며storage는 버퍼를 유지하고,rear와front는 큐의 선두와 후미에 대한 위치를 나타내며,count는 엘리먼트의 수를 나타내며,capacity는 버퍼의 크기를 표시합니다.init메서드에서storage를 주어진capacity에 따라 초기화 합니다.

함수

  • private mutating func makeUnique()

    non-objc객체의 (예: 순수한 스위프트 객체) 레퍼런스 카운트가 1 인지 검사하기 위해 내부적으로 stdlib에서 제공하는isUniquelyReferencedNonObjC()를 호출합니다.

    즉, 어떤 큐 인스턴스가 새로운 변수에 대입되었을 때 기존 변수나 새로운 변수에enqueue,dequeue,peek와 같이 큐의 내용이 변경되는 함수가 불리기 전까지 동일한 저장소를 공유하도록 하였습니다. 그러다가 실제로 큐의 내용이 변경되는 시점에 저장소를 복사하고 변경작업을 하게 됩니다. 이러한 방식이 “쓰기 시점의 복사(copy-on-wtite)”를 구현하는 방법입니다.

public func isUniquelyReferencedNonObjC<T : AnyObject>(inout object: T) -> Bool

if !isUniquelyReferencedNonObjC(&storage) {
        storage = Storage.copy(storage)
    }
  • enqueue() 는 엘리먼트를 큐의 끝에 추가합니다.
  • dequeue() 는 큐에서 첫 번째 엘리먼트를 꺼내 옵니다.
  • peek() 는 큐의 첫 번째 엘리먼트를 반환합니다.

큐가 배열처럼for...in루프를 지원하기위해서는SequenceType프로토콜을 구현해야합니다. 이 프로토콜에서 가장 중요한 것은GeneratorType을 리턴하는generate()함수입니다. 따라서next()함수가 큐의dequeue()함수를 호출하도록 하는GeneratorType프로토콜을 구현해야합니다.

extension Queue: SequenceType {
  func generate() -> QueueGenerator<Element> {
    return QueueGenerator<Element>(queue: self)
  }
}

struct QueueGenerator<Element> : GeneratorType {
  var queue: Queue<Element>
    mutating func next() -> Element? {
    return queue.dequeue()
  }
}

큐 사용 예

정수Int의 큐를 만들엇SequenceType의 함수들이 동작하는 예를 만들어 보겠습니다.

var intQueue = Queue<Int>(capacity: 20)
intQueue.enqueue(11)
intQueue.enqueue(12)
intQueue.dequeue() // 가장 앞쪽에 있는 11를 꺼내오고 큐에서 제거됩니다.
intQueue.enqueue(13)
print("Print elements in queue")
for i in intQueue {
 print(i)  // 12와 13이 출력됩니다.
}

let queueValuesMultipliedByTwo = intQueue.map { $0 * 2 }
print(queueValuesMultipliedByTwo) // 출력: [24, 26]

레퍼런스 타입을 큐에 저장하기

예로 사용할 간단한 클래스를 만들고 클래스의 설명(description)을 출력할 수 있도록CustomStringConvertible프로토콜을 따르도록 구현합니다.

class Foo : CustomStringConvertible {
 let tag: Int
 init(_ tag: Int) {
  self.tag = tag
 }
 deinit {
  print("Removing...\(tag)")
 }
 var description: String {
  return "#\(tag)"
 }
}

레퍼런스 타입의 큐를 사용하는 예입니다.

var queueClass = Queue<Foo>(capacity: 20)
queueClass.enqueue(Foo(1))
queueClass.enqueue(Foo(2))
queueClass.dequeue()
print(queueClass)

results matching ""

    No results matching ""