[DataStructure] 큐 1부

0. 서론

만약 데이터가 물밀듯이 쌓여 처리할 수 있는 속도보다 빠르다면, 그동안 쌓이는 데이터는 어떻게 해야 좋을까요?
음식점 안에 사람이 많아 자리가 없으면, 사람들은 줄을 서죠. 자리가 생기면, 먼저 온 사람이 먼저 자리에 앉듯이
데이터도 줄세워 처리를 기다리게 할 수 없을까요? 

들어온 순서대로 데이터를 처리하는 선입 선출을 위한 자료구조, 이번 글은 큐에 대해 다뤄보겠습니다.

1. 구조

내가 먼저야!
선입 선출, 어린 아이들도 알고있는 세상의 이치입니다. 먼저 무언가를 한 녀석이 우선권을 갖는다!
큐는 데이터를 줄세워 처리를 대기시킵니다. 처리가 끝나면, 먼저 들어온 데이터를 먼저 처리합니다.
데이터는 자아가 없으니 서로가 먼저라고 우길 일은 없겠습니다만, 오히려 서로가 아무말도 없어 골치인 녀석들인 데이터는
사용하려는 사람이 처리 순서를 지정해주어야 합니다.

Swift에서 사용자가 데이터를 선입선출의 형태로 처리하기 위해서 사용할 수 있는 방법은 여러가지가 있을 수 있겠죠.
그러나 우리는 개발자이므로, 선입선출에 있어 개발자끼리의 약속인 큐(queue)를 사용하는것이 이롭습니다.
소스코드에 큐라는 단어를 보는것만으로도, 데이터를 선입선출로 처리하겠다는 정보를 줄 수 있으니 말이죠!
약속이란 참 편리한 물건입니다.

2. 구현

큐를 구현하는 방법 또한 여러가지가 있을 수 있겠습니다만, 먼저 스택 2개를 사용하여 간단히 구현해보겠습니다.
스택 2개로 어떻게 큐를 구현하겠다는건지 궁금하지 않으신가요? 적어도 저는 궁금했습니다.

아이디어는 다음과 같습니다.

• enqueue시 입력을 담당하는 스택에 데이터를 append한다.
  이로 인해 먼저 들어온 데이터가 맨 앞, 나중에 들어온 데이터가 맨 뒤에 위치한다.
• 출력을 담당하는 스택에, 입력용 스택을 뒤집어 복사한다.
  이로 인해 먼저 들어온 데이터가 맨 뒤, 나중에 들어온 데이터가 맨 앞에 위치한다.
• popLast 따위를 활용하여 dequeue할 때, 상기 과정에 의해 해당 요소는 먼저 들어온 데이터이다.

위의 과정대로라면 append와 popLast 모두 O(1)이므로 상수시간 내에 수행할 수 있습니다.
단, 스택을 뒤집어 복사하는 과정을 제외한다면 말이지요.
Swift는 Array 내의 요소를 뒤집은 Array를 반환해주는 메소드 reversed()를 지원합니다만
해당 이름으로 정의된 메소드가 복수개이며, 따라서 반황형에 따라 O(1) 또는 O(n)인 메소드가 동작합니다.
(여러 블로그에 해당 메소드가 O(1)으로 동작한다는 설명이 많은데, 아무리 quick view는 그렇지 않았기에 알아보았습니다)

• 반환형이 Array일 경우
  이는 Sequence 에 구현돼있는 메소드로, 복사한 Array의 모든 요소를 Swap한 결과를 반환합니다.
  n개의 데이터 중 n/2개에 접근하므로 O(n)의 Cost가 발생합니다. 소스코드 링크
  
• 반환형이 ReversedCollection일 경우
  이는 BidirectionalCollection에 구현돼있는 메소드로, array를 거꾸로 접근하도록 래핑한 자료형인
  ReversedCollection를 반환합니다. 소스코드 링크
  

RerversedCollection은 RangeReplaceableCollection Protocol을 채택하고 있지 않기 때문에, popLast등을 사용할 수 없습니다.
따라서 Sequence에서 제공하는 reversed()를 사용하게 되고, 이는 O(n)의 Cost가 발생하기에 deque시에 outbox가 비어있을 때 O(n), 그렇지 않다면 O(1)의 Cost가 발생하게 됩니다.

요약하면, dequeue시에 outbox에 있는 요소가 적을수록, 자주 dequeue할 수록 dequeue는 더 자주 O(n)의 Cost가 발생하겠군요.

이를 해소하기 위해 front의 위치를 기억하는 인덱스를 사용하거나, 링크드 리스트를 사용하는 등의 방법이 있겠습니다만..!
계속 진행하겠습니다.

struct Queue<T>{
    fileprivate var inbox: [T] = []
    fileprivate var outbox: [T] = []
    init(inbox: [T] = [], outbox: [T] = []) {
        self.inbox = inbox
        self.outbox = outbox
    }
}

 

아이디어대로 큐에 들어오는 데이터를 담당하는 inbox, 나가는 데이터를 담당하는 outbox를 생성하였습니다.
생성자를 통해 이미 존재하는 Array로 큐를 생성할 수 있군요

    mutating func enqueue(element: T){
        inbox.append(element)
    }
    mutating func dequeue()->T?{
        if outbox.isEmpty{
            //outbox.isEmpty == true 일때만 O(n)인 reverse()를 사용하기때문에 전체적으로는 O(1)이라고 할 수 있음
            outbox = inbox.reversed()
            //Array.removeAll()은 keepingCapacity가 false일 때, O(1)의 Performance를 갖는다.
            //https://stackoverflow.com/questions/54133045/performance-array-removeall-vs
            inbox.removeAll()
        }
        return outbox.popLast()
    }

기본적인 삽입, 삭제 연산인 enqueue와 dequeue입니다.
dequeue시 reversed 메소드를 사용하고, 이때 inbox를 removeAll 하고 있습니다.
(removeAll()을 호출하는것과 []를 대입하는 것은 어떤 차이가 있는지 궁금하지 않으신가요? 그것은 따로 포스팅하도록 하겠습니다.)

    var isEmpty: Bool{
        return outbox.isEmpty && inbox.isEmpty
    }
    var front: T?{
        return outbox.isEmpty ? inbox.first : outbox.last
    }
    var rear: T?{
        if outbox.isEmpty { return inbox.last }
        return outbox.first
    }
    var count: Int{
        return outbox.count + inbox.count
    }

큐의 상태와 가장 최근에 추가한 요소 rear, 가장 처음에 추가한 요소 front 프로퍼티를 갖습니다.

전체 소스코드입니다.

struct Queue<T>{
    fileprivate var inbox: [T] = []
    fileprivate var outbox: [T] = []
    init(inbox: [T] = [], outbox: [T] = []) {
        self.inbox = inbox
        self.outbox = outbox
    }
    var isEmpty: Bool{
        return outbox.isEmpty && inbox.isEmpty
    }
    var front: T?{
        return outbox.isEmpty ? inbox.first : outbox.last
    }
    var rear: T?{
        if outbox.isEmpty { return inbox.last }
        return outbox.first
    }
    var count: Int{
        return outbox.count + inbox.count
    }
    mutating func enqueue(element: T){
        inbox.append(element)
    }
    mutating func dequeue()->T?{
        if outbox.isEmpty{
            //outbox.isEmpty == true 일때만 O(n)인 reverse()를 사용하기때문에 전체적으로는 O(1)이라고 할 수 있음
            outbox = inbox.reversed()
            //Array.removeAll()은 keepingCapacity가 false일 때, O(1)의 Performance를 갖는다.
            //https://stackoverflow.com/questions/54133045/performance-array-removeall-vs
            inbox.removeAll()
        }
        return outbox.popLast()
    }
}

마무리

이로써 기본적인 사용을 위한 구현은 끝입니다.
왜 Swift는 큐를 내장하지 않아서.... 큐를 쓸 때 마다 이 고생을....

큐를 구현하는 여러가지 방법 중, 스택을 1개만 사용하여 구현하는 방법 또한 존재합니다.
그것은 다음 포스팅에서!

2부에서 뵙겠습니다.