먼저 넣은 데이터를 먼저 꺼내는 자료구조 FIFO (First In First Out)의 형태

구조


class Queue<T> {
    inner class Node<T>(
        var data: T
    ) {
        var next: Node<T>? = null
    }
    private var first: Node<T>? = null
    private var last: Node<T>? = null

}

<aside> 💡 Queue의 Item은 노드로 이뤄져있고 Node는 다음 값을 가리키는 next라는 변수를 가지고 있다.

</aside>

add

만약 마지막 값이 null 이 아니라면 (존재하는 경우) 마지막 값의 다음을 가리키는 next에 해당 아이템을 넣어준다. 그다음 queue의 마지막 값을 갱신 해 준다. 값이 비어있다면 처음에 아이템을 넣어준다.

  fun add(item: T) {
        val t = Node(item)

        if (last != null) {
            last!!.next = t
        }
        last = t
        if (first == null) {
            first = t
        }
    }

remove

만약 큐의 처음이 비어있는 상태라면 (아무 값도 없는상태) Exception을 발생시킨다 그렇지 않다면 큐의 첫번째 값의 다음값을 큐의 첫번째 값으로 땡겨오고 땡겨온 값이 null인경우 (원래 아이템이 1개인경우)에는 last를 null로 갱신해준다. 그 다음 삭제된 값을 return 해준다.

fun remove(): T {
        if (first == null) {
            throw NoSuchElementException()
        }

        val data: T = first!!.data
        first = first!!.next

        if (first == null) {
            last = null
        }
        return data
    }

peek & isEmpty

 fun peek(): T {
        if (first == null) {
            throw NoSuchElementException()
        }
        return first!!.data
    }

    fun isEmpty(): Boolean {
        return first == null
    }