Swift) 큐(Queue) 구현 해보기

 

 

 

안녕하세요? 소들입니다 :)

훔... 제가 자료구조나 알고리즘 바보인ㄷ.. 😭 뿌에엥

오늘부터 한번 공부를 해보려고..!!!!!1 마음을 먹었습니다..!!!!!!11

(시작하는 마음에서 이전 제로 베이스에서 짠 알고리즘 포스팅은 비공개!!!!)

 

따라서, 새로운 마음 가짐으로 :)

Swift에선 지원하지 않는 Queue에 대해 구현을 해보려고 해요!

뭐.. Queue는 FIFO고.. enqueue, dequeue 같은 것들이 있죠..!

 

파이썬은 Queue를 라이브러리로 지원 하던데 Swift는 음..슴...

그래서 어렵지 않으니 배열로 직접 구현을 해보겠음돠

 

뭐.. 나의 공부를 위한 것이니

이론은 다른 포스팅처럼 자세하게 다루진 않으렵니다ㅎㅎ....;

(만약 Queue가 뭔지 모르신다면 대략난감입니다)

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. Swift로 Queue 구현하기

 

음... 먼저 말했듯이 Swift는 Queue를 따로 지원하지 않음..

시스템적인 DIspatchQueue 이런 거 제외하고는..

 

따라서 구조체와 배열로 다음과 같이 만들 수 있음

 

 

struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

 

 

이런 식으로 구현하고, 실제 사용은 다음과 같이 하면 됨

 

 

var myQueue = Queue<Int>()
myQueue.enqueue(10)
myQueue.dequeue()

 

 

흠..... 기초라서 어려울 것은 하나 없다만,

근데 아무래도 배열로 구현을 하다 보니까, 효율면에서 위 방식은 문제가 될 수 있음..!

뭐 문제까진 아니지만.. 개선의 여지랄까?

 

어떤 것이냐면,

배열에서 가장 마지막 element를 삭제하는 것은

맨 뒤에 자신만 삭제하면 되니까, O(1) 로 문제가 되지 않음

근데 만약 Queue는 마지막이 아닌 처음 element를 삭제하잖음??

 

 

 

 

그럼 다음과 같이 element가 하나씩 당겨지는 과정이 있음 즉, O(n) 이라는 것임

때문에, Queue 특성 상 Head의 element를 삭제하는 

dequeue의 작업은 오버헤드가 발생한다는 말임 (크진 않겠지만..)

 

+ 이것은 배열 특성으로, 삭제 뿐만 아니라 추가할 때도 똑같음

append의 경우 O(1), insert의 경우 O(n)

하지만, Queue에서 enqueue 작업은 늘 append이니, dequeue만 다룸

 

따라서 찾아보니까, 

다음과 같이 dequeue에 조금 더 효율적인 Queue를 만든다고 함

 

 

 

 

2. Dequeue에 효율적인 Queue

 

앞서 살펴봤듯이,

Queue에서 dequeue하는 작업에서 오버헤드가 발생하는 것을 봤음

따라서, 이를 좀 더 효율적으로 개선하여,

dequeue 시 배열을 앞당겨주는 작업을 최소화 하는 것임!!

어떻게?

 

실제 배열의 Head를 삭제하는 것이 아닌,

현재 Head를 가리키고 있는 포인트를 변경시켜서

dequeue가 호출될 때마다 하던 배열의 삭제 작업을 하지 않는 것임

대신, 더 이상 필요없는 dequeue된 element는 nil로 만들어주는 것임

 

뭐 이론으론 이해 안 갈 수도 있으니

 

 

 

 

이런 식으로, head라는 것을 두어서

dequeue 시 반환되어야하는 element의 index를 들고 있는 것임!

 

그러면 dequeue가 불릴 때마다,

element를 삭제하고, 나머지 element를 당겨오는 과정이 없기 때문에

오버헤드가 발생하지 않음, 즉 O(1) 될 수 있음!

 

대신!!

만약 enqueue를 계속 할 수록, nil로 할당된 dequeue된 element를 언제까지 들고 있을 순 없으니까,

적정한 때에 dequeue 된 element들을 remove하는 작업을 해주는 것임

(뭐 예제론 50개라 했는데, queue의 1/4이 쌓였을 때나 알아서 설정하면 될듯)

 

먼저, 코드로는 다음과 같이 구현할 수 있음

 

 

struct Queue<T> {
    private var queue: [T?] = []
    private var head: Int = 0
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        guard head <= queue.count, let element = queue[head] else { return nil }
        queue[head] = nil
        head += 1
        
        if head > 50 {
            queue.removeFirst(head)
            head = 0
        }
        return element
    }
}

 

 

이땐 dequeue 된 element에 nil을 할당하기 위하여

queue의 자료형이 Optional로 변함 ([T?])

 

쨌든 이런 방식으로 dequeue의 시간복잡도를 줄이게

Queue를 만들 수도 있움!! :)

 

 

 

 

3. Protocol을 채택한 Queue도 있는데..

 

음.... 찾아보니까 이 Queue에다가

Sequence, Collection Protocol을 준수시켜서 구현한 예제가 꽤 있는데...

 

솔직히 말하면 구현이 어려운 건 아님...!

근데.. 왜..? 라는 생각이 들어서..

 

Queue라는 것은 일반적으로

FIFO, 즉 enqueue, dequeue 작업만 해도 충분하다 생각 하는데,

굳이 Protocol을 채택해서 Subscript로 접근하고 하는 게 이해가 안가서.. 🥶

그럴 거면 enqueue, dequeue만 있는 그냥 배열 아닌가..

 

몰라ㅎ 튜닝의 끝은 순정이랬나ㅎ

그냥 난 굳이 Queue에 Sequence, Collection 프로토콜을 준수시켜야할 필요성을

아직! 못느껴서 혹여나 준수해서 쓸 일이 생기면 그때 추가하겠음

 

 

 

 

 

 

.

.

.

자료구조 & 알고리즘 공부 1일차 소들이 화이팅!