목표
- Queue의 특징을 익힌다.
- Queue 인터페이스를 구현하는 클래스(LinkedList)의 사용법과 특징을 익힌다.
개요
Queue란 FIFO(First In First Out)의 특징을 갖는 자료 구조이다. 즉, 먼저 들어온 값이 먼저 나가는 자료구조이다.
Kotlin에서는 Queue를 구현하기 위해 JCF(Java Collection Framework)에서 제공하는 Queue Interface를 이용한다.
하지만, Queue는 단순한 인터페이스이므로, 인터페이스를 구현하는 Class를 사용해야 하는데, 우리는 우리는 그중 LinkedList를 사용하여 Queue를 다루어본다.
생성
Queue 인터페이스를 이용하기 위해서는 인터페이스를 구현하는 구현체를 이용해야 한다. 그 중 대표적인 것이 LinkedList와 ArrayBlockingQueue이다. 우리는 이 글에서 LinkedList를 이용한 Queue을 생성을 다룬다.
LinkedList를 이용한 Queue를 생성하기 위해서는 타입에 Queue를 넣고 구현부에 LinkedList의 생성자를 넣어야 한다. LinkedList를 이용하여 생성된 Queue는 Capacity가 지정되어 있지 않으며 계속해서 값을 넣을 수 있다.
val queue: Queue<Int> = LinkedList<Int>()
Array가 있을 때는 list로 바꾼 다음 LinkedList의 생성자에 넣어주면 된다.
val queue: Queue<Int> = LinkedList(intArrayOf(1,2,3).asList())
조작
Queue Interface에는 다음의 6가지 연산을 지원한다.
- add(element : E) : Boolean
- offer(element : E) : Boolean
- remove() : E
- poll() : E
- element() : E
- peek() : E
입력[add, offer], 제거[remove, poll], 확인[element, peek]은 같은 연산을 수행하지만, 각각 세부 동작이 다르다. 지금부터 함께 살펴보자
add, offer
add와 offer은 값을 Queue에 추가해주기 위한 연산이다.
add는 Queue의 Capacity 인한 오류 발생 시 Exception이 발생하고, offer는 발생하지 않는다는게 차이점이다. 하지만, 현재 다루는 LinkedList에서는 메모리의 한계까지 LinkedList를 만들지 않는 이상 용량 값의 제한이 발생하기 어렵기 때문에 어느 것을 써도 상관없다. 이후 다루는 ArrayBlockingQueue에서는 용량 값에 제한을 줄 수 있어, 이때 주의해서 보아야 한다.
val queue: Queue<Int> = LinkedList<Int>()
queue.add(5) // queue = [5]
queue.add(6) // queue = [5, 6]
queue.offer(7) // queue = [5, 6, 7]
remove, poll
remove와 poll은 Queue에서 값을 빼내기 위한 연산이다. remove와 poll 수행 시 가장 먼저 들어간 데이터가 return 된다.
remove와 poll 또한 값이 null이 나올 경우 error handling이 되어있는지 안되어 있는지에 대한 차이점을 가지고 있다. remove는 더이상 빼낼 데이터가 없을 경우 NoSuchElementException을 발생시키고, poll은 null을 리턴한다.
val queue: Queue<Int> = LinkedList<Int>()
queue.add(1)
queue.remove()
queue.remove() // Exception in thread "main" java.util.NoSuchElementExceptionval queue: Queue<Int> = LinkedList<Int>()
queue.add(1)
queue.poll()
queue.poll() // null , No Error Thrown
element, peek
element와 peek은 현재 Queue의 Head에 어떤 값이 들어있는지 확인하기 위한 연산이다. Queue를 변화시키지 않으면서 맨 앞에 있는 element의 값을 보기 위한 것이다.
element와 peek의 차이점은 마찬가지로 error에 대한 handling이 되어있는지 되어있지 않은지이다. element는 값이 없으면 NoSuchElementException을 발생시키지만, peek은 null을 return 한다.
val queue: Queue<Int> = LinkedList<Int>()
queue.add(1)
queue.poll()
queue.peek() // null, No error thrown
queue.element() // Exception in thread "main" java.util.NoSuchElementException
