swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제

swift 자료구조 queue 코드로 정리 - 큐 일상생활 예제

 

자료구조 큐란

일상생활의 예를들어 보면 자료구조 큐는 마트에서 줄서는 구조와 같습니다.

또는 버스를 탈려고 줄을 선다던가, 영화관에서 줄을 서는 구조와 같습니다.

제일 앞에 있는 사람이 제일 먼저 서비스를 받겠죠? 제일 마지막에 있는 사람이 제일 마지막에 서비스를 받구요.

일상생활에서의 이런 구조를 그대로 옮겨온 자료구조가 바로 큐 입니다.

 

큐의 작동

큐는 필수적으로 2가지 역할이 필요합니다.

 

[1] 인큐(enqueue) : 데이터를 큐의 제일 뒤에 넣는 역할

[2]디큐(dequeue) : 큐의 제일 앞에 있는 데이터를 삭제 후 리턴하는 역할

 

그리고 부수적으로 큐가 비었는지 확인하는 역할과, 제일 앞의 데이터를 삭제하지 않고 리턴만 하는 역할 도 있습니다.

 

큐 자료구조를 구현할때 위의 내용을 반드시 구현해주어야 하기 때문에(부수적으로 구현해야될 함수도 구현하기로함) 아래 처럼 프로토콜을 작성해줍니다.

 

public protocol Queue {
    associatedtype Element
    
    //큐 제일 뒤에 element 요소를 삽입한다. 성공하면 true를 리턴한다.
    mutating func enqueue(_ element: Element) -> Bool
    
    //큐에서 제일 앞에 있는 element 요소를 삭제하고 리턴한다.
    mutating func dequeue() -> Element?
    
    //큐가 비었는지 체크 한다.
    var isEmpty: Bool { get }
    
    //큐의 가장 앞에 있는 요소를 리턴한다.
    var peek: Element? { get }
}

 

그리고 구조체로 QueueArray를 생성합니다. 스택과 마찬가지로 array로 큐를 구현해 보도록 합니다.

 

/// protocol Queue를 채택한 QueueArray 작성
/// protocol Queue의 associatedtype Element 는 T에 의해 추론된다.
public struct QueueArray<T>:Queue{
    public typealias Element = T
    
    // 큐를 array로 구현한다.
    private var array:[T] = []
    public init(){}

}

//큐 출력용
extension QueueArray:CustomStringConvertible{
    public var description: String{
        return array.description
    }
}

 

인큐(enqueue)

인큐는 큐의 제일 마지막에 요소를 삽입하는 역할 입니다. 스위프트 내장 라이브러리에는 배열에 append 함수를 호출하면 배열의 제일 마지막에 값을 넣어줍니다.

    /*
        큐의 제일 마지막에 요소 삽입 O(1)
        배열이 꽉차면 O(n)의 처리 속도로 배열을 조정한다.
        (새 배열을 위한 메모리 할당과 복사)
        하지만 매번 배열의 크기를 두배로 늘리기 때문에 처리 속도는 O(1) 이다.
    */
     public mutating func enqueue(_ element: T) -> Bool {
        array.append(element)
        return true
    }

 

디큐(dequeue)

디큐는 큐의 제일 앞의 요소를 삭제하고 리턴합니다. 인큐와 마찬가지로 스위프트 내장 라이브러리에는 배열에 removeLast를 호출하면 배열의 제일 앞에 있는 요소를 삭제 후 리턴해 줍니다.

    /*
     큐의 제일 첫번째 요소 삭제 후 리턴
     배열이 비었으면 nil 리턴
     처리 속도는 O(n)
     이유는 첫번째 요소 삭제후 남아있는 요소들을 앞으로 한 칸씩 이동시켜야 되므로.
    */
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : array.removeFirst()
    }

 

empty와 peek

empty와 peek도 스위프트 내장 배열 라이브러리에 isEmpty와 first 프로퍼티를 사용해서 처리해 줍니다.

    //큐가 비었는지 체크. O(1)
    public var isEmpty: Bool{
        return array.isEmpty
    }
    
    //큐의 제일 앞에 있는 요소 꺼내기. O(1)
    public var peek: T?{
        return array.first
    }

 

큐 테스트

아래와 같이 큐를 만들고 세 명의 이름을 넣어줍니다. 그리고 dequeue 함수를 이용해서 제일 앞의 이름을 삭제 후 리턴합니다.

var queue = QueueArray<String>()
queue.enqueue("park")
queue.enqueue("kang")
queue.enqueue("kim")

print("queue:\(queue)")
queue.dequeue()

print("dequeue 후 queue:\(queue)")

출력

queue:["park", "kang", "kim"]
dequeue 후 queue:["kang", "kim"]

 

성능

array로 구현한 큐의 성능

 

Queue.zip

0.02MB

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

 

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication

 

https://www.raywenderlich.com/books/data-structures-algorithms-in-swift/