[자료구조] Queue(큐) with Swift

안녕하세요. 개발하는 정주입니다.

 

오늘은 "Queue"를 정리하였습니다.

포스팅 하단에 Swift로 Queue를 구현하고 dequeue의 시간복잡도 개선, 테스트도 함께 진행했습니다.

 

---

Queue란?

Queue는 Stack과 함께 기본적인 자료 구조 중 한가지입니다.

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 일렬로 이루어진 줄을 생각하면 연상이 쉽습니다.

먼저 줄을 선 사람이 먼저 나갈 수 있는 것처럼 Queue도 먼저 넣은 데이터가 먼저 나오는 것입니다.

 

---

Queue의 동작

Queue는 크게 3가지 동작을 합니다.

• Enqueue : Queue의 맨 뒤에 원소를 추가합니다.
• Dequeue : Queue의 맨 앞 원소를 삭제합니다.
• Peek : 맨 앞에 위치한 데이터를 읽습니다.

Queue의 상태를 나타내는 변수는 아래 두 개입니다.

• front : 큐 맨 앞의 index
• back(rear) : 큐 맨 뒤의 index

아래에서 Swift로 구현한 Queue는 Enqueue, Dequeue, front만을 구현하였습니다.

 

---

Queue의 종류

Stack과 다르게 Queue는 몇 가지 종류가 있습니다.

 

선형 Queue

막대 모양인 Queue로 일반적으로 Queue라고 하면 이 선형 Queue를 의미합니다.

Queue의 마지막에 원소를 추가하고 맨 앞(front)의 원소를 뺍니다.

 

기본 Queue는 front를 감소시키는 방법이 없기 때문에 공간이 꽉 차게 되면 더이상 요소를 추가할 수 없습니다.

심지어 dequeue로 데이터가 빠져서 앞에 공간이 남아도 이 공간에 데이터를 추가할 수 있는 방법이 없습니다.

 

이를 보완하기 위해 원형 Queue라는 것이 탄생했습니다.

 

원형 Queue

선형 Queue의 문제점을 보완한 Queue입니다.

front가 back과 같아지면 Queue의 맨 앞으로 데이터를 넣어 원형으로 연결하는 Queue입니다.

즉, 맨 끝까지 데이터가 차고 맨 앞에 공간이 있다면 맨 앞에 데이터를 넣겠다는 의미입니다.

맨 뒤와 맨 앞이 연결되어 원형이라고 말하는 것이지요.

 

front를 추가로 조작해야 하지만 선형 Queue보다 메모리 효율면에서 우수합니다.

 

우선순위 Queue

Enqueue하는 것은 일반 Queue와 동일합니다.

하지만 Dequeue를 하는 것에 차이가 있습니다.

 

일반 Queue는 먼저 집어 넣은 데이터가 먼저 나오는 구조이지만 우선순위 Queue는 우선순위에 따라 나오는 순서가 결정됩니다.

넣는 순서에 상관 없이 우선순위를 매겨 이를 기준으로 Dequeue합니다.

 

우선순위 Queue는 Heap을 다룰 때 추가로 설명하겠습니다.

 

덱(Deque)

입구와 출구가 따로 존재하는 Queue와 달리 양쪽에서 모두 삽입, 삭제가 가능한 자료구조입니다.

Stack과 Queue의 특성을 모두 갖고 있으며 양쪽에서 삽입, 삭제가 필요한 경우 사용합니다.

 

---

Queue의 활용

Queue가 어떻게 사용되는지 알아보겠습니다.

• 어떠한 작업/데이터를 순서대로 실행, 사용하기 전 대기시킬 때
• 서로 다른 thread 또는 process 사이에서나 네트워크를 통해 자료를 주고 받을 때 자료를 일시적으로 저장할 때

 

운영체제에서의 Queue

운영체제에서 Queue는 아주 중요한 자료구조입니다. (뭔들 안 중요하겠냐마는...)

운영체제 포스팅은 아니므로 간단하게만 소개할 예정입니다.

 

운영체제에서 Queue는 Linked List로 이루어져 있습니다.

대표적으로 Buffer Queue와 Scheduling Queue가 있습니다.

• Buffer Queue : 데이터를 전송하는 동안 일시적으로 데이터를 보관하는 메모리의 Queue
• Scheduling Queue : CPU 할당을 얻기 위해 대기 중인 프로세스가 쌓이는 Queue

위처럼 운영체제는 I/O 작업의 데이터를 임시로 보관하거나 Scheduling을 위해 Queue를 사용합니다.

 

iOS에서의 Queue

iOS에서도 Queue는 중요한 자료구조입니다. 아마 Dispatch Queue라는 것은 들어보셨을 겁니다.

이 단어의 Queue가 바로 오늘 다루는 자료구조 Queue입니다.

 

Dispatch Queues

 

Dispatch Queue는 세 가지로 나뉩니다.

• Main Queue
  • 별도의 처리를 하지 않은 코드는 Main Thread에서 작업됩니다. Main Thread에서 작업된다는 것은 이 Task들이 Main Queue에서 대기한 뒤 Main Thread에 할당된다는 의미입니다.
  • 단 한 개만 존재하며 Serial 특성을 가진 Queue입니다. (한 개만 존재하므로 당연히 Serial 합니다.)
• Global Queue
  • Concurrent 특성을 가진, Task를 분산 시킬 수 있는 Queue입니다.
  • 여러 개의 Thread로 Task를 분산 시키기 때문에 순서가 중요하지 않은 작업을 Global Queue로 하면 유용합니다.
  • QoS(Quality Of Service)에 따라 6개의 종류(userInteractive > userInitated > default > utility > background > unspecified)로 나뉩니다.
• Custom Queue
  • Custom으로 만든 Queue입니다.
  • 기본적으로 Serial 특성을 가지지만 Concurrent로 설정할 수 있습니다.

 

---

Swift로 Queue 구현

Swift에서 Queue를 구현해보았습니다.

두 가지 버전으로 일반 Queue 버전과 Dequeue의 시간복잡도를 개선한 버전입니다.

 

일반 Queue 버전

struct Queue<T> {
    private var queue: [T] = []
    
    public var size: 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()
    }
}

일반적인 Queue 버전입니다.

배열을 이용해 구현했으며 enqueue는 append(), dequeue()는 removeFirst()로 구현하였습니다.

 

dequeue의 removeFirst()는 시간복잡도가 O(n)입니다.

맨 앞의 원소를 빼내면 이후의 모든 원소를 앞으로 당기는 작업이 필요하기 때문입니다.

 

이것을 개선한 것이 아래의 버전2입니다.

 

시간복잡도 개선 버전

struct Queue2<T> {
    private var queue: [T?] = []
    private var front: Int = 0
    
    public var frontValue: Int {
        return self.front
    }
    
    public var size: 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 front <= size, let element = queue[front] else { return nil }
        queue[front] = nil
        front += 1
        return element
    }
}

dequeue의 시간복잡도를 개선한 버전입니다. front를 추가하고 dequeue를 수정하였습니다.

 

기존의 removeFirst() 대신 nil로 초기화를 하며 front를 이용해 index만 증가 시킵니다.

그럼 데이터는 삭제하되 공간은 그대로이기 때문에 앞으로 당기는 작업이 필요 없습니다.

 

따라서 이 버전의 dequeue는 O(1)의 시간복잡도를 가집니다.

 

실행 속도 비교

정말 개선이 되었는지 확인하기 위해 테스트를 해보았습니다.

var myQueue = Queue<Int>()
var myQueue2 = Queue2<Int>()

let times = 1000000 //100만
let workingCheck = 100000
var durationTime = 0.0, startTime = 0.0

startTime = CFAbsoluteTimeGetCurrent()

작업

durationTime = CFAbsoluteTimeGetCurrent() - startTime
print("queue1 enqueue: \(durationTime)\n")

Queue와 Queue2에 대해 총 100만 회를 enqueue하고 dequeue하면 각각 얼마나 소요될까 측정해보았습니다.

 

100만 회로 한 이유는 Swift 자체의 느린 속도때문인지 아니면 Xcode 문제인지 반복 속도가 너무 느려서 타협한 횟수 입니다.

1억으로 하고 싶었는데 아쉽네요.

 

일반 Queue 결과

일반 Queue의 결과입니다.

 

개선 Queue 결과

개선된 Queue의 결과입니다.

enqueue의 속도는 Q1과 Q2가 동일합니다. 왜냐하면 enqueue는 O(1)로 시간복잡도가 동일하기 때문입니다.

하지만 dequeue는 차이가 매우 심한 것을 볼 수 있습니다.

Q1은 O(n)의 시간복잡도로 인해 Q2에 비해 약 200배 느린 모습을 볼 수 있습니다.

물론 출력, 조건문 등 다른 변수가 있지만 그럼에도 확연히 느리다는 것은 확실합니다.

 

 

Q2를 이용해 1억 회 반복한 결과입니다.

첫 번째 테스트 보다 100배 더 많이 반복했지만 그럼에도 Q1보다 빠른 결과를 얻었습니다.

 

---

이렇게 Queue 정리를 마무리 합니다.

removeFirst()가 비효율적이다라는 것만 알았지 이정도의 차이가 있을 줄은 몰랐습니다.

역시 자료구조 포스팅을 시작하길 잘했다고 생각하빈다.

 

잘못된 점이 있다면 댓글로 알려주시면 감사하겠습니다.

감사합니다.