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

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

큐(Queue)란 무엇인가?

• 사람들이 음식점에 줄을 서고 있는 모습을 상상해보자, 먼저 줄은 선 사람이 먼저 가게에 들어갈 수 있다. 이러한 상황은 일상생활에서 자주 발생되는데 이러한 현상을 컴퓨터로 표한한 것이 ‘큐(Queue)’ 이다.

큐(Queue)의 특징

• ‘먼저 온 순서대로 먼저 작업을 해 준다.
• First - In - First - Out (FIFO) 이라고 부르기도 한다. 즉 큐는 FIFO 특성을 가진 자료 구조이다.

---

큐 (Queue) 구현

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

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

Queue Protocol 구현

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

}

---

QueueArray 구현 (배열로 구현한 큐)

//Queue Array
public struct QueueArray<T>: Queue {

    private var array = Array<T>()
    //제네릭 타입 T 로 Queue 프로토콜의 Element 타입 추론됨

    public init() {}

    //프로토콜에서 구현한 것들
    public var isEmpty: Bool {
        return array.isEmpty
    }

    public var peek: T? {
        return array.first
    }

    //큐 추가(큐 끝에)
    public mutating func enQueue(_ element: T) -> Bool {
        array.append(element)
        //append 수행속도는 0(1)
        //배열에 추가 할때마다 그 배열의 메모리크기의 2배씩 늘어난다. -> 스위프트 배열 구조의 특징
        return true
    }

    public mutating func deQueue() -> T? {
        return isEmpty ? nil : array.removeFirst()
        //비어있으면 nil리턴
        //제거의 연산속도는 0(n) , 첫 아이템 제거 연산이 0(n) 이기 때문에
    }
}

결과 확인

//QueueArray 출력
extension QueueArray: CustomStringConvertible {
    //CustomStringConvertible프로토콜을 채택한 객체를 출력할때 출력내용을 사용자화 해준다.

    public var description: String {
        return String(describing: array)
        //array 배열을 출력하도록 설정
    }
}

var queueArray = QueueArray<String>()
//인스턴스 생성
//제네릭 타입은 String, 이름 넣을 것이기 때문
queueArray.enQueue("철수")
queueArray.enQueue("영희")
queueArray.enQueue("민수")

print(queueArray) //출력
queueArray.deQueue() //가장앞에 있는 큐 제거
print(queueArray) //변경된 큐 출력

---

출처 : 스위프트 : 자료구조 큐 (1 / 4): Queue: #배열로 구현한 큐: #배열의원리: #swift :: 씩이 머릿속