[JAVA] - 큐 (Queue)

큐 (Queue)

먼저 들어온 데이터가 가장 먼저 나가는 구조로 선입선출 (First In First Out; FIFO) 자료구조라 불린다.

데이터가 입력된 순서대로 계산이 필요한 경우 사용된다. (프린터 출력 대기열, 너비 우선 탐색 - BFS 등)

쉽게 이해하려면 은행 창구 앞에서 번호표를 뽑고 먼저 뽑은 사람먼저 상담을 진행하는 경우를 생각하면 될 것 같다. 

 

 

큐 공간 : 데이터가 존재할 수 있는 공간

Front : 큐 공간에서 데이터가 처음으로 들어가는 부분, 큐 공간의 맨 앞 부분

Rear : 큐 공간에서 데이터가 마지막으로 들어갈 수 있는 부분, 큐 공간의 맨 뒷 부분

Dequeue : 데이터가 꺼내지는 동작

Enqueue : 데이터가 삽입되는 동작

 

 

큐 (Queue) 사용법 및 주요 메서드

 

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();	// int형 queue 선언

 

위와같이 Queue 클래스를 import 해준 뒤에, Queue를 선언하여 사용할 수 있다.

 

우측 항을 보면 Queue가 아닌 LinkedList로 선언한 것을 볼 수 있는데,

큐는 인터페이스로 구현되어 있어 바로 객체를 생성할 수 없다.

인터페이스나 추상클래스는 참조되는 메소드들을 오버라이딩해서 구현한 뒤에 사용할 수 있기 때문이다.

Queue 객체 생성 시 오버라이딩 해야하는 메소드들

 

따라서 간편하게 사용하고자 LinkedList로 선언 하였는데, LinkedList에서도 큐에 필요한 연산들이 다 구현되어 있어 사용할 수 있는것이다. (다형성)

(다형성 : 하나의 객체나 메소드가 여러가지 다른 형태를 가질 수 있는 것)

 

① add(), offer()

    큐에 데이터를 삽입해준다.

 

// queue에 데이터를 삽입
queue.add(1);
queue.add(2);
queue.ofter(3);
queue.ofter(4);

 

 

② poll(), remove()

    큐에 데이터를 삭제한다.

    선입선출 구조로 인해 가장 먼저 삽입되는 데이터를 삭제한다.

 

//	queue 데이터 삽입
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
//	queue 데이터 삭제
queue.remove();
queue.poll();

 

 

큐에 데이터가 비어있을때 remove와 poll 명령에 차이가 있는데, remove 명령을 진행하면 예외가 발생하고,

poll 명령을 진행하면 null을 반환한다.

 

큐에 데이터가 비어있을 때, remove 명령과 poll 명령의 차이

 

③ size()

    큐에 크기를 구하는 메서드로 데이터의 개수를 의미한다.

 

queue.size()	// 큐의 크기를 구한다.

 

 

④ peek()

    큐에 첫번째 데이터를 참조한다.

 

queue.peek();	// 큐의 맨 처음 데이터를 조회한다.

 

 

⑤ clear()

    큐의 데이터를 모두 삭제한다.

 

queue.clear();	// 큐의 모든 데이터를 삭제한다.