[자료구조 with 코틀린] 3. Queue

1. 개념

먼저 들어간 데이터가 먼저 나오는 자료구조입니다.

FIFO(First In First Out)이라고도 합니다.

안드로이드에서 Looper를 사용할 때 메시지 큐에 사용되는 자료구조입니다.

2. 시간복잡도

a. 탐색

앞선 스택과 마찬가지로, 특정 데이터를 찾을 때까지 탐색해야 하므로 O(N)의 시간복잡도를 가집니다.

b. 삽입 및 삭제

모두 O(1)의 시간복잡도를 가집니다.

3. 구현

LinkedList를 사용하여 구현하는 것이 좋습니다. 삽입 및 삭제에 O(1)의 시간복잡도를 가지기 때문입니다.

class Queue<E> {
    private var head : Node<E>? = null

    inner class Node<E>(
        var data: E,
        var next: Node<E>?
    )

    fun enqueue(item: E) {
        if (head == null) {
            head = Node(item, null)
            return
        }
        var thisNode = head
        while (thisNode?.next != null) {
            thisNode = thisNode?.next
        }
        thisNode?.next = Node(item, null)
    }
    fun dequeue() : Node<E>? {
        if (head == null) {
            return null
        }
        var nextNode = head?.next
        var thisNode = head
        head = nextNode
        return thisNode
    }
    fun isEmpty() : Boolean {
        return head == null
    }
}

4. 스택을 사용해 구현

큐는 먼저 들어온 데이터가 먼저 나오는 구조입니다.

반면 스택은 마지막에 들어온 데이터가 먼저 나오는 구조입니다.

이를 고려하면, 두 개의 스택을 사용하면 큐를 구현할 수 있습니다.

로직은 다음과 같습니다.

1) 스택 A에 데이터를 삽입한다.

2) 추출시, 스택 A의 모든 데이터를 스택 B로 옮긴다.

이때 스택 A에 있던 모든 데이터의 순서가 역전되어 B에 담기게 된다.

3) 이후 스택 B에서 데이터를 추출하면, 가장 먼저 삽입한 데이터를 가장 먼저 추출할 수 있다.

코드는 다음과 같습니다.

class Queue<E> {

    private val enQueueStack = Stack<E>()
    private val dequeueStack = Stack<E>()

    fun enqueue(item: E) {
        enQueueStack.push(item)
    }
    fun dequeue() : E? {
        if (dequeueStack.size() == 0) {
            while(enQueueStack.peek() != null) {
                dequeueStack.push(enQueueStack.pop()!!)
            }
        }
        return dequeueStack.pop()
    }
    fun size() : Int {
        return enQueueStack.size()
    }

}