Queue- 자료구조

메모리 구조 공부하면서 Stack 자료구조 글을 포스팅 했었는데… 메모리 구조, ARC는 꾸준히 하고 있는가.. 쉿!

오늘은 거의 Stack과 쌍을 이루는 Queue에 대해 소개하고 swift로 구현해보도록 하겠습니다!

Queue 란?

큐 FIFO ( First In First Out ) 형식의 자료구조입니다. LIFO 인 스택과 차이를 보입니다.

가장 먼저 추가 된 것을 가장 먼저 배출하는 것입니다. 큐라는 단어가 생소하지만, 이미 일상 생활에서 굉장히 익숙합니다. 영화관, 은행에서 번호표를 뽑고 기달리는 것과 같이요!

큐의 대표적인 연산자는 다음과 같습니다

∙ enqueue : 큐에 데이터 추가

∙ dequeue : 가장 먼저 추가 된 데이터 배출

∙ isEmpty : 큐 비어있는 여부를 반환

그럼 swift 로 Queue 구현해봅시다!

Queue 구현

swift 기본 제공해주는 배열을 통해 Queue을 구현한 예시입니다.

struct Queue<T> {
    private var queue: [T] = []
    
    var count: Int {
        return queue.count
    }
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    mutating func enqueue(_ item: T) {
        queue.append(item)
        printInfo()
    }
    
    mutating func dequeue() -> T? {
        guard let dequeueItem = queue.first else {
            printInfo()
            return nil
        }
        queue.removeFirst()
        printInfo()
        return dequeueItem
    }
    
    private func printInfo() {
        print("count : \(count) ,  queue : \(queue)")
    }
}

아래와 같이 동작합니다.

동작에는 이상이 없어 보이나! 배열의 특성상 해당 방식은 비효율적입니다.

item 추가인 enqueue는 array의 맨 뒤 추가로 문제가 없으나, dequeue 시 문제가 발생합니다.

[1, 2, 3, 4, 5, 6] 에서 dequeue를 하게 되면, 단지 처음 값을 가져와 queue.removeFirst() 통해 지우고, 반환했지만, 내부적으로는 맨 앞을 삭제하고 한 칸씩 땡기는 작업이 발생합니다.

이는 dequeue 호출 될 때마다 발생합니다.

var waitingNumber = Queue<Int>()
waitingNumber.enqueue(1)  // count : 1 ,  queue : [1]
waitingNumber.enqueue(2)  // count : 2 ,  queue : [1, 2]
waitingNumber.enqueue(3)  // count : 3 ,  queue : [1, 2, 3]
waitingNumber.enqueue(4)  // count : 4 ,  queue : [1, 2, 3, 4]
waitingNumber.enqueue(5)  // count : 5 ,  queue : [1, 2, 3, 4, 5]
waitingNumber.enqueue(6)  // count : 6 ,  queue : [1, 2, 3, 4, 5, 6]
waitingNumber.dequeue()   // count : 5 ,  queue : [2, 3, 4, 5, 6]
waitingNumber.dequeue()   // count : 4 ,  queue : [3, 4, 5, 6]
waitingNumber.dequeue()   // count : 3 ,  queue : [4, 5, 6]
waitingNumber.enqueue(7)  // count : 4 ,  queue : [4, 5, 6, 7]
waitingNumber.enqueue(8)  // count : 5 ,  queue : [4, 5, 6, 7, 8]
waitingNumber.dequeue()   // count : 4 ,  queue : [5, 6, 7, 8]
waitingNumber.dequeue()   // count : 3 ,  queue : [6, 7, 8]
waitingNumber.dequeue()   // count : 2 ,  queue : [7, 8]
waitingNumber.dequeue()   // count : 1 ,  queue : [8]
waitingNumber.dequeue()   // count : 0 ,  queue : []
waitingNumber.dequeue()   // count : 0 ,  queue : []
waitingNumber.enqueue(9)  // count : 1 ,  queue : [9]
waitingNumber.enqueue(10) // count : 2 ,  queue : [9, 10]

위의 비효율성은 head 라는 변수를 통해 해결 할 수 있습니다.

head는 배열의 가장 최근 들어 온 item 즉 dequeue가 될 item의 index를 가르킵니다.

dequeu 시 head의 item 값을 가져오고, head 자리를 nil로 빈 값을 채운 뒤, head는 한 칸 뒤로 이동, 값 반환 진행합니다.

대신, 기준을 정해 queue 빈 값들을 정리해줘야 합니다. 아래 같은 경우 배열에 큐 값이 차지하는 비율이 60이하가 되는 경우 빈 값을 정리해줍니다.

struct Queue<T> {
    private var queue: [T?] = []
    private var head: Int?

    var count: Int {
        guard let head = head else {
            return 0
        }
        return queue.count - head
    }

    var isEmpty: Bool {
        return queue.isEmpty
    }

    mutating func enqueue(_ item: T) {
        if(head == nil) {
            head = 0
        }
        queue.append(item)

        if(count * 100 / queue.count < 60) {
            resetHead()
        }
        printInfo()
    }

    mutating func dequeue() -> T? {
        var dequeueItem: T? = nil
        if let head = head {
            dequeueItem = queue[head]
            queue[head] = nil
            self.head = head + 1
            if(count == 0) {
                self.head = nil
                self.queue = []
            }
        }
        printInfo()
        return dequeueItem
    }

    mutating func resetHead() {
        queue.removeFirst(head!)
        head = 0
    }

    private func printInfo() {
        print(" head : \(head) , count : \(count) ,  queue : \(queue)")
    }
}

아래와 같이 동작합니다

var waitingNumber = Queue<Int>()
waitingNumber.enqueue(1)  // head : Optional(0) , count : 1 ,  queue : [Optional(1)]
waitingNumber.enqueue(2)  // head : Optional(0) , count : 2 ,  queue : [Optional(1), Optional(2)]
waitingNumber.enqueue(3)  // head : Optional(0) , count : 3 ,  queue : [Optional(1), Optional(2), Optional(3)]
waitingNumber.enqueue(4)  // head : Optional(0) , count : 4 ,  queue : [Optional(1), Optional(2), Optional(3), Optional(4)]
waitingNumber.enqueue(5)  // head : Optional(0) , count : 5 ,  queue : [Optional(1), Optional(2), Optional(3), Optional(4), Optional(5)]
waitingNumber.enqueue(6)  // head : Optional(0) , count : 6 ,  queue : [Optional(1), Optional(2), Optional(3), Optional(4), Optional(5), Optional(6)]
waitingNumber.dequeue()   // head : Optional(1) , count : 5 ,  queue : [nil, Optional(2), Optional(3), Optional(4), Optional(5), Optional(6)]
waitingNumber.dequeue()   // head : Optional(2) , count : 4 ,  queue : [nil, nil, Optional(3), Optional(4), Optional(5), Optional(6)]
waitingNumber.dequeue()   // head : Optional(3) , count : 3 ,  queue : [nil, nil, nil, Optional(4), Optional(5), Optional(6)]
waitingNumber.enqueue(7)  // head : Optional(0) , count : 4 ,  queue : [Optional(4), Optional(5), Optional(6), Optional(7)]
waitingNumber.enqueue(8)  // head : Optional(0) , count : 5 ,  queue : [Optional(4), Optional(5), Optional(6), Optional(7), Optional(8)]
waitingNumber.dequeue()   // head : Optional(1) , count : 4 ,  queue : [nil, Optional(5), Optional(6), Optional(7), Optional(8)]
waitingNumber.dequeue()   // head : Optional(2) , count : 3 ,  queue : [nil, nil, Optional(6), Optional(7), Optional(8)]
waitingNumber.dequeue()   // head : Optional(3) , count : 2 ,  queue : [nil, nil, nil, Optional(7), Optional(8)]
waitingNumber.dequeue()   // head : Optional(4) , count : 1 ,  queue : [nil, nil, nil, nil, Optional(8)]
waitingNumber.dequeue()   // head : nil , count : 0 ,  queue : []
waitingNumber.dequeue()   // head : nil , count : 0 ,  queue : []
waitingNumber.enqueue(9)  // head : Optional(0) , count : 1 ,  queue : [Optional(9)]
waitingNumber.enqueue(10) // head : Optional(0) , count : 2 ,  queue : [Optional(9), Optional(10)]

정리

∙ 큐를 배열로 구현하는 경우 배열의 특성상 dequeue 시 유의해야한다.

---

참고자료

https://babbab2.tistory.com/84

https://woongsios.tistory.com/222