[Kotlin] 큐 - Queue

🔷 큐 (Queue)이란?

    큐(Queue)은 일렬로 늘어선 사람들의 줄을 말하기도 한다.

    선형 리스트의 한쪽에서 자료의 입력되고, 반대 쪽에서 출력이 가능한 자료구조이다.

    Q = (q0, ... , qn-1) 구조일 때 q0이 앞(front)원소, qn-1을 뒤(rear)원소라고 한다.

    이런 큐의 구조를 선입선출 (FIFO, First-In First-Out)구조 라고 한다.

🔹큐의 시작과 끝

        큐는 한 쪽에서는 입력, 반대 쪽에서는 출력이 일어난다.

        가장 먼저 온 사람이 가장 먼저 나가는 대기줄의 형태와 동일하다.

        큐는 사용하기 위하여 큐의 상태를 나타내는 front와 rear 변수가 필요하다.

        front는 가장 앞에 있는 원소를 가르키며, 제일 먼저 들어온 변수부터 나가는 출구이다.

        rear은 가장 뒤에 있는 원소를 가르키며, 새 자료는 rear가 가르키는 자료 위에 쌓이는 입구이다.

        rear가 큐의 최대값-1인 상태일 때 큐가 꽉 찬 상태이다.

 

        🔹add(), offer() : 큐의 데이터를 삽입하는 연산

        🔹remove(), poll()   : 큐의 데이터를 삭제 및 반환하는 연산

🔹선입선출 (FIFO, First-In First-Out)

        큐은 한쪽 끝(rear)에서 데이터의 삽입이 일어나고 반대쪽(front)에서 삭제 작업이 진행된다.

        따라서 가장 먼저 들어온 원소가 가장 먼저 삭제되는 특성을 가진다.

       이런 큐의 구조를 선입선출(FIFO : First-Int First-Out)를 가지게 된다.

---

🔷 메모리 초과

       큐의 최대 용량을 초과하였을 경우에 오류가 발생한다.
       그러나 연결리스트(LinkedList)는 메모리의 한계까지 만들지 않는 이상 용량 제한이 발생하기 힘들다.

       만일의 사태를 대비하여 주의는 필요하나 큰 차이는 없다.

---

🔷 해시맵 사용법

     Queue -> 큐 초기 설정

     add, offer -> 큐에 데이터 삽입

     remove, poll -> 큐에 데이터 반환 및 삭제

     element, peek -> 큐에 첫 값(가장 앞 원소, front) 확인

     size -> 큐의 크기 반환

     elementAt(i) -> 의 i번째 원소 반환

     isEmpty, isNotEmpty  -> 큐의 원소 존재 유무 확인

---

🔹Import

       kotlin에서는 자체적으로 Queue을 제공하지 않으므로 직접 구현하거나 java에서 호출한다.

       현 게시글에서는 java에서 호출하는 방식으로 작성한다.

       java.util 에서 전체(*)혹은 큐(Queue)만 import하여 사용한다.

import java.util.*
import java.util.Queue

🔹Queue

        큐 초기 설정

        큐로 선언을 하고 연결리스트로 할당한다.

val queue : Queue<DataType> = LinkedList()

🔹add, offer

        큐에 데이터 삽입

        가장 마지막(rear 위치)에 원소를 삽입한다.

queue.add(value)
queue.offer(value)

        ✨ add()과 offer()의 출력 차이

                add(): 가득 찬 queue일 경우 illegalStateException 발생

                offer() : 가득 찬 queue일 경우 false 반환

🔹remove, poll

       큐에 데이터 반환 및 삭제

       가장 처음(front 위치)에 원소를 반환 및 삭제한다.

queue.remove()
queue.poll()

        ✨ remove()과 poll()의 출력 차이

                remove(): 빈 큐일 경우 NoSuchElementException 발생

                poll() : 빈 큐가일 경우 null 반환

🔹element, peek

        큐에 첫 값(가장 앞 원소, front) 확인

queue.element()
queue.peek()

        ✨ element()과 peek()의 출력 차이

                isEmpty(): 빈 큐일 경우 NoSuchElementException 발생

                isNotEmpty() : 빈 큐일 경우 null 반

🔹size

        큐의 크기 반환

queue.size

🔹elementAt(i)

        큐의 i번째 원소 반환

        가장 앞(front)에 원소부터 인덱스 값을 계산한다.

queue.elementAt(index)

🔹isEmpty | isNotEmpty

        큐의 원소 존재 유무 확인

queue.isEmpty()
queue.isNotEmpty()

        ✨ isEmpty()과 isNotEmpty()의 출력 차이

                isEmpty(): 빈 큐일 경우 true

                isNotEmpty() : 빈 큐가 아닐 경우 true

---

🔷 큐의 모든 원소 삭제

🔹isNotEmpty() + poll()

        큐가 비어있지 않을 경우 반복

        큐의 원소를 삭제

while(queue.isNotEmpty()){
	queue.pop()
}