![[알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐),ArrayList, Stack으로 Queue 구현하기 - Kotlin](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FLTIg2%2FbtrfTGSPkcY%2F65x96VMcKqxjgGOVGSlD0k%2Fimg.jpg)
목차
Queue 개념
큐는 영화티켓을 사기 위해 기다릴 때, 롤 큐를 기다릴 때처럼 실생활에 적용되는 사례가 많습니다. 이 큐의 특징은 선입선출(FIFO: 먼저 들어온 것이 먼저 나가는 형태)이라는 것입니다.
Queue 인터페이스 구현
큐에 인터페이스를 만들어보겠습니다.
interface Queue<T>{
fun enqueue(element: T): Boolean
fun dequeue():T?
val count: Int
get
val isEmpty: Boolean
get() = count == 0
fun peek(): T?
}위에 4가지에 키 함수가 있습니다.
enqueue: 맨뒤에 큐에 element를 삽입해준 후 성공하면 true를 반환합니다.
dequeue: 큐에 가장 앞부분에 element를 지우고 지운 값을 리턴합니다.
isEmpty: count속성을 사용하여 큐가 비어있는지 확인합니다.
peek: queue에 가장 앞부분을 리턴해줍니다. 지우지는 않습니다.
함수를 보시면, 삽입은 뒤에서만 일어나고 제거는 맨 앞에서만 일어납니다.
Queue 예제
예제를 통해 Queue에 사용 예제를 보겠습니다. 아래 이미지를 영화 티켓을 위한 큐라고 가정해보겠습니다.
- 맨 앞에 있는 Ray는 영화 티켓을 받았기 때문에 dequeue가 되었고,
- Peek함수를 실행시키면 queue에서 가장 앞에 있는 Brian을 리턴합니다.
- Vicki가 새로 들어왔기 때문에 enqueue("Vicki")로 추가할 수 있습니다.
4가지 큐 생성
Queue를 구현하는 대표적인 4가지 생성법을 다뤄보겠습니다.
1. ArrayList 베이스 큐
2. Double LinkedList 베이스 큐
3. Ring Buffer 베이스 큐
4. Two Stacks 베이스 큐
ArrayList 베이스 큐
ArrayList 큐 클래스 생성
ArrayList로 이루어진 큐를 만들기 위해서 먼저 클래스를 구현해주겠습니다.
class ArrayListQueue<T> : Queue<T> {
private val list = arrayListOf<T>()
}
Queue를 상속받은 ArrayListQueue라는 이름을 가진 클래스를 생성해주겠습니다.
Count와 Size 함수 오버라이드
class ArrayListQueue<T> : Queue<T> {
private val list = arrayListOf<T>()
override val count: Int
get() = list.size
override fun peek(): T? = list.getOrNull(0)
}- count로 size를 받을 수 있습니다.
- 가장 앞에 있는 값을 받을 수 있습니다.
Enqueue 함수 오버라이드
Enqueue는 element를 arraylist끝에 추가합니다.
사이즈에 상관없이 enqueue는 O(1) operation입니다. O(1)은 Big-O complexity chart 중 하나입니다.
Big-O 간단 설명
시간 복잡도에 관하여 간단히 설명하면 그래프 기준 빨간색에 가까울수록, 테이블 기준으로 위로 갈수록 알고리즘이 빨라지며, n 값이 커질수록 알고리즘 수행 시간이 급격하게 늘어나게 됩니다. 눈치채셨겠지만 오른쪽 테이블을 그래프로 나타낸 것이 왼쪽 그래프입니다.
n값은 우리가 집어넣는 계산 인풋을 의미하고 계산할게 많아지면 수행 시간이 늘어나게 됩니다. 아래 Big O 중 O(1)을 다뤄보겠습니다. O(1)은 안에 상수가 들어가 있으므로 n에 영향을 받지 않습니다(즉 데이터 처리할 개수 n의 영향을 받지 않습니다.). 상수라고 부르기도 합니다.
O(n)은 선행(Linear)입니다. 말 그대로 n 즉 x값 이 늘어나는 만큼 시간이 오래 걸리게 됩니다. (for 문이 한번 있는 식)
O(n^2)은 반복문이 두 번 있는 식입니다. 선행보다 오래 걸리게 됩니다.
다른 식
즉 위표에서는 O(1000!) 가장 수행 시간이 길다는 것을 나타냅니다.
Enqueue를 통해서 MIC를 추가하면 뒤에 빈 공간이 아직 있는 걸 확인하실 수 있습니다.
override fun enqueue(element: T): Boolean {
list.add(element)
return true
}
계속 추가하다가 더 이상 빈 공간이 없게 되면 arraylist가 꽉 차서 더 공간이 필요하게 됩니다.
그래서 공간을 추가하게 되면 arraylist에 공간을 늘리기 위해 사이즈를 바꿔야 합니다. 사이즈를 바꾸는 것은 O(n)입니다. 사이즈를 바꾸기 위해서는 새로운 메모리를 지정하고 지금 데이터를 모두 복사해서 새로운 리스트에 전달해주어야 합니다. 그만큼 처리시간이 많이 걸리게 됩니다.
Dequeue 함수 오버라이드
element를 지우기 위해서는 enqueue보더 좀 더 많은 작업을 필요로 합니다.
override fun dequeue(): T? =
if (isEmpty) null else lsit.removeAt(0)만약 큐가 비어있다면, dequeue는 null을 반환합니다. element가 존재한다면, 가장 앞에 값을 지웁니다.
이 작업은 O(n)입니다.
ToString 함수 오버라이드
디버깅을 위해서 toString을 오버라이드 해야 합니다. 아래 코드를 추가해주세요
override fun toString(): String = list.toString이제 위에서 만든 ArraylistQueue를 사용해보겠습니다.
"Queue with ArrayList" example{
val queue = ArrayListQueue<String>().apply{
enqueue("Ray")
enqueue("Brian")
enqueue("Eric")
}
println(queue)
queue.dequeue()
println(queue)
println("Next up: ${queue.peek()}")
}Ray, Brian Eric을 queue에 추가하고, Ray를 제거했습니다. 그리고 Brian이 맨 앞에 있는 것을 peek로 확인하였습니다.
ArrayList Queue의 장점/단점
| Operations | 최선 | 최악 |
| enqueue | O(1) | O(1) |
| dequeue | O(n) | O(n) |
| Space Complexity | O(n) | O(n) |
Dequeue를 제외하고 대부분 operation은 입력 크기에 따라 선형적으로 증가합니다.
Doubly LinkedList 베이스 큐
Doubly LinkedlIst는 LinkedList와 같은 개념인데 양방향으로 연결되어있는 LinkedList입니다. DoublyLinkedList를 구현해보겠습니다.
class LinkedListQueue<T> : Queue<T> {
private val list = DoublyLinkedList<T>()
private var size = 0
override val count:Int
get() = size
}
Enqueue함수 오버라이드
LinkedList queue 클래스 안에 오버라이드 해주시면 됩니다.
override fun enqueue(element: T): Boolean {
list.append(element)
size++
return true
}Double LinkedList의 특징에 따라 tail 노드에 prev와 next를 업데이트해줍니다. size를 늘릴 수 있습니다. 이것은 O(1)입니다.
Dequeue함수 오버라이드
override fun dequeue(): T? {
val firstNode = list.first? : return null
size--
return list.remove(firstNode)
}이 코드를 보시면 먼저 queue에 element가 존재하는지 확인합니다. 그리고 존재하지 않는다면, null을 리턴하고 있다면 사이즈 값을 -1한후 가장 앞 node를 지웁니다.
가장 앞에 있는 Node를 지우는 것도 O(1)입니다. ArrayList에서는 리스트에 있는 Element를 하나씩 옆으로 모두 옮겨줘야 했지만, DoublyLInkedList에서는 next와 previous pointer만 첫 번째 노드에서 두 번째 노드로 바꿔주면 됩니다.
Peek함수 오버라이드
peek함수입니다. 리스트에 가장 앞에 있는 Element를 찾습니다.
override fun peek(): T? = list.first?.value
ToString 함수 오버라이드
디버깅을 위해 toString을 오버라이드 해주겠습니다.
override fun toString(): String = list.toString()"Queue with Doubly Linked List" example{
val queue = LinkedListQueue<String>().apply{
enqueue("Ray")
enqueue("Brian")
enqueue("Eric")
}
println(queue)
queue.dequeue()
println(queue)
println("Next up: ${queue.peek()}")
}
Doubly LinkedList Queue 장점/단점
| Operations | 최선 | 최악 |
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
| Space Complexity | O(n) | O(n) |
ArrayList Queue에서는 dequeue아이템이 선형적으로(O(n)) 오퍼레이션 시간이 증가했지만 DoublyLinkedList에서 dequeue는, prev와 head 포인터만 변경해주면 됐으므로, 상수(O(1))로 증가함으로 더 빠르게 처리되는 걸 알 수 있습니다.
그럼 ArrayList보다 처리가 빠른데 단점은 무엇일까요? 테이블에는 나와있지 않지만 LinkedList특성상 list에 모든 element들은 node에 앞과 뒤가 어떤 node와 연결되어있는지 참조하게 됩니다. 이렇게 되면 ArrayList보다 메모리 할당량이 높아지게 됩니다.
Ring Buffer 베이스 큐
Ring Buffer Queue개념 이해
링 버퍼는 원형 큐라고도 불립니다. 고정된 array 크기를 가지고 있습니다. 그리고 링이라는 의미와 같이, element를 추가할 수 있는 곳에 가장 끝까지 오면 더 이상 추가가 불가능하고 다시 처음 시작점으로 돌아가게 됩니다.
링 버퍼에는 2가지 포인터가 있습니다:
1. read: queue에 앞부분을 계속 업데이트해줍니다.
2. write: 다음에 올 자리를 업데이트해줍니다.
Enqueue
이제 read와 write, 두 포인터를 활용하여, enqueue와 dequeue 가 작동 시 포인터가 어떻게 작동하는지 확인하겠습니다.
enqueue를 했을 때 write은 queue에 추가될 item이 들어갈 자리로 이동해 있는 걸 확인하실 수 있습니다.
enqueue를 해줄 때마다 이렇게 write의 index는 하나씩 증가하여, 추가적으로 2번을 enqueue를 array에 끝까지 도달하였습니다. 이제 dequeue를 해보겠습니다.
dequeue를 하게 되면 read의 index가 하나씩 증가합니다. 위 그림은 2번 dequeue를 진행하여 인덱스가 2 증가하여 john까지 도달했습니다. 여기서 아이템을 한 번 더 enqueue 하면 write의 index는 어떻게 될까요?
Ringbuffer에 특성에 따라 write은 다시 처음으로 되돌아갑니다.
read 또한 2번 더 dequeue를 진행해주면 array에 끝에 도달하게 되어 다시 시작점으로 이동하게 됩니다.
결론:
1. read와 write이 array에 끝에 도달하면, 다시 시작점으로 되돌아옵니다.
2. read와 write이 같은 인텍스에 위치하면 queue가 비어있다는 것을 확인할 수 있습니다.
Ring Buffer Queue클래스 만들기
Ring Buffer Queue를 구현해보겠습니다.
class RingBufferQueue<T>(size: Int): Queue<T>{
private val ringBuffer:RingBuffer<T> = RingBuffer(size)
override val count: Int
get() = ringBuffer.count
override fun peek(): T? = ringBuffer.first
}size 파라미터가 필수로 들어가게 됩니다. 왜냐하면 ringbuffer는 항상 array 크기가 정해져 있기 때문입니다.
- ringBuffer에서 ringbuffer queue에 쓸 함수를 불러오겠습니다.
- count와 peek를 ring buffer에서 함수를 오버라이드 합니다.
- count를 가져오게 되면 isEmpty함수도 같이 가져오게 됩니다.
- 이 두 가지 함수는 O(1) 오퍼레이션입니다. 위에서 다뤘다시피 O(1)은 상수식입니다.
Enqueue 함수 오버라이드
RingBuffer Queue 클래스 안에 오버라이드 해주시면 됩니다.
override fun enqueue(element: T): Boolean =
ringBuffer.write(element)- enqueue 함수를 실행할 때마다 write pointer가 하나씩 증가합니다.
- 그리고 리턴 값을 보면 Boolean인 것을 확인할 수 있습니다.
- 이 이유는 RingBuffer는 array가 정해진 크기기 때문에 정해진 크기보다 더 enqueue를 하게 될 경우 false를 반환하고 시작점으로 보내야 하기 때문입니다.
Dequeue 함수 오버라이드
Dequeue를 오버라이드 해주겠습니다.
override fun dequeue(): T? =
if(isEmpty) null else ringBuffer.read()- 값이 비어있다면 null을 반환하고, 비어있지 않다면 read가 실행됩니다.
ToString 함수 오버라이드
디버깅을 위해 toString을 오버라이드 해주겠습니다.
override fun toString():String = ringBuffer.toString()- toString을 활용하여 디버깅해보겠습니다.
"Queue with Ring Buffer" example{
val queue = RingBufferQueue<String>(10).apply{
enqueue("Ray")
enqueue("Brain")
enqueue("Eric")
}
println(queue)
queue.dequeue()
println(queue)
println(queue)
println(next("Next up:${queue.peek()}"))
}
RinBuffer Queue에 장점/단점
| Operations | 최선 | 최악 |
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
| Space Complexity | O(n) | O(n) |
- LinkedList와 같은 테이블과 같습니다. 그럼 다른 점은 무엇일까요?
- Ringbuffer는 size가 정해져 있다는 것입니다. 이 의미는 enqueue를 하다가 fail 할 수 있다는 의미이기도 합니다.
Two-Stack 베이스 큐
Stack과 Queue에 차이
우선 Stack과 Queue에 차이를 간단하게 알아보겠습니다.
Queue는 FIFO(선입선출: 가장 먼저 들어온 element가 먼저 반환)이고 Stack은 LIFO(후입 선출: 가장 마지막에 들어온 element가 먼저 나감)입니다. 그런데 Stack으로도 queue를 구현할 수 있습니다. 그러면 FIFO(선입선출) 형태를 만들어야 하는데, 2개의 Stack을 이용하면 됩니다.
스택에 대해 궁금하시다면 아래 링크를 확인해주세요.
[알고리즘] Kotlin 스택자료 구조 설명 및 구현 - Stack Data Structure, pop, push, peek, count
목차 스택 자료구조 개념 스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이
underdog11.tistory.com
Two Stack 큐 원리
아래 이미지는 2개의 스택을 이용하여 queue를 생성했을 때 모양입니다.
이와 같이 오른쪽에서 pop이 일어나고 있는 곳은 queue에 가장 앞부분이고 push가 되는 부분은 queue에 가장 마지막 부분이라고 생각하시면 됩니다.
Two Stack enqueue Dequeue 과정
초기 상태
Stack A: [] - 큐가 비어있는 상태입니다.
Stack B: []
Enqueue 1,2,3
Stack A: [1, 2, 3] - 큐에 1 2 3이 들어왔습니다.
Stack B: []
Dequeue Two Elements – 1
Stack A: []
Stack B: [3 2 1] — A에서 B로 모든 Element가 이동하였습니다. 이렇게 되면 LIFO형태처럼, 숫자가 1 2 3 순서로 들어왔던 게 먼저 들어온 순인 1 2 3으로 다시 나가게 됩니다.
Dequeue Two Elements – 2
Stack A: []
Stack B: [3] — 먼저 queue에 들어온 1과 2가 지워집니다.
Enqueue Element
Stack A: [4] - 4가 새로 들어왔습니다.
Stack B: [3]
Dequeue Element
Stack A: [4]
Stack B: [] —B에 3이 있었기 때문에 dequeue 되어 없어졌습니다.
두 개의 스택을 이용한 큐를 생성해보겠습니다.
class StackQueue<T> : Queue<T> {
private val leftStack = StackImpl<T>()
private val rightStack = StackImpl<T>()
}보시면 2개의 Stack을 만든 것을 확인하실 수 있습니다.
element를 enqueue 하게 되면 오른쪽 스택으로 이동하게 됩니다. Dequeue를 하면 당연히 반대로 오른쪽 스택에서 왼쪽으로 element가 이동합니다.
isEmpty함수 오버라이드
각 스택이 비어있는지 확인합니다.
override val isEmpty: Boolean
get() = leftStack.isEmpty &&rightStack.isEmpty
TransferElements 함수 만들기
이 함수를 통해 RightStack에 있는 element를 빼고 LeftStack으로 넣습니다. Stack은 원래 LIFO 형태지만 LeftStack으로 다시 넣어주면 RightStack과 LeftStack을 같이 활용해주면 FIFO 형태로 바뀝니다.
private fun transferElements() {
var nextElement = rightStack.pop()
while (nextElement != null) {
leftStack.push(nextElement)
nextElement = rightStack.pop()
}
}
Peek함수 오버라이드
Peek함수입니다. 리스트에 가장 앞에 있는 Element를 찾습니다.
override fun peek():T? {
if(leftStack.isEmpty) {
transferElements()
}
return leftStack.peek()
}leftStack이 비어있지 않다면, LeftStack에 가장 윗부분이 리스트에서 가장 앞에 있는 Queue입니다.
leftStack이 비어있다면, transferElements함수를 실행합니다. 그러면 element를 반환하거나 null을 반환하게 됩니다.
Peek를 찾는 것은 O(n) 오퍼레이션입니다.
Enqueue 함수 오버라이드
enqueue를 하게 되면 true를 반환하고 rightStack에 큐가 추가됩니다.
override fun enqueue(element: T): Boolean{
rightStack.push(element)
return true
}
Dequeue함수 오버라이드
override fun dequeue(): T?{
if(leftStack.isEmpty){ //1
transferElements() //2
}
return leftStack.pop() //3
}1. leftStack이 비어있는지 확인합니다.
2. leftStack이 비어있다면, rightStack에서 LeftStack으로 element를 이동합니다.
3. leftStack에 윗부분을 제거합니다.
ToString함수 오버라이드
디버그에 사용하기 위한 toString함수입니다.
override fun toString():String {
return "Left stack: \n$leftStack \nRight Stack \n$rightStack"
}
"Queue with Double Stack" example {
val queue = StackQueue<String>().apply {
enqueue("Ray")
enqueue("Brian")
enqueue("Eric")
}
println(queue)
queue.dequeue()
println(queue)
println("Next up: ${queue.peek()}")
}
Two Double Stack Queue 장점/단점
| Operations | 최선 | 최악 |
| enqueue | O(1) | O(1) |
| dequeue | O(1) | O(1) |
| Space Complexity | O(n) | O(n) |
- 링 버퍼 큐처럼 사이즈가 정해져 있지 않습니다.
- ArrayList는 Dequeue가 O(n)이었다면 Two Double Stack큐는 O(1) 오퍼레이션으로 진행돼서 더 빠릅니다.
- LinkedList보다 공간 지역성(spatial locality) 면에서 더 효율적입니다. 아래 이미지를 살펴보겠습니다.
- 위 그림과 같이 stack에서는 왼쪽과 같이 element가 저장될 때 바로 옆에 인접하게 저장하여, 메모리 효율이 좋고 cache도 덜 생성되는 반면 LinkedList는 오른쪽 그림과 같이 불규칙적으로 저장되어 메모리 효율이 안 좋습니다. 그러면 데이터를 접근하는데 더 시간이 오래 걸리고 cache를 더 생성하게 됩니다.