[스위프트 : 자료구조] 큐 (1 / 4): Queue: #배열로 구현한 큐: #배열의원리: #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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

큐 자료구조 : Queue

• What is Queue
• 영화티켓 살 때 줄 서죠? 학생 때 쉬는식간에 매점으로 줄 안서기 위해 달리죠? 왜냐하면 일찍 온 순서대로 티켓을 사거나, 매점을 이용하거나 할 수 있기 때문입니다.
• 일상생활, 즉 인간이 생활을 할 때 이러한 현상들은 주변에 많이 일어나고 그래서 너무나 당연하게 느껴지죠?
• 이러한 현상들을 컴퓨터로 표현한 것을 'Queue' 라고 합니다. 
• 이러한 현상들은 공통점이 있습니다. '먼저 온 순서대로 먼저 작업을 해 준다는 것' 입니다.
• 이를 First - In - First - Out 이라고 부르며 FIFO 라고 알려져 있습니다. 즉 '큐는 FIFO 특성을 가진 자료구조' 인 것이죠!
• 영화관에서 줄서는 것을 예로 그림으로 표현하면 아래와 같습니다.

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

• 구현 ( Queue protocol , QueueArray 구조체 ) (1 / 4)
• Queue Protocol

public protocol Queue {
    associatedtype Element 
    // associatedtype 키워드는 프로토콜을 정의할 때 제네릭타입 처럼 일반화 시킨 타입을 지정할 떄 사용합니다.
    // 아래에 Element 활용한 메소드들 정의한 것 보이시죠? 
    // 이 프로토콜을 채택한 것의 타입이 Int 라면 아래에 정의한 메소드들에서 쓴 Element 는 모두 Int 가 되는 것이죠. 
    // 물론 String 도 Double 도 내가 원하는 타입이 될 수도 있구요!
    // 정리하면 Element 는 이 프로토콜을 채택하는 객체가 자기가 원하는 타입의 Queue 를 작성할 수 있도록 해주는 것이쥬.
    mutating func enQueue(_ element: Element) -> Bool
    // 큐 끝에 새로운 큐를 추가하고 성공여부 반환 , 구조체가 이 프로토콜 채택가능성 있기 때문에 mutating 붙여주기 유의.
    mutating func deQueue() -> Element?
    // 가장 먼저 들어온 앞의 큐 제거하고 제거한 큐 반환하기.
    
    var isEmpty: Bool { get } // 큐가 비어있는지 알려주는 읽기전용 프로퍼티 (get은 읽기전용 을 알려주는 겁니다.)
    var peek: Element? { get } 
    // 가장 앞의 큐를 알려줍니다.. 제거하는게 아니구요 (deQueue 와 차이)
    // peek 은 '살짝 보다' 라는 뜻입니다^^.
    // get 은 읽기 라는 연산을 수행하고 set 은 쓰기 연산을 수행하는 키워드 입니다. (노파심에 ^^)
}

( associatetype swift 공식문서) ( generics type 제 글 )

• QueueArray ( 배열로 구현한 큐 )

public struct QueueArray<T>: Queue { // Queue 프로토콜을 채택함.
    private var array = Array<T>() 
    // 제네릭 타입 T 로 Queue 프로토콜의 Element 타입이 추론되겠죠? Queue 프로토콜에서 설명한 associatedtype 이니까요!
    public init() {}
    
    // protocol에서 정의한 것들 지켜야쥬?
    public var isEmpty: Bool {
        return array.isEmpty // 배열의 isEmpty 프로퍼티 사용하면 되쥬?
    }
    public var peek: T? {
        return array.first // 배열의 first 프로퍼티 사용하면 되쥬? 
    }
    
    public mutating func enQueue(_ element: T) -> Bool { // 큐 추가.
        array.append(element) 
        // append 연산은 수행속도가 O(1) 입니다. 이 표기법을 몰라도 됩니다. 수행속도 : O(1) > O(n) > O(n2)제곱
        // 왜냐하면 표준라이브러리의 Array 의 append 연산이 O(1) 로 수행됩니다.
        // 이게 뭐냐면 배열이 꽉 찼는데 더 추가해야 될 때마다 해당 배열 인스턴스는 배열의 크기를 두배로 늘립니다.
        // 그림으로 스위프트의 배열에 대해 설명해 드릴게요!
        return true
}

• 스위프트에서 배열 구조체 ( Array  )
• 이걸 왜 설명할 까유? 배열의 특징을 알아야 배열로 구현한 큐의 성능을 알 수 있기 때문이쥬?

• 6개 또 꽉차면?
  

• 이게 스위프트의 배열에서는 먼저 크게 늘려놓으니 빈 공간에 추가할 땐 수행속도가 빠릅니다.
• 하지만 가끔씩(?) 크기를 늘려야 할 때 수행속도가 O(n) 입니다. 배열의 메모리를 n 번 반복해서 할당해야 하기 때문이죠!
• 이것이 스위프트 배열 구조체의 특징.

• QueueArray 이어서

public mutating func deQueue() -> T? {
        return isEmpty ? nil : array.removeFirst() 
        // 비어있으면 제거할 게 없으므로 반환값도 없습니다. 그러므로 isEmpty 를 기준으로 if를 실행합니다.
        // 위의 구문은 isEmpty 가 true 면 nil , false 면 array.removeFirst() 를 반환하라는 뜻입니다.
        // 제거 연산은 수행속도가 O(n) 입니다. 배열에서 첫 아이템 제거 연산이 O(n) 이라서..
        // 배열에서 속도가 왜그래? : 배열의 맨 앞의 아이템을 제거하면 그 뒤에 있는 것들이 한칸씩 앞으로 이동해야 되기 떄문.
        // 그림으로 보시죠!
         }

• 배열에서의 deQueue

• 한 칸씩 앞으로 이동시켜야 하기 때문에 수행시간이 O(n) 이 됩니다. n 번 반복수행 해야 하거든요. 비 효율적인 면이 있네요.
• 이러한 단점 때문에 성능이 낮아지므로 큐를 다르게도 구현하는 것입니다. 

• QueueArray 사용자 출력 ( 잘 됬는지 내 눈으로 봐야 하니까요! ㅎㅎ )

extension QueueArray: CustomStringConvertible { 
// CustomStringConvertible 프토토콜을 채택한 객체를 출력할 때 출력내용을 사용자화 해줍니다.
    public var description: String {
        return String(describing: array) 
        // array 배열을 출력하도록 설정.
        // Array 구조체는 이 프로토콜이 이미 채택되어 있어서 그냥 출력하면 됩니다.
    }

( CustomStringConvertible 공식문서)

• 실행

var queueArray = QueueArray<String>() // 인스턴스 생성하구, 제네릭 타입은 String 으로 하겠습니다. 내 이름 추가할 거거든요ㅋㅋ
queueArray.enQueue("창식") // 큐 추가하구~ 제 이름입니다..^^
queueArray.enQueue("유정")
queueArray.enQueue("주혁")
print(queueArray) // 여기서 한번 출력 
queueArray.deQueue() // 가장 앞에 있는 큐 제거,
print(queueArray) // 출력

• 결과

• 성능( Performance )

• Swift4: 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList

전체 소스 파일