Queue는 대기열이라고 이라고 생각하면된다.
선입선출(FIFO : First in First Out) 자료구조다
놀이공원의 대기줄, 은행의 번호표를 생각하면 된다
시간 순으로 어떤 작업 또는 데이터를 처리할 필요가 있는 것들은 큐의 성질을 가지고 있다. 대표적으로 알고리즘에서는 BFS(너비 우선 탐색)에 사용된다
<Queue Interface에 선언 할 메소드>
offer()의 경우 리스트에서 add()와 비슷한 역할이고, poll()의 경우는 remove()와 비슷한 역할, peek()은 element()와 비슷한 역할이다.
차이점은 add(), remove(), element()는 내부적으로 예외를 처리하고 있다
하지만 offer(),peek(),element()의 경우 예외를 던지는 것이 아니라 null또는 false를 던진다
offer() : 가능한 경우 요소를 삽입하고 그렇지 않으면 false를 반환한다
remove()와 poll()메서드는 큐의 헤드를 지우고 리턴한다. remove()는 예외를 throw하고 poll()메소드는 null을 return한다
element()와 peek() 메소드는 큐의 헤드를 지우지 않고 리턴한다
대개 LinkedList로 구현한 큐가 쓰이지만 상황에따라 ArrayDeque나 PriorityQueue처럼 내부적으로 배열을 사용하여 구현하여 사용하고 있는 큐 자료 구조도 있다.
배열을 사용하여 구현되는 자료구조 클래스는 내부에서 최상위 타입 배열인 Object[]배열을 사용하여 데이터들을 사용한다
큐는 선형적으로 접근하게 되면 쏠림 현상이 발생하는데 매번 삭제 연산 때마다 삭제된 원소 뒤의 모든 원소들을 한 자리씩 앞으로 땡겨오는 것은 매우 비효율적이고 그렇다고 배열 크기를 늘리자니 배열이 꽉찬 상태인 것도 아니라 빈 공간을 낭비하게 된다
이를 해결하기 위한 간단한 방법은 앞의 빈 자리에 다시 채워넣는 것이다. 배열을 원형이라고 생각하면 가장 마지막 원소의 위치를 가리키는 변수 front(앞)과 rear(뒤)가 필요하다
