[Algorithm] 큐 ( Queue )_자료구조(DataStructure_Swift) [2/4]

큐 ( Queue )_자료구조(DataStructure_Swift)

---

Doubly Linked List 이용한 큐 (Queue) 구현

아래와 같은 총 4가지의 큐를 구현할 예정입니다.
각각의 여러 방법에는 ‘성능 차이’ 가 있습니다만
여러 큐를 구현하며 똑같은 큐를 구현하되, 빠르고 효율적으로 구현하자는 취지입니다.

1. Array를 이용한 큐 구현
2. Doubly Linked List 이용한 큐 구현
3. Two Stack을 이용한 큐 구현
4. Ring Buffer를 이용한 큐 구현

---

연결 리스트가 가지는 기본적인 Node 클래스

public class Node<T> {

    public var value: T // 값
    public var next: Node<T>? // 다음 노드 참조
    public var previous: Node<T>? // 이전 노드 참조 : 여기가 단순연결리스트와 차이.

    public init(value: T) {
        self.value = value
    }
}

extension Node: CustomStringConvertible {

    public var description: String {
        return String(describing: value)
    }
}

Queue 프로토콜

    associatedtype Element
    //associatetype 키워드는 프로토콜 정의 시, 제네릭 타입처럼 일반화 시킨 타입을 지정할 때 사용 합니다.
    //이 프로토콜을 채택한 것의 타입이 Int라면 아래에 정의한 메소드들에서의 Element와 전부 Int가 됩니다.
    //따라서, Element는 이 프로토콜을 채택하는 객체가 자신이 원하는 타입의 Queue를 작성할 수 있도록 해 주는 것입니다.

    mutating func enQueue(_ element: Element) -> Bool
    //큐 끝에 새로운 큐를 추가하고, 성공여부 반환, 구조체가 이 프로토콜을 채택할 경우를 대비해 mutating Keword 추가

    mutating func deQueue() -> Element?
    //가장 먼저 들어온 앞의 큐를 제거하고 제거한 큐 반환

    var isEmpty: Bool { get }
    //큐가 비어있는지를 알려주기 위한 읽기전용 프로퍼티(get)은 읽기 전용

    var peek: Element? { get }
    // 가장 앞의 큐를 알려줍니다. (제거하는 것은 아님)
}

---

DoublyLinked 클래스

• 연결 리스트의 확장된 개념입니다.
• 연결리스트는 자신의 노드값과 다음 노드를 가리키는 '참조 정보'로 구성되지만 여기서는 현재노드가 다음노드의 '참조 정보' 뿐만 아니라 이전 노드의 '참조 정보'도 가지고 있다는 것이 '더블 연결리스트' 입니다.

 

public class DoublyLinkedList<T> {

    private var head: Node<T>? // 헤드 노드
    private var tail: Node<T>? // 테일 노드

    public init() { }

    public var isEmpty: Bool { // 헤드노드가 비었으면 연결리스트가 비어 있는 것이다.
        return head == nil
    }

    public var first: Node<T>? {
        // head 노드는 항상 가장 앞에 있으므로 first 프로퍼티로 설정하면 됩니다.
        // 옵셔널임을 유의 (리스트가 비어있으면 nil 이니까요^^)
        return head
    }

    public func append(_ value: T) {
        let newNode = Node(value: value) // 새로 들어올 노드 초기화하고 newNode 에 저장.

        guard let tailNode = tail else { // tail 이 nil 인지 검사 = 리스트가 비어있는지 검사.
            head = newNode // 비어있으면 head, tail 모두 설정해줌.
            tail = newNode
            return
        }
        // 비어있지 않다면 실행.
        newNode.previous = tailNode // 새로 들어올 노드의 '이전 참조' 에 현재 tail 노드로.
        tailNode.next = newNode // 현재 tail 노드의 '다음 참조' 를 새로 들어올 노드로.
        tail = newNode // 연결정보 완료했으면 마지막으로 새로운 테일노드 설정해줌.
        // 정리하면 새로 들어올 노드를 들어올 당시의 'tail 노드' 와 연결을 서로 해주고
        // 들어올 당시의 'tail 노드' 는 그 당시에는 마지막 노드지만 이제는 마지막 노드의 '이전노드' 가 되므로
        // 새로 들어온 노드가 진짜 'tail' 노드가 되는 것이죠.
    }

    public func remove(_ node: Node<T>) -> T {
        let prev = node.previous // 제거할 노드의 이전참조
        let next = node.next // 제거할 노드의 다음참조

        if let prev = prev { // 가장 앞의 노드면 prev 가 nil 이쥬?
            prev.next = next
            // 가장 앞의 노드가 아니면 제거되는 노드의 이전노드의 다음노드가 제거되는 노드의 다음노드가 되쥬?
        } else {
            head = next // 가장 앞의 노드면 head 노드 새로 설정, 제거되는 노드 다음노드가 새로운 head 노드 됨.
        }

        next?.previous = prev // 제거 하는 노드의 다음노드의 이전노드 참조가 제거하는 노드의 이전노드로 설정.

        if next == nil { // 제거하는 노드가 마지막 노드라면
            tail = prev // tail 노드 새로 설정해줌.
        }

        // 마지막에 할일을 다 한 참조정보들 메모리에서 없애기.
        node.previous = nil
        node.next = nil

        return node.value
    }
}

extension DoublyLinkedList: CustomStringConvertible {

    public var description: String {
        var string = ""
        var current = head // head 노드에서 시작!
        while let node = current {
            string.append("\(node.value) -> ")
            // 문자열 메소드인 append 사용해서 노드의 값을 연결리스트 처럼 -> 로 이어 붙인다.
            current = node.next
            // 다음 반복을 위해 current 가 next 가지게 하기.
        }
        return string + "end"  // 마지막에 end 를 붙여서 리스트의 끝이라는 것을 표현.
    }
}

QueueLinkedList 클래스

• 배열로 구현한 큐와 유사한 구조, 큐를 단지 연결리스트로 구현한 것 뿐입니다.
• 연결리스트의 메소드와 프로퍼티 활용

public class QueueLinkedList<T>: Queue {
    private var list = DoublyLinkedList<T>()
    //Doubly 연결리스트의 인스턴스 생성하기!
    public init() {}

    public func enQueue(_ element: T) -> Bool { //큐에 값 추가 하기
        list.append(element) //연결리스트의 append 메소드로 큐에 값을 추가 한다.
        return true
    }

    public func deQueue() -> T? { //큐에 값 제거하기
        guard !list.isEmpty, let element = list.first else {
            // 연결리스트 비어있지 않고
            // 연결리스트의 first는 옵셔널로 선언 되어 있으므로 바인딩 해제
            return nil
        }
        return list.remove(element) //연결리스트의 remove 메소드로 첫 번째 값을 제거 시킵니다.
    }

    public var peek: T? { //큐의 가장 앞의 값을 반환해서 얻습니다.
        return list.first?.value
    }

    public var isEmpty: Bool { //연결리스트의 isEmpty를 읽습니다.
        return list.isEmpty
    }
}

extension QueueLinkedList: CustomStringConvertible {
    public var description: String {
        return String(describing: list)
    }
}

---

실행 결과

var queueLinkedlist = QueueLinkedList<String>()
queueLinkedlist.enQueue("철수")
queueLinkedlist.enQueue("유진")
queueLinkedlist.enQueue("주혁")

print(queueLinkedlist)
queueLinkedlist.deQueue()
print(queueLinkedlist)

성능 비교

• ArrayQueue 와 비교
• 장점
• deQueue 메소드의 수행속도가 O(1) 로 빠릅니다. ( ArrayQueue 는 Q(n)임. )
• 이는 연결리스트의 특징인 아이템이 제거되도 나머지 요소들이 재정렬하지 않아도 되기 때문입니다.
• 단점
• 연결리스트를 추가할 때 수행하는 동적할당이 상대적으로 큰 메모리를 소모합니다.
• 값, 이전노드 참조, 다음노드 참조 이렇게 3개를 포함하기 때문입니다.

---

전체 코드

MyPlayground.playground.zip

0.01MB

---

출처 : the-brain-of-sic2.tistory.com/20?category=779571