[Algorithm] 큐 구현하기 (Swift)
Swift에서 스택과 큐
Swift로 프로그래밍을 하다 보면 자료구조를 구현해줘야 하는 것들이 있다. 그중 하나가 큐이다. 스택의 경우 removeLast() 와 append(_:) 의 경우 complexity 가 O(1) 이기 때문에 배열에서 위와 같은 함수를 사용하여 그대로 구현할 수 있다.
따라서 스택은 구현이랄 것도 없다. 원래 있는 메서드를 개념에 맞게 사용하면 그것이 스택 자료구조이다.
var stack: [Int] = [1, 2, 3, 4, 5]
stack.append(6)
print(stack.removeLast()) // 6
print(stack) // [1, 2, 3, 4, 5]
하지만 큐의 경우 FIFO 이기 때문에 removeFirst() 메소드를 사용해야 하는데 문제는 complexity 가 O(n) 이라는 것이다. 당연하게도 배열의 첫 요소를 없애고 나머지 요소를 한 칸씩 앞으로 당기기 때문에 O(n) 이 나오는 것은 당연하다.
큐는 아래와 같이 구현하면 큐라고 할 순 있겠지만, 문제는 removeFirst() 할때마다 O(n) 의 시간이 걸린다는 것이다. 단순히 이렇게 구현하게 된다면 큐가 커질수록 시간은 오래 걸릴 것이다. (알고리즘 문제의 경우 무조건 시간초과가 난다)
var queue: [Int] = [1, 2, 3, 4, 5]
queue.append(6)
print(queue.removeFirst()) // 1
print(queue) // [2, 3, 4, 5, 6]
큐 구현하기
초 간단 버전
바로 removeFirst() 를 쓰지 않는 것...! 그냥 head 라는 인덱스를 사용하여 접근하는 것이다. 요소를 지우지 않고 계속 쌓는 느낌이다. 하지만 head는 큐에서 맨 앞요소를 사용할 때마다 1을 더해준다.
var queue: [Int] = [1, 2, 3, 4, 5]
var head = 0
queue.append(6)
print(queue[head]) // 1
head += 1
print(queue) // [1, 2, 3, 4, 5, 6]
굳이 복잡하게? 구현해보자면... enqueue, dequeue 로 큐를 편하게 쓰게 바꿀 수 있다.
import Foundation
struct Queue<T> {
private var array: [T] = []
private var head: Int = 0
var isEmpty: Bool {
return head >= array.count
}
var count: Int {
return array.count - head
}
init() { }
init(_ element: [T]) {
array = element
}
mutating func enqueue(_ element: T) {
array.append(element)
}
mutating func dequeue() -> T? {
guard head < array.count else { return nil }
let element = array[head]
head += 1
return element
}
}
// 사용 예시
var queue = Queue([1, 2, 3, 4])
queue.enqueue(5)
print(queue) // Queue<Int>(array: [1, 2, 3, 4, 5], head: 0)
print(queue.count) // 5
print(queue.dequeue()) // Optional(1)
print(queue.count) // 4
print(queue) // Queue<Int>(array: [1, 2, 3, 4, 5], head: 1)문제점
문제점은 딱 하나다 계속 배열이 쌓인다는 것, 결국 dequeue를 해도 메모리에서 해제가 되지 않기 때문에 계속 메모리를 차지하고 있는다는 것이다.
스택 두개와 .reversed() 로 큐 구현하기
이 아이디어는 Swift에서 reversed() 메소드의 complexity 가 O(1) 인 것을 활용하는 것이다.
inbox, outbox 를 사용한다. dequeue를 할 때, outbox 의 마지막 요소를 꺼내고, 만약 outbox가 없다면 inbox를 reversed() 로 뒤집어 준 뒤 outbox 에 넣어주고 다시 outbox 의 마지막 요소를 꺼내주면 된다. 이렇게 되면 메모리의 사용이 줄어들게 된다.
struct Queue<T> {
private var inbox: [T] = []
private var outbox: [T] = []
var isEmpty: Bool {
return inbox.isEmpty && outbox.isEmpty
}
var count: Int {
return inbox.count + outbox.count
}
init() { }
init(_ array: [T]) {
self.inbox = array
}
mutating func enqueue(_ n: T) {
inbox.append(n)
}
mutating func dequeue() -> T? {
if outbox.isEmpty {
outbox = inbox.reversed()
inbox = []
}
return outbox.popLast()
}
}
var queue = Queue([1, 2, 3, 4])
queue.enqueue(5)
print(queue) // Queue<Int>(inbox: [1, 2, 3, 4, 5], outbox: [])
print(queue.count) // 5
print(queue.dequeue()) // Optional(1)
print(queue.count) // 4
print(queue) // Queue<Int>(inbox: [], outbox: [5, 4, 3, 2])
.reversed() 에 대해서
그럼 여기서 의문이 생긴다. 어떻게 reversed() 의 시간복잡도는 O(1) 이 될 수 있을까? 다시 공식문서를 살펴보게 된다면 reversed() 가 반환하는 것은 새로운 배열이 아닌 ReversedCollection 임을 알 수 있다. 새로운 배열을 반환하는 것이 아닌 원본 배열의 요소를 직접 참조하는 방식으로 이루어 진다. 원본 컬렉션을 복사하지 않고 요소를 역순으로 순회할 수 있도록 하는 것이기 때문에 시간 복잡도가 O(1) 인 것이다.
의문점
원본배열을 바꾸어 봤지만 바뀐 6이 아니라 그대로 1이 나오게 되는데 생성 시점의 배열에 역순으로 접근하는 것 같다. 살짝 이부분이 이해가 가지 않는데, 좀더 메모리나 Swift에 대한 공부가 필요 할 것 같다.
var array = [1, 2, 3, 4, 5]
let reversedArray = array.reversed() // reversedArray는 원본 배열의 역순 뷰를 반환
array[0] = 6 // 원본 배열 변경
print(array) // [6, 2, 3, 4, 5]
print(Array(reversedArray)) // [5, 4, 3, 2, 1] reversedArray는 원본 배열의 이전 상태를 유지