큐(Queue) 란?

큐란 ?

먼저 넣은 데이터가 먼저나오는 FIFO 구조로 저장하는 형식을 말한다.

큐 원리 그림출처) https://st-lab.tistory.com/184

 

큐의 종류?

선형 큐는 막대모양으로 된 큐이다. 크기가 제한되어있고, 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 옮겨야한다는 단점이있다.

환형 큐는 선형큐의 문제점(배열로 큐를 선언할 시, 큐의 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달한 후 실제로는 데이터 공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형큐이다. front가 큐 끝에 닳으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식이다. 

우선순위 큐는 우선순위를 이용하여 우선순위가 높은 순서대로 나게 된다. 실생활 예시를 들자면, 병원에서 기존 환자들을 진료보다가, 응급환자가 오게되면 먼저 진료하게 되는 경우로 이해하면 된다.

큐의 문제점? (위에서 언급)

큐를 구현하고 사용할 때, 데이터를 뺄 때는 front 위치의 하나의 값을 출력을 하면 front 가 한 칸씩 뒤로 밀려나게 되는데, 이럴 경우 큐의 가용범위도 줄어들며 큐의 재사용 또한 불가능해진다.

억지로 큐의 재사용을 위해 front 를 출력하고 front 의 인덱스를 한칸식 앞당긴다 하더라도 불필요한 연산이 너무 많아집니다. 

이러한 문제점이 발생해 개선한 원형큐를 사용합니다.

큐를 사용하는 곳은?

- BFS (너비 우선 탐색)

- 프린터 인쇄 대기열

- 선입 선출이 필요한 대기열 (티켓 카운터)

- 콜센터 고객 대기시간

- 캐시(Cache) 구현

- 작업 스케줄러 및 프로세스 관리

- 윈도 시스템의 메시지 처리기

큐 사용법 ?

Queue 인터페이스는 클래스로 구현된 Stack과는 다르게 큐 메모리 구조를 별도의 인터페이스 형태로 제공을합니다.

Queue를 상속 받은 하위 인터페이스들은 4가지다.

1. Deque<E>

2. BlockingDeque<E>

3. BlockingQueue<E>

4. TransferQueue<E>

 

Queue 는 대부분 위 하위 인터페이들 중, Deque 인터페이스를 구현한 LinkedList 클래스를 이용하여 인스턴스 화 시킨다.

ex. Qeueue<E> qu = new LinkedList<E>();

 

큐의 대표적 메서드 6개

add : 큐에 데이터를 넣고 성공하면 boolean형으로 값을 return 한다. (예외발생)

offer : 큐에 데이터를 넣고 성공하면 boolean 형으로 값을 return 한다. (값 리턴)

remove : 큐에서 제일 먼저 들어온 데이터를 제거하고 return 한다. (예외발생)

poll : 큐에 제일 먼저 들어온 데이터를 제거하고 해당 값을 return 하고, 비어있다면 null을 리턴한다. (값 리턴)

element : 큐에서 제일 먼저 들어온 데이터를 제거하지 않고 값을 return 한다. (예외발생)

peek : 큐에 제일 먼저 들어온 데이터를 제거하지 않고, 값을 return 해온다. (값 리턴)

 

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html

 

 

큐 구현 방법 ( 배열 / 리스트 ) ?

[JAVA]

선형큐 , 리스트큐로 구현

연결 리스트로 큐 구현