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

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

---

큐 (Queue) 구현

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

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

---

Double Stack 이란? (위의 4가지 방법 중 가장 성능이 좋음)

• 더블 스택은 두개의 스택으로 큐를 구현하는 아이디어 입니다.
• 스택은 배열(Array)로 구현했었습니다
• 더블 스택은 배열의 마지막 요소를 제거하는 연산은 재정렬이 필요하지 않으므로 수행속도가 O(1)임을 활용한 방법입니다.

• Left Stack : deQueue 전용 스택, deQueue를 수행한 아이템들은 여기로 들어간다.
• Right Stack : enQeue 전용 스택, enQueue를 수행할 아이템들은 여기로 들어간다.
• enQeueu RightStack에 append 메소드 사용 하여 추가
• deQeueu 수행 시 Right Stack의 요소들을 거꾸로 정렬한 뒤, Left Stack에 옮기고 popLast()메소드 사용하여 마지막 값 제거
  • 거꾸로 정렬하는 이유는 수행속도를 빠르게 하기 위함.
  • 거꾸로 정렬한 Left Stack에서 마지막 요소를 제거하면 가장 첫번째의 1이 제거됨을 알 수 있다.

---

Queue 프로토콜

public protocol 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 }
    // 가장 앞의 큐를 알려줍니다. (제거하는 것은 아님)
}

Double Stack Queue 구현

public struct QueueDoubleStack<T>: Queue {
    private var leftStack = Array<T>() //deQueue 담당
    private var rightStack = Array<T>() //enQueue 담당

    public init() {}

    //MARK: Queue 프로토콜 사항들
    public mutating func enQueue(_ element: T) -> Bool {
        rightStack.append(element)
        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
        //왼쪽 스택에 값이 있을때 큐의 맨앞을 표현 하려면
        //거꾸로 정렬 되어 있기 때문에 스택의 마지막 값이 되므로 last
        //오른쪽을 먼저 확인하면 왼쪽에 값 남아 있을 가능성이 있기 때문에 주의
    }
}

extension QueueDoubleStack: CustomDebugStringConvertible {
    public var debugDescription: String {
        let printLast = leftStack.reversed() + rightStack
        //두 스택 모두가 큐의 전체 값이므로 전체 연결해서 표현
        return String(describing: printLast)
    }
}

---

결과 확인

var queueStack = QueueDoubleStack<String>() //인스턴스 생성
queueStack.enQueue("철수") //값 추가
queueStack.enQueue("미영")
queueStack.enQueue("은지")
print(queueStack) //전체 출력
queueStack.deQueue() //deQueue 해서 왼쪽으로 이동
print(queueStack) //제거 확인

---

출처 : 스위프트 : 자료구조 큐 (3 / 4): Queue: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음: #swift :: 씩이 머릿속