[자료구조] 큐(Queue)란 (Swift)

큐의 개념

큐는 기존 스택과는 다르게 먼저 들어간 자료가 먼저 나오는 구조입니다(First in First Out). 

한쪽이 뚫려 있는 구조로 한쪽으로는 데이터의 삽입(enQueue) 다른 한쪽은 데이터 추출(deQueue)이 진행됩니다.

큐는 front(머리) rear(꼬리) 가 존재하는데 데이터 삽입시 rear 다음에 위치(rear+1) 데이터 추출시에 먼저 들어온 데이터가 나가야 하기때문에 머리 위치에서 나갑니다.

 

 

큐의 구현(Array)

struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
}

var testQueue = Queue<Int>()
testQueue.enqueue(1) // 1
testQueue.enqueue(2) // 1 , 2
testQueue.dequeue() // 1반환 -> 1을 먼저 제거함 1이 먼저 들어왔기 때문에(First In First Out)

 

구현

Array를 통해 append() 와 removeFirst() 구현이 가능합니다. 하지만 이방법의 단점은 removeFirst()를 하면 배열의 재배치가 일어나 시간복잡도가 O(N)이 발생합니다.

 

 

큐의 구현(dequeue 개선)

struct Queue<T> {
    private var queue: [T?] = []
    private var front: Int = 0
    
    public var frontValue: Int {
        return self.front
    }
    
    public var size: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        guard front <= size, let element = queue[front] else { return nil }
        queue[front] = nil
        front += 1
        return element
    }
}

 

 

출처 https://babbab2.tistory.com/84

구현

기존의 removeFirst() 대신 nil로 초기화하여 front(포인터)를 이용하여 index만 증가 시킵니다.

그럼 데이터는 삭제하고 공간은 그대로 이기때문에 앞으로 당기는 작업이 없어집니다 -> 시간복잡도 O(1)

 

 

 

 

왜 사용해야할까 or 나만의 고민

가장 먼저 입력된 데이터를 처리하고 싶을때 사용하면 매우좋음

순서를 중요시 여기는 시스템에 사용하면 좋음

 

 

 

 

 

참조)

https://babbab2.tistory.com/84