[자료구조] 큐-2 (원형 큐)

기존의 선형 큐는 dequeue를 하면 앞 부터 쌓였던 데이터가 빠져나간다. Head는 빠져나간 자리의 다음 데이터를 가리키게 되며 비어있는 자리로는 데이터를 추가 할 수 없게 된다. 굳이 재사용을 하겠다면 dequeue를 하고 비어있는 자리를 메꾸기 위해 뒤 데이터들을 앞쪽으로 당겨야하는 작업이 필요한데 , 그렇게 되면 O(n)만큼의 시간복잡도가 발생하게 된다.

 

이런 비효율적인 구조를 보안한 것이 바로 원형 큐다. 

원형큐의 동작이 어떻게 이뤄지는지 그림으로 보자.

 

그림 1 출처 : https://namu.wiki/w/큐(자료구조)

순서는 좌측 상단부터 시작한다.

enqueue를 진행하면서 rear는 계속 한 단계 뒤의 공간을 가리키게 된다. dequeue를 진행하면 선형 큐의 방식처럼 head(front)도 한 단계 뒤로 계속 이동한다. 선형 큐와 똑같아 보이지만 dequeue를 하면 생기게 되는 공간을 재사용 하기 위해 뒤의 데이터들을 끌어오는 동작을 수행하지 않아도 된다는 장점이 있다.

 

구조를 그림으로 본다면 Ring 처럼 보이기 때문에 RingBuffer라고 부르기도 한다.

 

구현

class CircleQueue {
    
    private var front: Int = 0
    private var rear: Int = 0
    private var queue:[Int?] = [nil,nil,nil,nil,nil,nil]
    
    func isEmpty() -> Bool {
        return front == rear
    }
    
    func isFull() -> Bool {
        return ((rear + 1) % queue.count) == front
    }
    
    func enqueue(_ data: Int) {
        if isFull() {
            print("is Full! \(data)")
        } else {
            rear = (rear + 1) % queue.count
            print("eq :  \(data)")
            queue[rear] = data
        }
    }
    
    func dequeue() -> Int? {
        if isEmpty() {
            print("is Empty!")
            return nil
        } else {
            front = (front + 1) % queue.count
            if let data = queue[front] {
                print("dq :\(data)")
                queue[front] = nil
                return data
            } else {
                return nil
            }
        }
    }
    
    func printDatas() {
        print("printDatas -------------")
        for (idx, data) in queue.enumerated() {
            print("idx: \(idx) data: \(data)")
        }
    }
}


let cq = CircleQueue()
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)
cq.enqueue(6)
cq.printDatas()

cq.dequeue()

cq.printDatas()

cq.enqueue(3)
cq.enqueue(4)
cq.enqueue(5)

cq.printDatas()

cq.dequeue()
cq.dequeue()

cq.printDatas()

cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
cq.enqueue(4)
cq.printDatas()