큐(Queue) 기본 개념
큐는 새로운 항목을 리스트의 뒤쪽에 추가하고, 기존 항목을 리스트의 앞쪽에서 제거할 수 있는 자료구조입니다. 다시 말해, 가장 먼저 추가한 항목이 가장 먼저 제거됩니다. 흔히 편의점에서 들을 수 있는 선입선출(FIFO, First In First Out) 방식입니다.
이런 큐가 왜 필요할까요? 많은 알고리즘에서 객체를 임시 리스트에 추가했다가 나중에 이를 꺼내는 경우가 있습니다. 이때 추가와 제거의 순서가 중요한 경우 큐를 사용합니다.
큐와 비슷한 자료구조로 스택(Stack)이 있는데, 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작합니다.
큐의 동작 원리
예를 들어, 숫자를 큐에 추가하는 경우를 살펴보겠습니다.
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)queue.dequeue()
10이 가장 먼저 삽입된 숫자였기 때문에 위 코드는 10을 반환합니다. 이후 남은 항목들이 한 칸씩 앞 당겨져서 이제 큐는 [3 , 57 ]이 됩니다. 다음으로 deque는 3을, 그다음은 57을 반환합니다. 큐가 비어 있을 경우, nil을 반환하거나 구현 방식에 따라 오류 메시지를 출력할 수도 있습니다.
만약 추가 및 제거 순서가 중요하지 않다면, 큐 대신 스택을 사용할 수 있습니다. 스택은 더 간단하고 빠르게 동작합니다.
Swift로 구현한 간단한 큐
아래는 Swift에서 큐를 간단히 구현한 예제입니다.
public struct Queue<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
위 구현은 간단하고 잘 작동하지만, 최적화는 되어 있지 않습니다.
- enqueue: 배열의 끝에 항목을 추가하는 작업은 항상 O(1), 즉 일정한 시간이 걸립니다.
- dequeue: 배열의 앞에서 항목을 제거하는 작업은 O(n), 즉 배열 크기에 비례하는 시간이 걸립니다. 이는 비효율적이기 때문에 최적화가 필요합니다.
enqueue(항목 추가)은 왜 O(1), 즉 상수 시간 연산이 걸릴까요? 그 이유는 Swift의 배열은 항상 끝부분에 여분의 공간을 보유하고 있기 때문입니다. 코드를 예로 들어보겠습니다.
var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")위 Queue는 실제로는 아래와 같은 모습을 띄게 됩니다.
[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]
여기서 xxx는 아직 값을 채워지지 않고 미리 빼놓은 메모리 공간을 의미합니다. 새로운 항목을 추가하면 다음 빈 공간(즉, xxx 자리)을 채우게 됩니다
[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
따라서, 이 과정은 메모리의 한 위치에서 다른 위치로 데이터를 복사하는 것으로, 상수 시간 작업입니다.
하지만 배열의 끝에 있는 빈 공간은 정해진 개수만 존재합니다. 마지막 xxx가 사용되고 새로운 항목을 추가해야 할 때는, 배열이 더 넓은 메모리 공간을 확보하기 위해 크기를 재조정해야 합니다. 크기를 재조정하는 과정에서는 새로운 메모리를 할당하고 기존 데이터를 모두 새로운 배열로 복사하게 되는데, 이는 O(n) 시간 복잡도를 가지며 상대적으로 느립니다.
다행히 이 과정은 가끔씩만 발생하므로, 배열의 끝에 항목을 추가하는 평균 시간은 여전히 O(1)입니다.
반면, dequeue(항목 제거)의 경우는 다릅니다. dequeue는 배열의 시작 부분에서 항목을 제거하는 연산인데, 이때 배열에 남아 있는 모든 요소들을 메모리 상에서 한 칸씩 앞으로 이동시켜야 하므로 항상 O(n) 연산이 됩니다.
예를 들어, 첫 번째 항목 "Ada"를 dequeue 하면 한 칸씩 당겨서 "Ada" 자리에 "Steve"가, "Steve" 자리에 "Tim"이, 그리고 "Tim" 자리에 "Grace"가 복사됩니다.
before: [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
after: [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]
이처럼 메모리의 요소들을 모두 이동시키는 작업은 배열의 크기가 n이라고 했을 때 항상 O(n) 시간이 소요됩니다. 따라서 저희는 선형적 시간 복잡도가 걸리는 dequeue는 고쳐야 합니다.
효율적인 큐 구현
Dequeue를 효율적으로 바꾸기 위해서 배열의 앞쪽에도 미리 공간을 확보해 놓을 수 있습니다. Swift에서는 이런 방식의 배열(queue)을 지원하지 않기 때문에 직접 구현해줘야 합니다.
쉽게 말하자면, 배열의 앞쪽에서 항목을 하나 뺄 때마다 항목들을 전부 옮기는 게 아니라, 맨 앞의 값이 있는 자리를 비웠다고 표시하는 것입니다. 위 배열 예시에서 "Ada"를 Dequeue 하면 아래와 같이 나옵니다.
[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
코드를 통해 구현해 보겠습니다.
public struct Queue<T> {
fileprivate var array = [T?]()
fileprivate var head = 0
public var isEmpty: Bool {
return count == 0
}
public var count: Int {
return array.count - head
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
guard head < array.count, let element = array[head] else { return nil }
array[head] = nil
head += 1
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
return element
}
public var front: T? {
if isEmpty {
return nil
} else {
return array[head]
}
}
}
다른 부분은 거의 유사하고 dequeue() 부분이 다릅니다. 큐에서 dequeue 할 때 array[head]의 값을 nil로 만들어 값을 뺀 것과 같은 효과를 만들어 냅니다. 이 방법은 Queue의 dequeue를 할 때마다 queue의 앞부분에 nil이라는 값들이 쌓여서 배열이 점점 커지게 됩니다.
이를 방지하기 위해서 배열의 앞부분의 nil 값의 개수를 계산해 약 25%의 배열이 사용되고 있지 않다면 (nil로 채워져 있다면), 이 사용하지 않는 값들을 지워냅니다.
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
