[JAVA] 자료구조 - 큐(Queue) , 배열과 링 버퍼(ring buffer)로 구현하기

큐(Queue)

큐(queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조 입니다.

먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO : First In First Out)구조로 되어 있습니다.

 

삽입(enqueue) : 큐에 데이터를 넣는 작업 , 복잡도는 O(1)

삭제(dequeue) : 데이터를 꺼내는 작업 , front를 꺼낸 다음 두번째 이후의 요소를 맨앞으로 옮깁니다.

                      복잡도는 O(n) -> 효율이 떨어짐

 

데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 합니다.

 

★ 디큐를 하면서 두번째 이후의 모든 요소를 하나씩 앞쪽으로 옮겨야(shift) 합니다.

 

배열로 큐 구현하기

 

자료구조 - 링 버퍼(ring buffer)

앞서 본 배열로 큐를 구현하면서 디큐를 할 때 두번째 이후의 모든 요소를 하나씩 앞쪽으로 옮기면서 

발생한 요소이동문제가 있었습니다.

링 버퍼를 사용한다면 이문제를 해결할 수 있습니다. 처리의 복잡도는 O(1)입니다. (배열 - O(n))

 

링 버퍼는 배열 요소를 앞쪽으로 옮기지 않습니다. 

배열의 처음과 끝이 연결된 자료구조 입니다.

여기서는 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가

프론트(front)와 리어(rear)입니다.

 

5개의 데이터(35, 56, 24, 68, 19)가 차례대로 que[5], que[6], que[7], que[0], que[1] 에 저장됩니다.

프론트 값은 7이고 리어 값은 2 입니다.

 

다음으로 인큐를 하게 되면 que[2](리어가 가르키고 있는 위치) 에 저장하고 리어값을 1만큼 증가합니다.

디큐를 하게 되면 프런트 요소(que[5])의 값 35를 빼고 프런트 값을 1만큼 증가합니다.

 

 

링 버퍼로 큐 구현하기

검색 메소드 indexOf 에서 스캔의 시작은 배열의 첫 요소가 아니라, 큐의 첫요소 프런트 입니다.

따라서 찾는 인덱스 계산이 (i + front) % max 로 복잡합니다.

 

실행 코드

---

이상으로 queue에 대해 알아보았습니다.