[스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!: #swift

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

Ring Buffer 를 이용한 큐 구현

• 구성
• Queue 에서는 4가지 다른 특성의 큐를 구현할 예정입니다. 다룰 것들은 다음과 같습니다.
• Queue 프로토콜 구현 (1 / 4)
• 아래 4 가지 큐를 구현할 때 Queue 프로토콜을 채택해서 구현하려고 이 프로토콜을 정의합니다.
• Array 를 사용해서 큐 구현. (1 / 4)
• Doubly Linked List  이용해서 큐 구현. (2 / 4)
• doubly linked list 구현 (2 / 4)
• Double Stack 을 이용해서 큐 구현.(3 / 4)
• Ring Buffer 를 이용해서 큐 구현. (4 / 4)
• 이렇게 여러가지 방법으로 큐를 구현하는 이유는 성능차이 ( Performance )  가 있기 때문입니다.
• '성능을 조금 씩 개선하면서 똑같은 큐를 빠르고 효율적으로 만들어 보자는 것'이 4가지 큐를 구현하는 목적 입니다.

• What is Ring Buffer ? ( Circular buffer 라고도 불림 )
• Ring Buffer 는 고정된 크기의 배열을 사용하고, 배열이 큐의 값들로 가득 차면 다시 첫 번째 아이템으로 돌아오는 방법을 사용합니다. 
• 그림으로 설명합니다. 은근히 복잡하니 집중!
• 크기가 4 인 배열의 Ring Buffer 생성

• Ring Buffer 에 "Chris" 라는 아이템을 enQueue 로 넣어보자.
• 추가되는 동시에 Write 이 가리키는 곳이 한칸 앞으로 가네!

• Ring Buffer 에 두 개의 아이템 추가로 enQueue 해 보자!
• 마찬가지로 2개가 추가되니 Write 두 칸 앞으로 이동. 
• Write 은 원래 있던 곳에 아이템을 추가하고 앞으로 이동하는 역할을 하는 것을 알 수 있쥬?

• Ring Buffer 에 deQueue 두 번 실행해 보자!

• deQueue() 두 번 실행하면 Read는 원래 있던 곳의 아이템을 반환하고 실행한 만큼 앞으로 이동합니다. ( 여기선 "Chris", "Lattner" 가 반환되겠쥬? )

• 한 칸 남은 곳에 enQueue 를 실행하여 큐 가득 채워보자.

• 큐가 가득 참과 동시에 Write 은 되돌아 가서 배열의 첫 인덱스를 가리키쥬?

• 이 아이디어가 RingBuffer 의 원리 입니다.

• Read 를 이용해서 항상 큐에 가장 먼저 들어온 값을 읽을 수 있게 되는 거죠.

• 하지만 크기가 고정되 있어서 큐에 들어오는 값의 개수가 예측 불가능할 경우엔 사용할 수 없습니다. ㅠㅠ.

• 구현 ( RingBuffer 가 복잡하므로 먼저 구현하고 QueueBuffer 를 구현할 예정입니다. )

• RingBuffer

public struct RingBuffer<T> {
    
    private var array: [T?] // 고정된 크기의 배열입니다.
    private var readIndex = 0 // RingBuffer 의 Read 입니다.
    private var writeIndex = 0 // RingBuffer 의 Write 입니다.
    
    public init(count: Int) {
        array = Array<T?>(repeating: nil, count: count) 
        // 고정된 크기의 배열을 사용하기 때문에 배열의 크기인 count 를 초기화 함수에 넣어야 합니다.
    }
    
    public var first: T? { 
        return array[readIndex]
        // RingBuffer 의 Read 인 readIndex 를 읽어오면 큐의 첫번째 값입니다.
    }
    
    private var availableSpaceForReading: Int {
        return writeIndex - readIndex
        // 읽을 수 있는 개수를 표현한 것.
    }
    
    public var isEmpty: Bool {
        return availableSpaceForReading == 0
        // writeIndex 와 readIndex 가 같은 위치에 있으면 빈 큐입니다.
        // wirte 이 한바퀴 돌아서 올 수 있지 않냐는 의문이 들지만
        // 뒤에 나올 isFull 프로퍼티로 그 오류를 막습니다. 
    }
    
    private var availableSpaceForWriting: Int {
        return array.count - availableSpaceForReading
        // 큐에 값을 추가하는 wirte 을 할 수 있는 것을 표현
        // 고정된 배열이기 때문에 배열의 크기에서 읽을 수 있는 개수 빼면 나머지가 입력할 수 있는 개수죠?
    }
    
    public var isFull: Bool {
        return availableSpaceForWriting == 0
        // 배열이 가득 차면 writeIndex 가 한바퀴 돌아서 Read 랑 같은 위치에 놓이는 경우를 그림으로 보셨쥬?
        // 그 경우를 예로 들면 array.count = 4 고 availableSpaceForReading 도 4라
        // availableSpaceForWriting 는 0 가 되겠쥬?
        // 이런 식으로 큐가 가득 찬 경우를 표현합니다.
        // 가득 찼다면 더 이상 write 을 수행할 수 없게 제한해야 하기 때문에 꼭 필요한 부분입니다.
    }
    
    public mutating func write(_ element: T) -> Bool { // 큐에 값 입력하는 역할의 메소드
        if !isFull { // 가득 찼는지 먼저 확인하구요.
            array[writeIndex % array.count] = element 
            // % 연산(나누어 떨어지는)을 사용해서 끝에서 다시 되돌아 오는 것을 표현합니다.
            writeIndex += 1 // write 수행할 때마다 writeIndex 한 칸씩 앞으로 감을 표현합니다.
            return true
        } else {
            return false
        }
    }
    
    public mutating func read() -> T? {// 큐에 먼저 들어온 값을 제거하는 역할의 메소드.
        if !isEmpty {
            let element = array[readIndex % array.count] // 마찬가지로 %
            readIndex += 1 // 마찬가지로 한 칸씩 앞으로
            return element
        } else {
            return nil
        }
    }
}

• 출력을 위해 extension 

extension RingBuffer: CustomStringConvertible {
    public var description: String {
        let values = (0..<availableSpaceForReading).map {
            // 0..<availableSpaceForReading 은 읽을 수 있는 범위를 Range 구조체로 표현하는 것입니다.
            // 0..< 이 기호가 Range 구조체.
            // 우리가 출력할 것이 큐 안에 있는 값이죠?
            // 큐 안에 있는 값이라는 것은 아직 제거되지 않은 값 부터 새로 추가된 값 까지 를 뜻하죠?
            // 그것을 표현한 것이 availableSpaceForReading(writeIndex - readIndex) 입니다.
            // 그 범위를 표현한 Range 구조체에서 map 메소드를 사용해서 문자열로 변환합니다.
            String(describing: array[($0 + readIndex) % array.count]!)
            // String(describing:) 은 String 구조체의 초기화 함수죠? 
            // 매개변수에 들어온 타입의 description을 출력하는 것이죠.
            // $0 은 클로저에서 첫 번째 매개변수를 뜻합니다. 
            // collection 타입에서 map 메소드를 쓰면 $0 는 해당 범위의 각각의 값을 표현합니다.
            // 배열의 크기가 7 인 RingBuffer 로 예를 들면 아래 그림과 같습니다.
        }
        return String(describing: values)
        // 결국 우리가 반환하는 values 는 문자열을 가지고 있는 배열이고 이 배열 타입을 문자열 타입인 description 으로 반환하는 것
    }
}

• Range 구조체와 하위에 있는 map 메소드 여기!
• 배열의 크기 7인 RingBuffer 로 설명

• 이제 array[($0 + readIndex) % array.count] 가 뭘 표현하는지 알아보죠
• $0 은 0..< availableSpaceForReading  범위에서 각각의 값을 표현한다고 했죠? 그래서 0,1,2,3,4 입니다. 0..<5 이니까요.
• availableSpaceForReading 쓰는 이유는 아직 제거되지 않은 값부터 새로 추가된 값까지의 범위를 출력할 것이 목적이기 때문에 그렇습니다.
• readIndex 를 해당 범위만큼 더하면서 나온 값을 배열의 인덱스로 넣어서 값을 구합니다.   
• 예제에서는 array.count = 7 이기 때문에 
• 0+3, 1+3, 2+3, 3+3, 4+3 를 7로 나눈 나머지 를 사용합니다. ( 되돌아 가려면 % 썼었쥬? )
• 3,4,5,6,0 번째 인덱스의 값이 문자열로 전환되서 배열로 반환됩니다.
• 여기서는 4,5,6,7,8 이 나오겠네요.
• 큐 까지 구현하면 이 예제대로 실행해보고 출력결과 보여드릴게요.

• 구현
• QueueRingBuffer ( 매우 간단 ) ( RingBuffer 에서 다 해놔서.. )

public struct QueueRingBuffer<T>: Queue { 
    private var ringBuffer: RingBuffer<T> // 전에 구현한 RingBuffer 
    
    public init(count: Int) {
        ringBuffer = RingBuffer<T>(count: count) // BingBuffer 는 고정된 크기의 배열이 필요했었쥬?
    }
    
    public var isEmpty: Bool { // RingBuffer 에서 했쥬?
        return ringBuffer.isEmpty
    }
    
    public var peek: T? { // RingBuffer 에서 했쥬?
        return ringBuffer.first
    }
    
    public mutating func enQueue(_ element: T) -> Bool {
        return ringBuffer.write(element) // RingBuffer 에서 write 메소드가 enQueue
    }
    
    public mutating func deQueue() -> T? { // RingBuffer 에서 read 메소드가 deQueue
        return isEmpty ? nil : ringBuffer.read()
    }
}
 
extension QueueRingBuffer: CustomStringConvertible {
    public var description: String {
        return String(describing: ringBuffer) 
        // 출력도 RingBuffer 에서 다 만들어놨쥬?
    }
}
 

• 실행 ( 총 3 번 실행후 출력, 위의 예제대로 )

• 출력 ( 총 3번의 출력이 있었쥬? )

• 성능 ( Performance )

• 더블 연결리스트와 더블 스택으로 구현한 큐와 실행속도는 별다른 차이가 없지만 고정된 배열을 사용해야 하는 단점이 있습니다.

전체 소스 파일