Queue 란?
- Queue 자료구조를 그림을 통해 이해해 보자
- 각 아이템들이 들어간 순서대로 나오는 구조를 이야기한다
- First In First Out ( FIFO )
Swift 에서 Queue 구현
- 구조체로 Queue를 선언한 코드를 먼저 살펴보자
// Queue 선언
struct Queue<T> {
private var elements: [T] = []
public var count: Int {
return elements.count
}
public var isEmpty: Bool {
return elements.isEmpty
}
public mutating func enqueue(_ element: T) {
return elements.append(element)
}
public mutating func dequeue() -> T? {
return isEmpty ? nil : elements.removeFirst()
}
}
// Queue 사용
var intQueue = Queue<Int>()
print(intQueue)
// Queue<Int>(elements: [])
intQueue.enqueue(3)
print(intQueue)
// Queue<Int>(elements: [3])
print(intQueue.count)
print(intQueue.isEmpty)
// 1
// false
intQueue.dequeue()
print(intQueue.isEmpty)
// true
- 구조체를 이용해 [ count , isEmpty, enqueue, dequeue ] 를 간단히 구현 할수 있었다
문제점
구현 한거 아니야? 뭐가 문제야!!!
응.. 문제야..
- 위에서 선언한 방식으로 Queue를 사용하는데 ‘기능상' 문제는 없다, 하지만 메모리 관리 측면에서 너무 비효율적이다
- 비효율 적인 이유
- dequeue 를 수행할 때 removeFirst() 내장 함수를 사용하게 되는데 이것이 문제가 된다.
- 첫 요소를 제거한 후 모든 요소들의 인덱스를 한칸씩 앞으로 당겨야한다.
⇒ 위 그림에서는 한번만 수행되지만 만약 dequeue가 여러번 수행된다면..? 엄청난 메모리 낭비를 하게 될것이다
요소 하나하나 제거할 때마다 만약 queue내의 item이 100개, 1000개 라면,, 요소 하나를 제거하기 위해 수없이 많이 인덱스를 한칸씩 당겨주어야 한다
해결 방법
- head 라는 놈을 추가해 주고, dequeue될때마다 head 인덱스를 nil 로 바꿔준다
- 그리고 일정 수준 이상으로 nil 이 채워지면, 0인덱스부터 head 까지의 요소를 한번에 제거하고 head 를 0으로 초기화 해준다
- 이런 방법을 통해서 dequeue를 매번 하지않고, 쌓아 두었다가 일정 수준 이상에 도달하면 한번에 제거하기 때문에 메모리 측면에서 기존 방식보다 더 효율적이다
향상된 Queue 구현
struct Queue<T> {
// nil 이 포함되기 때문에 [T?] 의 Optional 타입으로 선언
private var elements: [T?] = []
private var head = 0
// nil 인경우 count를 안하기 위해 for case 문을 사용
public var count: Int {
var elementCount = 0
for case .some in elements { elementCount += 1 }
return elementCount
}
public var isEmpty: Bool {
return elements.isEmpty
}
public mutating func enqueue(_ element: T) {
return elements.append(element)
}
public mutating func dequeue() -> T? {
// head 가 큐의 아이템 갯수보다 크거나, head가 가르키는 곳이 nil 일경우 nil 반환
guard head < elements.count, let element = elements[head] else { return nil }
elements[head] = nil
head += 1
// Queue아이템의 1/3 보다 클경우마다 인덱스 0부터 head 까지 요소를 제거하고 head 0으로 초기화
if head > (elements.count / 3) {
elements.removeFirst(head)
head = 0
}
return element
}
}- 기존 방법과 다르게 nil 이 포함되기 때문에 옵셔널 타입의 배열로 선언해야 한다 [T?]
- 아이템의 1/3 보다 head가 클 경우마다 nil 요소들을 지우게 설정했지만, 적절하게 조절해서 사용하면 될거같다
- Count 의 경우, nil 인경우 count를 안하기 위해 for case 문을 사용 Nil 이 아닌 경우만 세서 반환한다.
var iQ = Queue<Int>()
iQ.enqueue(3)
iQ.enqueue(4)
iQ.enqueue(5)
iQ.count
// 3
iQ.dequeue()
// 3
iQ.count
// 2
iQ
// [nil, 4, 5] , head = 1
iQ.dequeue()
// 4
iQ
// [5], head = 0
iQ.count
// 1
iQ.dequeue()
// 5
iQ
// [], head = 0
iQ.dequeue()
// nil
iQ.count
// 0
iQ.dequeue()
// nil
참고 링크
