[Java / 자료구조] 큐 (Queue) 정리

큐(Queue)란?

사전적 의미로는 무엇을 기다리는 사람, 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조이다. 이 자료구조에서는 앞(front)과 뒤(back)가 존재한다. 가장 먼저 진입한 데이터가 가장 먼저 나가고 마지막에 진입한 데이터는 먼저 들어온 데이터가 모두 빠져나가기 전까지는 빠져나갈 수 없다.

 

큐 사용 사례

• 프린터 인쇄

※ 프린터 인쇄 과정

1. 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업(임시 기억 장치의) Queue에 들어간다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.

예시처럼 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼(buffer)라고 한다.

 

컴퓨터와 프린터 사이의 데이터 통신을 정리하면

• 일반적으로 프린터는 속도가 느리다.
• CPU는 프린터와 비교하여 데이터를 처리하는 속도가 빠르다.
• CPU는 빠른 속도로 인쇄에 필요한 데이터(Data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
• 프린터는 인쇄 작업 Queue에서 데이터(Data)를 받아 일정한 속도로 인쇄한다.

 

큐의 특징

• 두 개의 입출력 방향을 가지고 있다. 입력, 출력 방향이 다르다.
• FIFO(First In First Out) 혹은 LILO(Last In Last Out)이라고 부른다.
• 데이터는 하나씩 넣고 뺄 수 있다.

 

큐 클래스 메서드

offer(E e)

주어진 객체 삽입(enqueue) boolean 타입을 리턴한다.

 

add(E e)

주어진 객체 삽입(enqueue) boolean 타입을 리턴한다.

 

peek()

head에 위치한 객체를 리턴한다. 큐가 비었다면 null 리턴한다.

 

element()

큐의 head 리턴한다. 큐가 비었다면 Exception

 

poll()

front에 위치한 객체 리턴 후 제거(dequeue) 큐가 비었다면 null 리턴한다.

 

remove(E e) 

특정 객체 E 제거한다. 큐가 비었다면 null

 

 

FIFO(First In First Out)

Ex.1 1, 2, 3, 4를 큐에 차례대로 넣는다.

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

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.add(3);     // queue에 값 3 추가
queue.add(4);     // queue에 값 4 추가

               queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
             1 <- 2 <- 3 <- 4
         <---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.

Ex.2 큐가 빌 때까지 데이터를 전부 빼낸다.

queue.poll();       // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();

               queue.poll()
출력 방향 <---------------------------< 입력 방향

          <---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 된다.