Queue란? Java Queue Class에 대해 알아보자!

오늘 포스팅할 내용은

Queue의 정의

Java Queue Class 구현

Queue Class 사용 예제입니다.

 

큐 ( Queue )

 

Queue란( 줄, 대기열 )?  

선입선출( First In First Out )의 자료구조이며, 먼저 들어오는 Data가 먼저 나가게 됩니다. 

 

Data가 들어오는 가장 뒤 위치를 Back( or Rear )이라 하며, 입력 동작을 Enqueue라고 합니다.

 

Data가 나가는 가장 앞의 위치를 Front라고 부르며, 출력 동작을 Dequeue라고 합니다.

 

일반적인 Queue는 유한 순서 리스트라고도 부릅니다.

 

 

원형 큐( Queue )

 

원형 큐

Queue를 위해 배열을 지정하고 Queue를 사용하다 보면 배열의 앞부분이 빈다는 점을 활용하여 배열의 맨 마지막 부분을 쓰면 다시 맨 처음부터 다시 Queue를 채우기 시작하는 형태의 Queue입니다.

 

원형 큐 또한 기존 큐와 같이 선입선출( FIFO ) 구조를 지닌다는 점에서 기존의 큐와 동일합니다.

 

하지만 마지막 위치가 시작 위치와 연결되는 원형 구조를 띄우기 때문에 링 버퍼( Ring Buffer )라고 부르기도 합니다. 

 

 

데크( Deque, Double Ended Queue )

일반적인 큐는 뒤에서만 입력이 이루어지고 앞에서만 출력이 가능한 데 비해, 데크는 양쪽에서 모두 입력/출력이 가능한 스택( Stack )과 큐( Queue )의 특징을 모두 갖고 있습니다.

 

이러한 자료 구조의 구현은 Array나 LinkedList 둘 다 가능하지만, 위의 그림과 같이 이중 연결 리스트( Double Linked List )로 구현하는 방법이 가장 잘 어울립니다.

 

이중 연결 리스트로 구현을 하면, 양쪽으로 head와 tail이라는 두 포인터를 가지고 있다가 새로운 요소가 추가될 때마다 앞 또는 뒤로 연결시켜주기만 하면 됩니다. 

 

Queue의 사용 용도

 

어떠한 함수/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 주로 사용합니다.

 

서로 다른 스레드( Thread ) 사이 또는 각 프로세스( Process ) 사이, 네트워크를 통하여 Data를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용합니다. 

 

Java Queue Class Method

• add(Element) : Element를 Queue의 끝 부분에 추가합니다.
• remove() : Queue의 첫 번째( 맨 앞 ) Element를 삭제합니다.
• peek() : Queue의 가장 마지막( Back ) Element를 반환합니다.
• isEmpty() : Queue가 비어있는지 진리 여부를 반환합니다.

 

Queue<Integer> queue = new LinkedList<>();

int temp = 1;

// Queue의 Back에 추가합니다.
queue.add(temp);

// return 1
queue.peek();

// return false
queue.isEmpty();


queue.remove();

// Queue의 크기를 반환합니다.
queue.size();

 

Queue의 사용 사례

• 너비 우선 탐색 ( BFS, Breadth-First Search ) 구현
• 캐시( Cache ) 구현
• 우선순위가 같은 작업 예약
• 선입선출이 필요한 대기열
• 어떠한 서비스의 대기순서
• 프린터의 출력 처리 순서
• Process 관리 

 

이번 포스팅에서는 Queue의 자료구조에 대해 알아보았습니다.