Queue

Queue : 시퀀스의 한 쪽 끝에는 원소를 추가하고 다른 반대쪽으로는 제거할 수 있는 컬렉션 FIFO

Enqueue: 입력 연산, Dequeue: 출력 연산

만약 배열을 사용해서 Queue를 구현하면 Enqueue, Dequeue를 계속하면 데이터가 앞쪽으로 밀려나게 된다. 이를 해결하기 위해서는 원형 버퍼를 사용한다.

너비 우선 탐색 BFS나 캐시등을 구현할 때 유용하게 사용된다.

class Node(var item: Int, var next: Node?)
class MyQueue {
    var head: Node? = null
    var rear: Node? = null

    fun enqueue(item: Int) {
        val node = Node(item, null)
        if(head == null) {
            this.head = node
            this.rear = node
        } else {
            this.rear?.next = node
            this.rear = node
        }
    }

    fun dequeue(): Int? {
        val item = this.head?.item
        this.head = this.head?.next
        return item
    }

}