Queue 구현하기

Stack에 이은 Queue 구현입니다!

 

Queue는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)이라는 특징을 가진 자료구조입니다.

 

Stack의 경우에 들어오는 데이터들이 쌓여서 위에부터 걷어내는 자료구조였다면,

Queue는 먼저들어온 놈을 나중에 들어온 놈과 상관 없이, 먼저 내보낸다~ 라는 겁니다.

 

 

Queue의 구현요소로는

1. Queue안에 있는 현재 데이터 갯수

2. Queue가 비었는지 확인 할 수 있는 Bool값

3. Queue에 데이터를 넣는 enqueue()

4. Queue에서 데이터를 빼는 dequeue()

 

처럼 크게 4가지 정도가 있습니다!

 

 

바로 구현해볼까요?!

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

 

 사실 정말 어렵지 않습니다. 가장 기초적인 Queue의 형태이기 때문인데요!

dequeue()의 경우에만 Queue안에 데이터가 없을 수 있기 때문에, 옵셔널의 형태로 데이터를 반환해주게 되는 특징이 있습니다..ㅎㅎ

 

 

시간 복잡도 측면에서 생각을 해볼까요?

 

위와 같이 구현을 하게 된다면, Queue를 생성하게 되면 배열이 생성되는 것과 동일하기에..

enqueue()의 경우에는 배열의 가장 뒤에만 append를 해주므로, O(1)으로 항상 동일하지만,

dequeue()의 경우에는 배열의 가장 첫번째 데이터를 빼고, 나머지 데이터들의 index값을 하나씩 당겨주어야 하는 과정이 있기 때문에, O(n)의 복잡도를 가지게 됩니다!

 

 위와 같이 O(n)의 복잡도 가 싫다는 이유로, 데이터의 가장 처음 index값을 알려주는 head값을 만들어 dequeue()가 된다면, head값을 하나씩 뒤로 넘기는 Queue도 생각을 해볼 수 있게 됩니다ㅎ

 

 

 

그럼 이 Queue들을 언제 사용하게 될까요?

저희가 지금까지 많이 써왔던 DispatchQueue같은 작업이 그 예시가 될 수 있을 것 같습니다

 

DispatchQueue도 위에서 말한 특징이 있죠! 산발적으로 들어오는 데이터들을 순차적으로 다뤄주는 그런 특징이요!

 

 

사실 swift에는 python같은 언어와는 달리 Stack과 Queue가 내부 구현되어 있지 않은데요,

그 이유로는 일반 배열을 충분히 위와 같은 성격을 가질 수 있게 구현해 두었기 때문이라 생각합니다.

 

stack을 구현할때 사용한 popLast()와 오늘 정리한 queue에서의 removeFirst()같은 함수를 보면 그런 생각이 드네요!

 

오늘의 Queue도 간단해서 금방 끝났네요..ㅎㅎ

 

끗!