Queue
먼저 들어온 데이터가 가장 먼저 나가는 특징을 가진 자료구조
📌 FIFO 구조 : ( 선입선출 ) 먼저 들어간 것이 먼저 나온다.
구현 방법 :
배열로 구현 후에 가장 마지막 인덱스부터 dequeue 해준다.
Enqueue
queue에 새로운 데이터를 삽입한다.
enqueue 는 기존 queue의 마지막(오른쪽)에 데이터를 삽입한다.
Dequeue
queue에 있는 데이터를 꺼낸다.
dequeue는 기존 queue의 첫번째(왼쪽)의 데이터를 꺼낸다.
전체 코드
struct Queue<Element> {
private var queue: [Element] = []
var count: Int {
return queue.count
}
var isEmpty: Bool {
return queue.isEmpty
}
mutating func enqueue(_ element: Element) {
queue.append(element)
}
mutating func dequeue() -> Element? {
return isEmpty ? nil: queue.removeFirst()
}
}이때 dequeue를 하게 되면 모든 데이터를 한 칸씩 이동해야 하는데 이때 오버헤드가 발생하고
O(n) 의 시간복잡도가 소요된다.
이를 해결하기 위해서 두가지 방법이 있다.
dequeue의 시간복잡도 줄이기
1. 첫번째 데이터를 가리키는 포인터 변수 활용
첫번째는 head 변수를 따로 두고 head 변수가 가리키는 인덱스를 dequeue 하면서 head를 이동시킨다. 이렇게되면 queue에서 배열을 움직이는 실제 작업을 하지 않아도 된다.
다시 말해 queue의 첫번째 위치로 데이터를 옮기는 것이 아닌 head가 가리키는 것이 첫번째 위치가 되는 것이다.
O(1) head 포인터 활용
struct Queue<Element> {
private var queue: [Element?] = []
var head = 0
var count: Int {
return queue.count
}
var isEmpty: Bool {
return queue.isEmpty
}
mutating func enqueue(_ i: Element) {
queue.append(i)
}
mutating func dequeue() -> Element? {
guard head <= count, let element = queue[head] else { return nil }
queue[head] = nil
head += 1
if head > 10 {
queue.removeFirst(head)
head = 0
}
return element
}
}이때 어느정도 dequeue를 한 후에는 앞의 nil로 변경된 배열요소들을 삭제하는 작업이 필요하다.
위의 코드에서는 10으로 설정했다.
이 경우 순수 dequeue 작업의 시간복잡도는 O(1)이지만
head 앞의 nil이 된 항목들을 삭제하는 과정에서의 시간복잡도는 removeFirst(Int)의 과정이 O(n)의 시간복잡도가 소요되기 때문에 O(n)이 소요된다.
- removeFirst(Int)
괄호 안의 Int값까지 배열의 첫번째 인덱스부터 삭제하는 메소드
위의 코드에서는 head 값까지 dequeue 된 queue의 항목을 지우는데 사용된다.
Apple Developer Documentation
2. Stack 배열을 활용
두번째는 2개의 Stack 배열을 활용하는 방법이다.
하나의 Stack은 데이터를 삽입하는 enqueue만을 수행한다. (inStack)
또 다른 Stack은 데이터를 삭제하는 dequeue만을 수행한다. (outStack)
dequeue 작업은 inStack 을 reversed()하여 outStack 에 넣은 후에 popLast() 메소드로 맨 뒤의 데이터를 삭제한다.
Swift 의 reversed() 시간복잡도는 O(1) 이고 popLast() 또한 O(1)의 시간복잡도가 소요되므로 dequeue 작업에 소요되는 시간복잡도는 O(1)이다.
O(1) 2개의 Stack 배열 활용
struct DoublyStackQueue<Element> {
private var inStack: [Element] = []
private var outStack: [Element] = []
var isEmpty: Bool {
return inStack.isEmpty && outStack.isEmpty
}
mutating func enqueue(_ element: Element) {
inStack.append(element)
}
mutating func dequeue() -> Element? {
if outStack.isEmpty {
outStack = inStack.reversed()
inStack.removeAll()
}
return outStack.popLast()
}
}이때 dequeue 작업에서 outStack 에 inStack을 옮겨줬다면 inStack은 비워주어야한다.
dequeue 작업이 끝나고 outStack이 다시 비워졌을때 비워지지 않은 inStack을 다시 outStack에 넣어주게 되면 dequeue했던 데이터들이 다시 들어가기 때문이다.
