[자료구조] 큐 ( Queue )

개요

 

맛집 대기줄 같은 자료구조 입니다.

큐의 가장 큰 특징은 선입선출( FIFO, First-In-First-Out ) 이며, 먼저 들어온 데이터가 먼저 나간다는 의미입니다.

구현하는 방식에 따라 오버헤드가 발생할 수도 있고, 발행하지 않을 수도 있습니다.

 

데이터는 마지막에 추가되므로,

데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.

 

 

먼저 들어온 데이터가 제거되므로,

 

Head 자체를 삭제하는 경우 배열을 하나씩 당겨줘야 하기 때문에 데이터의 제거는 O(n) 의 시간복잡도를,

Head 를 가리키는 인덱스를 변경시킬 경우 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다. 

 

Queue 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.

큐_001

head	Queue 에서 제일 먼저 제거할 테이터입니다.
enqueue	Queue 에 데이터를 추가합니다. Queue 의 맨 뒷 부분에 데이터가 추가됩니다.
dequeue	Queue 에서 데이터를 제거합니다. Queue 에서 head 부분의 데이터가 제거됩니다.

                     

---

아래는 위에서 언급한 Head 자체를 삭제하는 경우와 Head 를 가리키는 인덱스를 변경시킬 경우의 동작입니다.

head 를 제거해서 배열을 이동시켜 오버헤드가 발생하는 Queue 는 아래 그림과 같이 동작합니다.

큐_002

head 인덱스를 변화시켜 배열을 움직일 필요가 없는 Queue 는 아래 그림과 같이 동작합니다.

큐_003

---

구현

 

Queue 는 Swift 를 사용하여 아래와 같이 구현하며, 아래와 같이 사용할 수 있습니다.

 

1. Head 자체를 제거하는 Queue 의 구현 - 오버헤드 발생

// MARK: Queue 구현
// Head 자체를 삭제함 - 오버헤드 발생
struct Queue<T> {
    private var queue: [T] = []
    
    public var count: Int {
        // Queue 의 길이를 반환합니다.
        return queue.count
    }
    
    public var isEmpty: Bool {
        // Queue 가 비어있는지 true/ false 를 반환합니다.
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        // Queue 에 데이터를 추가합니다.
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        // Queue 에서 데이터를 제거합니다.
        return isEmpty ? nil : queue.removeFirst()
    }
}

var mQueue = Queue<Int>()

mQueue.enqueue(10) 	// 데이터 추가
mQueue.isEmpty		// 비어있는지 확인
mQueue.count		// 길이 확인
mQueue.dequeue()	// 데이터 제거

 

2. Head 인덱스를 변경하는 Queue 의 구현 - 오버헤드 발생하지 않음, remove 작업 필요

// MARK: Queue 구현
// Head 인덱스를 변경함 - 오버헤드 발생하지 않음
struct Queue<T> {
    private var queue: [T?] = []
    private var head: Int = 0
    
    public var count: Int {
        // Queue 의 길이를 반환합니다.
        return queue.count
    }
    
    public var isEmpty: Bool {
        // Queue 가 비어있는지 true/ false 를 반환합니다.
        return queue.isEmpty
    }
    
    public mutating func enqueue(_ element: T) {
        // Queue 에 데이터를 추가합니다.
        queue.append(element)
    }
    
    public mutating func dequeue() -> T? {
        // Queue 에서 제거할 데이터( head 가 가리키는 데이터 )를 nil 로 바꾸고 head 의 인덱스를 변경한다.
        // head 가 Queue의 중간까지 변경되었다면 앞의 nil 을 지운다,
        guard head <= queue.count && !isEmpty, let element = queue[head] else { return nil }
        queue[head] = nil
        head += 1
        
        if head > count / 2 {
            queue.removeFirst(head)
            head = 0
        }
        return element
    }
}

var mQueue = Queue<Int>()

mQueue.enqueue(10) 	// 데이터 추가
mQueue.isEmpty		// 비어있는지 확인
mQueue.count		// 길이 확인
mQueue.dequeue()	// 데이터 제거

 

Swift 자체에는 지원하지 않으니 Queue 를 사용하려면 직접 구현해서 쓰셔야 합니다 ^^.

 

P.S

추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.