Queue in Swift
- 선형 자료구조
- FIFO (선입선출)
- 구현
- LinkedList
- DoubleStack
Swift에서는 Queue와 LinkedList를 기본 자료구조로 제공하지 않고 있는데요,
array를 사용해 queue를 만들면 enqueue 작업이 O(n)이 걸려서 비효율적입니다.
특히 코딩테스트 문제를 풀다보면 queue가 필요한 상황이 많기 때문에 미리 알아두고 구현해둔다면 좋겠죠?
오늘은 간단하게 Queue 에 대해 알아보고 swift에서는 어떻게 구현할 수 있을지 알아보겠습니다.
LinkedList를 사용한 구현과, stack 두 개를 사용한 doubleStack 구현을 알아볼텐데요,
LinkedList는 제가 구현해서 그런지 doubleStack과 복잡도 차이가 꽤 나더라구요... 😢
코딩테스트 문제에서 사용하신다면, DoubleStack을 사용하시는 걸 추천드립니다 :)
Queue, FIFO
Queue는 선형 자료구조의 일종으로 First In First Out(FIFO) 방식입니다.
먼저 들어간 원소가 먼저 나오는 형태의 FIFO(First In First Out) 방식의 자료구조입니다.
Stack이 나중에 들어온 원소가 먼저 나오는 LIFO 방식의 접시를 쌓는 형태의 모습이라면,
Queue는 가로로 통과하는 원형 통의 모습을 떠올려 볼 수 있겠네요 :)
stack이 함수를 처리하고 다시 호출된 위치로 돌아가는 함수 호출 등의 처리에 사용된다면,
Queue는 실생활에서 은행 대기표를 뽑고 기다리는 경우와 같이 먼저 뽑은 사람을 먼저 처리하는 경우에 사용됩니다.
개념 자체는 어렵지 않으실텐데요, 구현을 살펴보겠습니다.
LinkedList
stack 은 맨 뒤의 원소를 제거하기 때문에 array를 사용해서 구현하면 제거가 O(1)이기 때문에 효율적으로 구현할 수 있는데요,
queue 같은 경우 맨 앞의 원소를 제거해야 하기 때문에 array를 사용해서 구현하면 O(n)의 복잡도가 소요됩니다. 제거하고 뒤의 원소를 재배치 해주는 작업이 필요하기 때문이죠!
따라서 Queue를 구현할 때는 삽입/삭제에 O(1)이 소요되는 LinkedList를 많이 활용하는데요,
Swift에서는 LinkedList를 지원하지 않기 때문에 직접 구현해야 합니다.
LinkedList의 자세한 내용이 궁금하시다면 이전 글을 확인해주세요 :)
구현
node 상태를 print 하기위해 CustomStringConvertible 프로토콜을 구현해줬습니다 :)
// MARK: LinkedList
final class LinkedList<T> {
final class Node<T> {
var value: T
var next: Node?
weak var previous: Node?
init(_ value: T) {
self.value = value
}
}
private(set) var head: Node<T>?
private(set) var tail: Node<T>?
private(set) var count = 0
var first: T? {
return head?.value
}
var last: T? {
return tail?.value
}
var isEmpty: Bool {
return head == nil
}
func node(at index: Int) -> Node<T>? {
guard 0..<count ~= index else { return nil }
var node = head!
var current = 0
while index > current, let next = node.next {
node = next
current += 1
}
return node
}
func append(value: T) {
let newNode = Node(value)
guard !isEmpty else {
head = newNode
tail = newNode
count += 1
return
}
if count == 1 {
head?.next = tail
}
tail?.next = newNode
newNode.previous = tail
tail = newNode
count += 1
}
func insert(_ value: T, at index: Int) {
let node = Node(value)
if index == 0 {
node.next = head
head?.previous = node
head = node
count += 1
} else if index == count {
append(value: value)
} else {
assert(0..<count ~= index, "Out of Index: \(index), range: \(0)..<\(count)")
let next = self.node(at: index)
let before = next?.previous
node.previous = before
node.next = next
before?.next = node
next?.previous = node
count += 1
}
}
func removeAll() {
head = nil
tail = nil
count = 0
}
@discardableResult
func remove(node: Node<T>) -> T {
if node === head, node === tail {
head = nil
tail = nil
return node.value
} else if node === head {
defer {
head = node.next
head?.previous = nil
}
return node.value
} else if node === tail {
defer {
tail?.previous = tail
tail?.next = nil
}
return node.value
} else {
let before = node.previous
let next = node.next
before?.next = next
next?.previous = before
node.next = nil
node.previous = nil
count -= 1
return node.value
}
}
@discardableResult
func remove(at index: Int) -> T? {
assert(0..<count ~= index, "Out of Index: \(index), range: \(0)..<\(count)")
guard let node = node(at: index) else { return nil }
return remove(node: node)
}
}
extension LinkedList.Node: CustomStringConvertible {
var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> " + "\(next)" + " "
}
}
extension LinkedList: CustomStringConvertible {
var description: String {
guard let head = head else {
return "List is Empty"
}
return "\(head)"
}
}
LinkedList를 구현했다면, Queue는 간단하게 구현할 수 있겠죠?
// MARK: - Queue
struct Queue<T> {
private var list = LinkedList<T>()
var count: Int {
return list.count
}
var isEmpty: Bool {
return list.isEmpty
}
var front: T? {
return list.first
}
var last: T? {
return list.last
}
func enqueue(_ element: T) {
list.append(value: element)
}
func dequeue() -> T? {
guard !list.isEmpty else { return nil }
return list.remove(at: 0)
}
}
extension Queue: CustomStringConvertible {
var description: String {
return list.description
}
}
DoubleStack
하지만 보시다시피 Queue하나를 쓰자고 LinkedList의 코드 양이 상당합니다...
stack 두 개로 LinkedList 없이 구현할 수도 있는데요, 코드 양도 적고 직접 구현에서 버그 소지가 많은 LinkedList 보다도 더 믿고 사용할 수가 있겠네요. 문제를 풀면서 확인해봤는데 제 구현 문제일 수도 있는데, LinkedList를 사용하는 것보다도 DoubleStack을 사용하는 게 더 빠르더라구요!
그럼 stack 두 개로 어떻게 구현하는지 알아보겠습니다.
이해하면 생각보다 어렵지 않습니다. 구현을 위해 필요한 기본 이해는 배열을 뒤집는 데 (reverse) O(1)의 복잡도가 걸린다는 것입니다.
바라보고 있는 Point만 옮겨주면 되기 때문이죠!
다음으로는 입력만 받는 배열 (inbox) 과, 출력만 담당하는 배열 (outbox) 2개를 준비합니다.
말 그대로 inbox는 입력만, outbox는 출력만 하면 되는데요,
출력을 하는데 outbox가 비어있다면, 그동안 입력 받았던 배열을 뒤집어서 outbox에 넣어주고 Inbox는 비워줍니다.
말이 어려운데 퍼주는 양동이에 물이 다 떨어지면 받아뒀던 양동이를 부어서 채워주는거에요!!!
코드를 보시면 금방 이해가 되실거에요 :)
구현
struct DoubleStackQueue<Element> {
private var inbox: [Element] = []
private var outbox: [Element] = []
var isEmpty: Bool{
return inbox.isEmpty && outbox.isEmpty
}
var count: Int{
return inbox.count + outbox.count
}
var front: Element? {
return outbox.last ?? inbox.first
}
init() { }
init(_ array: [Element]) {
self.init()
self.inbox = array
}
mutating func enqueue(_ n: Element) {
inbox.append(n)
}
mutating func dequeue() -> Element {
if outbox.isEmpty {
outbox = inbox.reversed()
inbox.removeAll()
}
return outbox.removeLast()
}
}
extension DoubleStackQueue: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Element...) {
self.init()
inbox = elements
}
}
시간복잡도
이론상으로는 LinkedList와 DoubleStack 방식의 구현 모두 enqueue와 dequeue 가 상수시간 안에 처리가 가능하지만,
실제로는 차이가 조금 있었습니다.
백준 1697 숨바꼭질 bfs 문제를 위 방법으로 풀어봤는데요,
DoubleStack이 28ms
LinkedList가 64ms
그냥 array로 풀었을 때 380ms
의 시간이 소요되었답니다!
처음에는 LinkedList에 removeFirst를 구현하지 않고 그냥 remove(at:) 를 가지고 풀었었는데 나중에 removeFirst를 구현해서 효율을 조금 높였습니다.
읽어주셔서 감사합니다 !!