[자바 Do It! 알고리즘]Chapter04 스택과 큐(큐)

[큐]

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

2. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택과 다릅니다.

3. 큐에 데이터를 넣는 작업을 인큐(enqueue) 라고 하고

데이터를 꺼내는 작업을 디큐(dequeue) 라고 하고

데이터를 꺼내는 쪽을 프런트(front)

데이터를 넣는 쪽을 리어(rear) 라고 합니다.

4. 큐를 배열로 디큐흐면 que[0]에 저장된 값을 꺼낸 다음 두 번째 이후의 요소를 모두 맨앞으로 옮겨야 합니다. 이 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어집니다. 그래서 링 버퍼로 만듭니다.

​

[링 버퍼(ring buffer)로 큐 만들기]

1. 배열의 처음이 끝과 연결되어있다고 보는 자료구조입니다.

2. 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트(front)와 리어(rear) 입니다.

※ 여기서 프런트와 리어는 논리적인 데이터 순서이므로 물리적 요소가 아닙니다.

프런트 : 맨 처음 요소의 인덱스

리어 : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

☞ 큐로 사용할 배열(que)

인큐하는 데이터를 저장하기 위한 큐 본체용 배열입니다.

필드 que 는 실제로는 배열 본체가 아니라 본체를 참조하는 배열 변수입니다.

배열 본체는 생성자로 생성합니다.

​

☞ 큐의 최대 용량 (max)

큐의 최대 용량을 저장하는 필드로, 이 값은 배열 que에 저장할 수 있는 최대 요소의 개수와 같습니다.

​

☞ 프런트(front)

인큐하는 데이터 가운데 첫 번째 요소의 인덱스를 저장하는 필드입니다.

​

☞ 리어(rear)

인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드입니다.

다음 인큐 시에 데이터가 저장될 요소의 인덱스를 미리 준비해 두는 것이라고 생각하면 됩니다.

​

☞ 현재 데이터 수 (num)

큐에 쌓아 놓은 데이터 수를 나타내는 필드입니다.

front 와 rear의 값이 같은 경우 큐가 비어 있는지, 가득 찼는지 구별할 수 없는 상황을 피하기 위해 이 변수가 필요합니다.

큐가 비어 있을 때 num은 0이고, 가득 찼을 때는 num과 max의 값이 같습니다.

​

☞ 생성자 IntQueue

생성 시 큐는 비어 있기 때문에 num, front, rear 값을 모두 0으로 합니다.

매개변수 capacity로 전달받은 '큐의 용량'을 필드 max에 복사하고

요솟수가 max 인 배열 que의 본체를 생성합니다.

​

☞ 인큐 메서드 enque

인큐에 성공하면 인큐한 겂을 그대로 반환합니다.

큐가 가득차서 인큐할 수 없으면 예외를 던집니다.

rear 값을 1만큼 증가했을 때 큐의 최대 용량의 값인 max와 같아질 경우 rear를 배열의 처음인 0으로 변경해야 합니다.

​

☞ 디큐 메서드 deque

큐가 비어 있어 디큐할 수 없으면 예외를 던집니다.

1만큼 증가한 front 값이 큐의 용량인 max와 같아지면 front 같을 배열의 처음인 0으로 변경해야 합니다.

​

☞ 검색 메서드 indexOf

스캔의 시작 배열의 첫 요소가 아니라 큐의 첫 요소(프런트) 입니다.

그래서 스캔할 때 주목하는 인덱스 idx의 계산이 (i + front) % max로 복잡합니다.