queue는 새로운 아이템을 뒤에 추가할 수 있고, 앞에 아이템을 제거가 가능한 리스트이다. 그래서 처음 넣은(enqueue) 아이템을 처음 제거(dequeue)할 수 있다. FIFO(First in - First Out)형태이다!
우리는 왜 queue를 써야할까? 많은 알고리즘에서 아이템을 여럿 추가하고 나중에 리스트내에서 제거하고 싶을 때가 있다. 또한 추가/삭제의 순서가 중요한 경우도 많다.
queue는 FIFO형태이며, 처음에 넣은 원소가 가장 먼저 추출되게 되는 형식이다. stack(Last in - first out)과 유사하다!
숫자를 enqueue하는 사례를 보자.
queue.enqueue(10)현재 queue는 [ 10 ] 이다. 다음 숫자를 queue에 더해보자.
queue.enqueue(3)현재 queue는 [ 10, 3 ] 이다. 하나 더 더해보자.
queue.enqueue(57)현재 queue는 [ 10, 3, 57 ] 이다. 이제 queue의 가장 앞에 있는 첫 요소를 제거하기 위해 dequeue해보자.
queue.dequeue()마찬가지로 전달인자는 없다.
위 코드를 실행하면 [ 10 ]이 반환된다. 왜냐하면 처음 추가된 숫자가 10이기 때문이다. 현재 queue는 [ 3, 57 ]로 바뀌게 된다. 모든 요소가 1개의 공간만큼 이동한 것이 된다.
계속 dequeue 하게 되면, 3, 57이 반환될 것이다. 마찬가지로 queue가 빈 값이 되면 nil 혹은 오류 메시지를 출력한다.
queue가 정말 필요한 상황이 아니면 stack이 더 간단하고 빠르기에 추천한다! queue는 항상 최고의 선택은 아니라는 점!
Queue의 정의를 봐보자.
public struct Queue<T> {
fileprivate var array = [T]()
public var isEmpty: Bool {
return array.empty
}
public var count: Int {
return array.count
}
public mutating var enqueue(_ element: T) {
array.append(element)
}
public mutatint var dequeue() -> T? {
if isEmpty{
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}앞서 봤던 Stack의 정의와 별 다른 점은 없다. 다만 stack에서는 popLast를 사용하였으나, queue에서는 removeFirst를 사용하는 것을 확인해볼 수 있다.
Enqueuing은 배열의 크기에 관계없이, 항상 동일한 시간이 소요되고, 배열의 끝에 더하는 것이기에 O(1)의 연산이다.
왜 배열에 appending하는 것이 O(1) 혹은 시간에 변함없는 연산일지 궁금할 것이다. 왜냐하면 Swift의 배열은 항상 끝 부분에 빈 공간을 가지고 있기 때문이다. 아래 예시를 보자.
var queue = Queue<String>()
queue.enqueue("Seoul")
queue.enqueue("Busan")
queue.enqueue("Daegu")그러면 배열의 경우는 사실 아래와 같이 구성이 된다.
[ "Seoul", "Busan", "Daegu", xxx, xxx, xxx ]"xxx"는 메모리에 잡혀있지만 아직 값이 채워지지 않은 것이다. 해당 배열에 새 값을 추가하게 되면 사용하지 않은 공간에 덮어쓰기를 하게 된다.
[ "Seoul", "Busan", "Daegu", "Incheon", xxx, xxx ]한 공간에서 다른 장소로 메모리를 복사하는 행위이기에, constant-time operation이게 된다.
다만 배열의 끝에는 사용되지 않은 공간의 수가 제한되어 있다. 이에 마지막 "xxx"가 채워진 후, 새 값을 추가하고자 할 경우 배열의 크기를 재정의(크기 조정) 하여 공간을 더 만들어줘야 한다.
배열의 크기를 조정하는 것은 새 메모리를 할당하는 것과 기존 데이터를 새 배열로 복사하는 것들을 포함한다. 이는 O(n) 프로세스로, 상대적으로 느리다. 이는 가끔씩 발생하는 것이기에, 새 값을 추가하는 시간은 여전히 평균적으로 O(1) 만큼 소요된다.
하지만 dequeuing 같은 경우는 이야기가 다르다. 제거의 경우 배열의 시작에서 진행되기 때문이다. 남겨진 배열 요소들이 메모리에서 이동되어야 하기에 항상 O(n) 연산이다.
아래의 예제에서는 첫 성분인 "Seoul"을 dequeuing하고 "Busan"을 "Seoul" 자리로 복사한다. 그러면 "Daegu"가 "Busan"위치로 오게 되고, "Incheon"은 "Daegu"쪽으로 이동하게 되는 것이다.
before [ "Seoul", "Busan", "Daegu", "Incheon", xxx, xxx ]
/ / /
/ / /
/ / /
/ / /
after [ "Busan", "Daegu", "Incheon", xxx, xxx, xxx ]메모리 상에서 모든 요소를 이동하는 것은 항상 O(n) 연산이다. 간단한 사례를 통해 enqueuing은 효율적이나 dequeuing은 그렇게 만족스럽지 못하다.
좀 더 효율적인 queue
dequeuing을 조금 더 효율적으로 만들기 위해서, 이번에는 배열의 앞 쪽에 여유 공간으 만들어 둘 수 있다. 하지만 Swift 배열에서는 지원해주지 않기 때문에 우리가 스스로 만들어서 사용해야 한다.
핵심 아이디어는, 우리가 어떤 item을 dequeue하건, 배열을 앞으로 당기지 않고(느려서), 기존 item의 위치를 공백으로 만들어 준다(빠름)는 것이다. 만약에 위 처럼 "Seoul"을 제거했다면 아래와 같이 배열이 변경되었을 것이다.
[ xxx, "Busan", "Daegu", "Incheon", xxx, xxx ]여기서 Busan을 제거한다면?
[ xxx, xxx, "Daegu", "Incheon", xxx, xxx ]위 처럼 배열이 바뀌게 된다.
그리고 앞의 빈 공간들은 재사용되지 않기 때문에, 주기적으로 남은 요소들을 앞으로 이동시켜 배열을 다듬을 수 있다.
[ "Daegu", "Incheon", xxx, xxx, xxx, xxx ]
이 다듬는 과정은 이동하는 것에 대한 메모리 O(n) 연산을 포함하고 있다. 왜냐하면 이는 가끔만 실행되기에, dequeuing은 평균 O(1)이다.
아래의 코드를 사용하면 위에서 말한 Queue를 사용할 수 있다.
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)
let 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]
}
}
}
이제 배열은 그냥 T가 아니라 T? 타입의 객체로 저장된다. 왜냐하면 배열 원소에 대해 빈 공간을 표시해야 하기 때문이다. head 변수는 가장 앞 객체에 대한 인덱스이다.
많이 변경된 부분이 dequeue()이다. 우리가 아이템을 dequeue하게 되면, 배열에서 제거하기 위해 먼저 array[head]를 nil로 바꿔준다. 그리고 나서 그 다음 아이템을 첫 번째로 인식하기 위해 head를 1씩 증가시켜준다.
아래 그림으로 이해해보자.
원래 인덱스를 나타내는 head가 가장 앞에 있었으나,
[ "Seoul", "Busan", "Daegu", "Incheon", xxx, xxx ]
headSeoul이 제거되면서 head += 1 처리가 된다.
[ xxx, "Busan", "Daegu", "Incheon", xxx, xxx ]
head코로나 시국에 맞게,... 돌아다니면서 체온 체크를 해주는 사람이 있다고 보면 된다. Seoul에서 체온 체크를 모두 마치면, 주체인 head가 다음 원소로 이동하게 되는 것이다.
만약 배열의 앞부분에 생기는 빈 공간을 제거하지 않는다면 enqueuing과 dequeuing을 하는 것 처럼 배열은 계속 커지게 된다. 주기적으로 배열을 다듬기 위해 아래의 코드를 따르는 것이다.
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}위 코드는 전체 배열 크기의 비율로 시작 부분에서 빈 공간의 비율을 계산한다. 만약 배열의 25%이상이 사용되지 않고 있다면, 공간을 제거하게 되는 것이다. 하지만, 크기를 조정하기에 배열이 너무 작을 때가 있어 이를 고려하여, 배열을 다듬기 전에 최소 50개의 원소가 있어야 한다.
이를 Swift Playground에서 한 번 테스트해보자.
var q = Queue<String>()
q.array
q.enqueue("Seoul")
q.enqueue("Busan")
q.enqueue("Daegu")
q.array // ["Seoul", "Busan", "Daegu"]
q.dequeue()
q.array // [nil, "Busan", "Daegu"]
q.dequeue()
q.array // [nil, nil, "Daegu"]
q.enqueue("Incheon")
q.array // [nil, nil, "Daegu", "Incheon"]배열을 다듬도록 하려면
if array.count > 50 && percentage > 0.25 {
부분을 아래의 코드로 바꿔줘야 한다.
if head > 2 {
그리고 다른 객체를 dequeue하면 배열은 다음과 같이 변할 것이다.
q.dequeue()
q.array // ["Incheon"]
q.count // 1앞 부분의 nil 객체가 사라진 것을 볼 수 있고, 더 이상 배열 내에 낭비되는 공간이 존재하지 않는다. 새로운 버전의 Queue는 오리지날 버전 보다 복잡하지 않고, dequeue의 경우는 그대로 O(1) 연산이다.
-------
이외에도 queue를 만드는 여러 방법들이 있다. 대안으로는 linked list, circular buffer 또는 heap을 사용한다.
Queue의 변형으로는 deque(양끝에 enqueue,dequeue할 수 있는 queue)와 priority queue(가장 중요한 item이 항상 앞에 오도록 분류된 queue)가 있다.
끄읕.