큐(Queue)

큐 (Queue)란?

최근에 포켓몬 빵을 사기 위해 마트 오픈 시간 전에 줄은 선다는 이야기를 전해 들었다. 이와 같이 ‘줄서기’에서 줄이 영어로 Queue 이다.

그럼 Queue타입의 특징을 알아보자.

큐는 스택과 다른 점은 대표적으로 FIFO(First In First Out) 이다. 줄서기 처럼 먼저 들어온 것이 먼저 나가게 되는 구조이다.

enqueue(줄 서기)를 할 경우 줄이 없을 경우 처음이자 끝에 서게 되고, 줄이 있을 경우 가장 뒤에 서는 특징이 있다.

dequeue(줄을 빠져 나가는 것)은 FIFO와 같이 줄의 가장 앞에 있는 값이 빠져 나간다.

이러한 특성을 갖고 Queue를 구현해보았다.

이와 같이 Array로 Queue를 구현하게 되었을 경우 문제점이 발생되었다.

기능적으로는 전혀 문제가 없지만 개발자라면 메모리 절약에 중점을 두어야 하기 때문에 시간 복잡도에 관해 문제를 찾게 되었다.

dequeue를 할 경우 removeFirst() 메소드를 이용하게 되는데 이 메소드의 시간 복잡도가 O(n)이라는 것이다.

그래서 이 문제를 해결할 방법 2가지를 찾게 되었다.

첫번째는, Linked List 이고, 두번째는 DoubleStack을 이용하는 것이었다.

그래서 Linked_List를 이용하여 만들어봤다.

class Queue<T: CalculateItem> {
    private var list = LinkedList<T>()
    
    public var count: Int {
        return list.count
    }
    
    public var isEmpty: Bool {
        return list.isEmpty
    }
    
    public var firstValue: T? {
        return list.returnFirst()?.value
    }
    
    public func enqueue(_ element: T) {
        list.append(element)
    }
    
    public func dequeue() -> T? {
        return isEmpty ? nil : list.removeHead()?.value
    }
    
    public func removeAll() {
        list.removeAll()
    }
}

여기서 또 !! 문제점이 발생되었다.

Linked_List를 이용했을 경우 Node 클래스를 만들어 주어야 되는데 Queue는 구조체로 만드는 것이 더 적합하나, 구조체의 프로퍼티 중에 class의 인스턴스로 구현된 것이 있다면 클래스로 정의를 해주어야 된다는 것을 알게되었다. 왜냐하면 구조체의 특징인 immutable이라는 특징을 이용할 수 가 없기 때문이다. (즉 메모리에 참조 타입으로 올라간다.) 그래서 DoubleStack 구조가 큐(Queue)에 가장 적합하다고 생각하게 되었다.