[선형 자료구조] 큐(Queue)

큐(Queue)란?

FIFO(First In First Out)으로 가장 먼저 삽입된 요소가 가장 먼저 제거되는 구조를 가진다.

큐의 주요 연산으로는 Enqueue와 Dequeue가 있다.

 

Enqueue - O(1)

큐의 뒤쪽에 새로운 요소를 추가하는 연산

 

Dequeu - O(1)

큐의 앞쪽에서 요소를 제거하고 반환하는 연산

 

사용 사례

iOS GCD는 작업 수행을 위해 큐를 제공한다.

UI 업데이트의 경우 메인 스레드에서 이루어져야 하기 때문에, GCD의 메인 큐를 사용하여 먼저 들어온 작업부터 처리하게 된다.

 

종류

기본 큐 (Simple Queue)

선입선출(FIFO, First In First Out) 방식으로 요소를 처리한다.

원형 큐 (Circular Queue)

배열의 끝과 시작이 연결된 형태로, 큐의 뒤쪽에서 요소를 추가하고 앞쪽에서 요소를 제거하는 순환 구조를 가진다.
배열을 사용하여 메모리 효율을 높이고, 큐의 공간을 최적화한다.

우선순위 큐 (Priority Queue)

각 요소가 우선순위를 가지어 우선순위에 따라 큐에서의 순서가 결정된다.
우선순위가 높은 요소가 먼저 처리되며, 일반적으로 힙(Heap)을 기반으로 구현된다.

 

구현

두 개의 스택을 이용한 구현 방법

class Queue<T> {
    private var inbox: [T]
    private var outbox: [T] = []
    
    var isEmpty: Bool {
        return inbox.isEmpty && outbox.isEmpty
    }
    
    var count: Int {
        return inbox.count + outbox.count
    }
    
    init(_ input: [T]) {
        inbox = input
    }
    
    func enqueue(_ input: T) {
        inbox.append(input)
    }
    
    func dequeue() -> T? {
        if outbox.isEmpty {
            outbox = inbox.reversed()
            inbox.removeAll()
        }
        return outbox.popLast()
    }
}

 

reversed의 시간 복잡도

 

 

링크드 리스트를 이용한 구현 방법

class Node<T> {
    var value: T
    var next: Node?

    init(value: T) {
        self.value = value
    }
}

class Queue<T> {
    private var head: Node<T>?
    private var tail: Node<T>?

    // 큐가 비어있는지 확인
    var isEmpty: Bool {
        return head == nil
    }

    // 큐에 들어있는 요소의 수
    var count: Int = 0

    // 큐의 맨 앞에 있는 요소를 확인
    func peek() -> T? {
        return head?.value
    }

    // 큐에 요소를 추가 (맨 뒤에 추가)
    func enqueue(_ value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
        count += 1
    }

    // 큐에서 요소를 제거 (맨 앞에서 제거)
    func dequeue() -> T? {
        guard let headNode = head else {
            return nil
        }
        head = headNode.next
        if head == nil {
            tail = nil
        }
        count -= 1
        return headNode.value
    }
}