[Swift] Queue
Queue
Queue란, 한쪽 끝에서 삽입, 한쪽 끝에서 삭제가 이루어지는 유한 순서 리스트이다
- First-in-First-out의 선입선출 방식
- 먼저 들어간 원소가 먼저 나가게 되는 구조
- 음식점 대기줄, CPU의 테스크 스케줄링등이 Queue의 방식의 예
- BFS에서도 Queue를 사용하여 탐색해야 하는 노드의 리스트로 사용한다
Swift에서 Queue 구현하기
swift에서 Queue를 쉽게 구현하려면 queue
를 배열로 놓고 enqueue
는 append()
함수로, dequeue
는 removeFirst
함수로 대체할 수 있다
struct Queue<T> {
private var queue: [T] = []
public var count: Int {
return queue.count
}
public var isEmpty: Bool {
return queue.isEmpty
}
public mutating func enqueue(_ element: T) {
queue.append(element)
}
public mutating func dequeue() -> T? {
return isEmpty ? nil : queue.removeFirst()
}
}
하지만 위와 같은 queue
는 dequeue()
시 O(N)
의 시간복잡도가 걸린다는 것을 알 수 있다.
그러므로 stack
을 두 개 이용해 queue처럼 사용하는 방법을 사용한다.
inbox
& outbox
두 개의 Stack
으로, inbox
스택에서는 삽입만, outbox
스택에서는 삭제 연산만이 이루어지도록 한다.
-
삽입 연산
enqueue
시에는inout
스택에append()
를 해준다 -
삭제 연산
- 삭제 연산의 경우 살짝 복잡한데,
outbox
스택이 비어있을 경우,inbox
값들을 거꾸로 뒤집어(reversed())outbox
스택에 넣어준 후,outbox
스택의 맨 마지막 값을pop
해줍니다. outbox
스택이 비어있지 않을 경우outbox
스택의 맨 마지막 값을pop
해준다
- 삭제 연산의 경우 살짝 복잡한데,
class Queue<T> {
var inbox: [T]
var outbox: [T] = []
var count: Int {
return inbox.count + outbox.count
}
var isEmpty: Bool {
return inbox.isEmpty && outbox.isEmpty
}
init(_ queue: [T]) {
inbox = queue
}
func pushLast(_ element: T) {
inbox.append(element)
}
func pushFirst(_ element: T) {
outbox.append(element)
}
func popLast() -> T {
if inbox.isEmpty {
inbox = outbox.reversed()
outbox.removeAll()
}
return inbox.popLast()!
}
func popFirst() -> T {
if outbox.isEmpty {
outbox = inbox.reversed()
inbox.removeAll()
}
return outbox.popLast()!
}
}