Java(Queue)

큐 Queue는 데이터를 저장하는 선형 자료구조로, 차례를 기다리는 줄이라는 의미를 가지고 있는 단어처럼 먼저 들어온 자료부터 순서대로 처리하는 방식을 말한다.

한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 구조로서 선입선출(FIFO : First In First Out)의 특징을 가진다.

 

 

 

Queue의 특징

• 맨 앞(front) 에서 자료를 꺼내거나 삭제하고, 맨 뒤(rear)에서 자료를 추가 함
• Fist In First Out (선입선출) 구조
• 일상 생활에서 일렬로 줄 서 있는 모양
• 순차적으로 입력된 자료를 순서대로 처리하는데 많이 사용 되는 자료구조
• 콜센터에 들어온 문의 전화, 메세지 큐 등에 활용됨
• jdk 클래스 : ArrayList

 

자바에서 큐는 Queue 인터페이스로 정의되며, 이 Queue 인터페이스를 구현한 3개의 클래스(ArrayDeque, LinkedList, PriorityQueue)가 주어진다.

 

예외적인 큐는 우선 순위 큐( PriorityQueue)이다. 우선 순위 큐는 원소들이 우선순위에 따라서 저장한다.
원소들이 무작위로 삽입되었더라도 정렬된 상태로 원소들을 추출한다. 즉, remove() 를 호출할 때마다 가장 작은 원소가 추출된다. 

히프(heap)라는 자료구조를 내부적으로 사용하며, 히프는 이진 트리의 일종으로 add(), remove() 호출 시 가장 작은 원소가 효율적으로 트리의 루트로 이동한다. 

 

디큐(Deque)는 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있다. Deque 인터페이스는 ArrayDeque와 LinkedList 클래스들로 구현된다. 

 

Queue 메서드

• add() : 새로운 원소의 추가가 큐의 용량을 넘어서지 않으면 원소를 추가한다. (용량 넘을 시 IllgalStateException 발생)
• offer(): 원소 추가에 실해하면 false 반환한다.
• remove(), poll() : 큐의 처음에 있는 원소 제거 및  가져온다. (큐에 원소가 없으면 remove() 는 NoSuchElementException 발생, poll() 는 null 반환 )
• element(), peak() : 큐의 처음에 있는 원소를 삭제하지 않고 가져온다.( 큐가 비어 있으면  element()는 NoSuchElementException 발생, peak()는 null 반환)

 

 

코드 예시)

이 방식은 배열의 끝에 도달했을 때 자동으로 시작 위치로 돌아가지 않으므로 순환 구조가 아닌 일반 큐의 동작 방식이다.

 

 

코드 예시2)

배열을 활용한 Queue를 순환구조로 수정하기