[스위프트 : 자료구조] 큐 : Queue : Sequence, Collection 프로토콜 지향 큐 구현하기

[스위프트 : 자료구조] 큐 : Queue : Sequence, Collection 프로토콜 지향 큐 구현하기

스위프트: Swift/자료구조 : Data Strutures in Swift 2018. 10. 10. 21:22

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

저는 Swift 와 iOS 를 공부하고 연구하는 학생입니다.

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

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

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

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

Swift version : Swift 4.2 Swift 언어
참고한 것들

DataStructures and Algorithms in Swift
Swift-Algorithm-club 깃허브
스위프트 데이터 구조와 알고리즘
Youtube
칸 아카데미

씩이 Github

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

스위프트로 구현한 자료구조 : DataStructures in Swift4

스위프트로 구현한 알고리즘 : Algorithms in Swfit4

Swift 주제별 분류

프로토콜 지향적인 큐 구현하기

아래와 같은 의문에서 시작하여 큐를 프로토콜 지향적으로 구현합니다.

스위프트는 프로토콜 지향 프로그래밍의 패턴이라는데 그게 뭔데?

배열이 채택하고 있는 Sequence , Collection 프로토콜이 뭐지?

내가 쓸 때가 있어서 나에게 맞는 큐 자료구조를 만들었다면, 실제로 많이 사용하는 배열처럼 쉽게 사용할 수 있게 만들 순 있을까?

큐에 프로토콜 지향을 적용해보자

여러 프로토콜을 활용해서 나에게 맞게, 쓸만하게 큐 자료구조를 만들어보자.
기본적으로 배열로 큐를 구현했고, '큐' 자체를 모르거나 큐를 구현하는 방법을 알고 싶으면 여기!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public struct Queue<T> {
    internal var data = Array<T>()
    public init() {}
    
    public mutating func dequeue() -> T? {
        return data.removeFirst()
    }
    
    public func peek() -> T? {
        return data.first
    }
    
    public mutating func enqueue(element: T) {
        data.append(element) 
    }
    
    public mutating func clear() {
        data.removeAll()
    }
    
    public var count: Int {
        return data.count
    }
    
    public var capacity: Int {
        get {
            return data.capacity
        }
        set {
            data.reserveCapacity(newValue)
        }
    }
    
    public func isFull() -> Bool {
        return count == data.capacity
    }
    
    public func isEmpty() -> Bool {
        return data.isEmpty
    }
}
 
Colored by Color Scripter
cs

CustomStringConvertible 프로토콜을 채택해서 내가 원하는 출력 나오게 하기

CustomStringConvertible 프로토콜은 인스턴스 메소드인 var description: String 을 작성해야 한다는 것을 명시해 놓은 프로토콜이야.
extension 을 사용해서 CustomStringConvertible 프로토콜 을 채택하고 프로토콜에 명시된 대로 description 을 작성하자.

1
2
3
4
5
extension Queue: CustomStringConvertible {
    public var description: String {
        return data.description + "가 내가 정의한 큐 설명입니다!"
    }
}
Colored by Color Scripter
cs

전 / 후 비교해서 Queue 인스턴스 출력해보자.

차이점이 보이지?

실행 코드

전

후

expressibleByArrayLiteral 프로토콜을 채택해서 내가 원하는 초기값 '스택' 에 설정하기.

큐를 만들려는데 1 ~ 5 까지 들어있는 상태부터 만들어야 하는 상황이면? ( 초기값이 있는 상태인 거지 )
귀찮게 enqueue() 5 번 써서 입력해줘야 하면 안쓰겠지?
배열이 초기화 하는 방식으로 쉽게 초기화 할 수 있도록 expressibleByArrayLiteral 프로토콜 채택하자.

1
2
3
4
5
6
7
8
9
extension Queue: ExpressibleByArrayLiteral {
    public typealias ArrayLiteralElement = T
    public init(arrayLiteral elements: T...) {
        for element in elements {
            self.data.append(element)
        }
    }
}
 
Colored by Color Scripter
cs

실행

배열 처럼 초기화 하고 출력해보면

나오쥬? 배열처럼 쉽게 초기화!

Sequence 프로토콜을 채택해서 각 요소별로 반복문을 사용할 수 있게 해보자

( for in Loop 에서 사용하기 )

예를들어 Array 구조체는 Sequence 프로토콜을 채택하고 있기 때문에 for 루프 에서 사용할 수 있는 거거든?

아래와 같이 for in 다음에 배열이 들어갔잖아.
여기에 배열이 들어갈 수 있는 이유는 배열인 Array 구조체가 Sequence 프로토콜을 채택하고 있기 때문이라는 말이야~
1
2
3
4
5
let array = ["하나", "둘", "셋"]

for i in array {
print(i+" , ") // 하나 , 둘 , 셋
}
cs

적용하기 전에 Sequence 프로토콜에 대해서 간단히 설명할게.

Sequence 프로토콜에 부합하는 타입은 for ... in 순환문으로 반복 순회할 수 있다.
이 프로토콜의 요구사항은 아래와 같다.

makeIterator() -> Self.Iterator 메소드
associatedtype Iterator : IteratorProtocol

IteratorProtocol 프로토콜 채택한 Iterator 가 필요.

IteratorProtocol 의 요구사항은 아래와 같습니다.

IteratorProtocol은 이해하기 어렵다면 '마우스 커서' 라고 생각할 수 있어.
for in 루프에서 마우스 커서 에 따라 하나씩 움직이면서 반복한다는 느낌으로.

구현

next() 부분

이 부분에서는 Queue 의 특성대로 들어온 순서대로, 가장 아래에 있는 값 부터 반환하면서 간다. 그래서 removeFirst()

반대로 스택의 경우에 popLast() 를 하는데 그 이유는 Stack 의 특성이 상자에 쌓는 것처럼 위에것 먼저 꺼낼 수 있기 때문이야.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public struct QueueIterator<T>: IteratorProtocol {
    var currentElement: [T]
    
    public mutating func next() -> T? {
        if !self.currentElement.isEmpty {
            return currentElement.removeFirst()
        }else {
            return nil
        }
    }
}
 
extension Queue: Sequence {
    public func makeIterator() -> QueueIterator<T> {
        return QueueIterator(currentElement: self.data)
    }
}
Colored by Color Scripter
cs

실행과 결과

결과의 출력이 처음에 enqueue 된 1부터 반복되서 Queue 자료구조의 특징을 잘 표현했고 for 반복문을 활용할 수도 있게 됬지?

Collection 프로토콜 채택해서 Sequence 를 보완하자.

collection 프로토콜 먼저 설명할게

Collection 프로토콜의 명세 ( 요구조건 ) by 요기 애플 개발자 문서

startIndex, endIndex 프로퍼티를 제공해야 한다.
인덱스를 이용해 구성요소를 접근하는 subscrip(_:) 를 구현해야 한다. 최소한 읽기용은 반드시 구현해야 한다.
내부에서 인덱스를 증가시키기 위해 index (after: ) 를 구현해야 한다.

Collection 프로토콜은 Sequence 프로토콜을 상속받아 구현한 것.

어떤 객체가 Collection 을 채택하고 구현했으면 자동으로 Sequence 의 동작은 사용할 수 있어 ( 예제에서 해볼 거야. )

Collection 이 가지는 특성들이 Seqeunce 의 특성을 모두 포함해서 자동으로 Sequence 까지 사용할 수 있는 것. ( 상속 관계에 있는거랑 관련이 있지? )
인덱스의 범위와 인덱스의 전진 연산 만으로 Sequence 가 정의한 명세들을 모두 구현할 수 있다는 말이지.

Sequence 가 지닌 문제점들을 해결했어.

모든 Collection 은 유한해 (finite)
원하는 index 를 사용해서 구성 요소( element )에 접근할 수 있어 == access 할 수 있어 == get ( 읽기 ) 가능해.

Collection 이 가지고 있는 특성들이 Sequence 의 그것들을 모두 포함하기

구현

MutableCollection 은 Collection 을 상속 받은 프로토콜이야. ( Array( 배열 )도 MutableCollection 을 채택했어 )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Collection
extension Queue {
    private func  checkIndex(index: Int) {
        if index < 0 || index > count {
            fatalError("Index out of range")
        }
    }
}
 
extension Queue: MutableCollection {
    
    public var startIndex: Int {
        return 0 
    }
    
    public var endIndex: Int {
        return count - 1
    }
    
    public func index(after i: Int) -> Int {
        return  data.index(after: i)
    }
    
    public subscript (index: Int) -> T { 
        get {
            checkIndex(index: index) // 아 매개변수로 들어온 index 구나.
            return data[index]
        }
        set {
            checkIndex(index: index)
            data[index] = newValue
        }
    }
}
 
Colored by Color Scripter
cs

실행과 결과

collection 프로토콜의 명세를 채택함으로써 index 와 subscript 를 사용할 수 있게 된 것들 실행한 거야~

스위프트 표준 라이브러리의 기본적인 타입들의 프로토콜 계층은 아래와 같아.

프로토콜 헷갈린다면 참조

전체 소스 코드

'스위프트: Swift > 자료구조 : Data Strutures in Swift' 카테고리의 다른 글

[스위프트:자료구조] Heap: 힙 자료구조 (1 / 2) : Heap 이란? (1)	2018.11.05
[스위프트:자료구조] 트라이: Trie: 문자열 찾기: 단어 찾기 (0)	2018.10.11
[스위프트 : 자료구조] 스택 : Stack : Sequence 프로토콜 지향 스택 구현하기 (0)	2018.10.10
[스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐 (1)	2018.10.01
스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제 (0)	2018.09.27

인기포스트 MORE POST

ABOUT ME

씩이 머릿속 씩이 머릿속

'스위프트: Swift > 자료구조 : Data Strutures in Swift' 카테고리의 다른 글

티스토리툴바

인기포스트 MORE POST

ABOUT ME

'스위프트: Swift > 자료구조 : Data Strutures in Swift' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바