[스위프트 : 자료구조] 큐 (3 / 4): Queue: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음: #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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

Double Stack 을 이용한 큐 구현

• 구성
• 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 Double Stack
• 더블 스택은 두 개의 스택으로 큐를 구현하는 아이디어 입니다. 
• 스택은 배열(Array) 로 구현했었죠? 스택에 대한 개념이 없으면 스택 먼저 학습하시거나 이 장을 넘어가세요.
• 더블 스택은 배열의 마지막 요소를 제거하는 연산은 재정렬이 필요하지 않으므로 수행속도가 O(1) 임을 활용한 방법입니다. 

• Left Stack 은 deQueue 전용 스택입니다. deQueue 를 수행할 아이템들은 Left Stack 에 들어있겠죠?

• Right Stack 은 enQueue 전용 스택입니다. enQueue 를 수행할 아이템들은 Right Stack 에 들어있겠죠?

• enQueue 를 수행할 Right Stack 에 스택 자료구조의 append 메소드를 사용해서 값을 추가합니다. 

• deQueue 를 수행하면 enQueue 전용인 Right Stack 의 요소들을 거꾸로 정렬한 뒤 Left Stack 에 옮기고 popLast() 메소드를 사용해서 마지막 값을 제거합니다.

• 거꾸로 정렬하는 이유는 큐의 성질인 먼저 들어온 아이템을 먼저 제거하면서 수행속도 까지 빠르게 하기 위해서 입니다.

• 거꾸로 정렬한 왼쪽 스택에서 마지막 요소를 제거하면 가장 먼저 들어온 '1' 이 제거됨을 아래 그림에서 볼 수 있죠?

• 구현

 
public struct QueueDoubleStack<T>: Queue {
    private var leftStack = Array<T>() // enQueue 를 담당할 왼쪽 스택
    private var rightStack = Array<T>() // deQueue 를 담당할 오른쪽 스택
    
    public init() {}
    
    //Queue 프로토콜 사항들.
    public mutating func enQueue(_ element: T) -> Bool {
        rightStack.append(element) // 오른쪽 스택에 append 메소드 사용해서 배열에 값 추가하면 끝.
        return true
    }
    
    public mutating func deQueue() -> T? {
        if leftStack.isEmpty { 
            // dequeue 목록인 왼쪽 배열이 비어있지 않다면, 그냥 반환만 하면 되.
            // 비어있는지 확인하는 연산은 은근히 중요한 역할을 합나다.
            // 비어있을 때에만 스택의 값들을 옮기는 과정을 수행하므로 값들이 꼬일 일이 없죠.
            leftStack = rightStack.reversed() 
            // 거꾸로 정렬해서 제일 먼저 들어온 값이 맨 끝으로 가므로 거꾸로 정렬.
            rightStack.removeAll() 
            // 왼쪽 스택이 비어있어서 값을 제거하기 위해 오른쪽 스택 값들이 왼쪽으로 옮겨진다면
            // 옮겨진 오른쪽 스택 값들은 모두 제거됩니다. 그리고 새로 큐에 들어오는 값을 받는 겁니다.
        }
        return leftStack.popLast()
    }
    
    public var isEmpty: Bool { // 두 스택 모두 비어있어야 빈 큐 입니다.
        return leftStack.isEmpty && rightStack.isEmpty
    }
    
    public var peek: T? {
        return !leftStack.isEmpty ? leftStack.last : rightStack.first
        // 왼쪽 스택에 아이템이 있을 때 큐의 성격인 맨 앞을 표현하려면 
        // 거꾸로 정렬됬기 때문에 스택의 마지막 값이 되므로 leftStack.last 을 해줘야쥬?
        // 왼쪽 스택이 기준이 되는 이유는 
        // 두 스택에서 peek 이 원하는 가장 먼저 들어온 값은 deQueue 스택인 왼쪽스택이 기준이기 때문입니다.
        // 오른쪽 스택을 먼저 확인하면 왼쪽스택에 더 먼저 들어온 값이 있더라도 오른쪽 스택의 늦은 값을 선택하게 됨을 유의.
    }
}
 
extension QueueDoubleStack: CustomStringConvertible {
    public var description: String {
        let printList = leftStack.reversed() + rightStack
        // 두 스택 모두가 큐의 전체 값이므로 큐를 표혀하려면 연결해서 표현해야 하쥬?
        return String(describing: printList)
    }
}
 

• 실행

• 결과

• 성능

• 배열로 구현한 큐( QueueArray ) 와 비교하면
• deQueue() 메소드의 수행속도가 빠름  ( O(1) > O(n) )
• 더블 연결리스트로 구현한 큐 ( QueueLinkedList ) 와 비교하면
• Space Complexity ( 공간복잡성 ) 측면에서 연결리스트 보다 더 좋습니다. 끝판왕인거지.^^
• '더블스택  으로 구현한 큐'( QueueDoubleStack ) 의 공간 복잡성 : 빠름.

•  '연결리스트로 구현한 큐'( QueueLinkedList )의 공간 복잡성 : 메모리 접근 시간이 느림.
  

Swift4: 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!

전체 소스 파일