개요
맛집 대기줄 같은 자료구조 입니다.
큐의 가장 큰 특징은 선입선출( FIFO, First-In-First-Out ) 이며, 먼저 들어온 데이터가 먼저 나간다는 의미입니다.
구현하는 방식에 따라 오버헤드가 발생할 수도 있고, 발행하지 않을 수도 있습니다.
데이터는 마지막에 추가되므로,
데이터의 추가는 O(1) 의 시간복잡도를 갖습니다.
먼저 들어온 데이터가 제거되므로,
Head 자체를 삭제하는 경우 배열을 하나씩 당겨줘야 하기 때문에 데이터의 제거는 O(n) 의 시간복잡도를,
Head 를 가리키는 인덱스를 변경시킬 경우 데이터의 제거는 O(1) 의 시간복잡도를 갖습니다.
Queue 를 이해하기 쉽게 그림으로 나타내면 아래와 같습니다.
head | Queue 에서 제일 먼저 제거할 테이터입니다. |
enqueue | Queue 에 데이터를 추가합니다. Queue 의 맨 뒷 부분에 데이터가 추가됩니다. |
dequeue | Queue 에서 데이터를 제거합니다. Queue 에서 head 부분의 데이터가 제거됩니다. |
아래는 위에서 언급한 Head 자체를 삭제하는 경우와 Head 를 가리키는 인덱스를 변경시킬 경우의 동작입니다.
head 를 제거해서 배열을 이동시켜 오버헤드가 발생하는 Queue 는 아래 그림과 같이 동작합니다.
head 인덱스를 변화시켜 배열을 움직일 필요가 없는 Queue 는 아래 그림과 같이 동작합니다.
구현
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
추가적으로 생각나거나 찾은 내용은 날짜를 덧붙여 업데이트 하겠습니다.
'CS' 카테고리의 다른 글
[자료구조] 단순 연결 리스트( Singly Linked List ) (0) | 2023.02.21 |
---|---|
[자료구조] 순차 리스트 ( Sequential List ) (0) | 2023.02.19 |
[자료구조] 덱 ( Deque ) (0) | 2023.02.17 |
[자료구조] 자료구조 로드맵 (0) | 2023.02.17 |
[자료구조] 스택 ( Stack ) (0) | 2023.02.13 |