3.4 큐(Queue)

이번에는 큐를 알아보기로 해요.

큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 REAR, 꺼낼 위치 정보를 FRONT라고 말해요.

먼저 간단하게 보관하는 큐를 만들어 보기로 해요.

생성자 메서드에서는 자료를 보관할 버퍼의 크기를 입력 인자로 받게 구현하세요.

큐 초기화에 front와 rear는 0

소멸자에서는 내부에서 동적으로 생성한 버퍼를 해제해야겠죠.

자료를 rear 위치에 보관하는 Put 메서드를 구현합시다.

큐는 스택과 달리 꺼내는 쪽과 보관하는 쪽이 다릅니다. 이러한 이유로 보관할 위치를 단순히 증가하는 형태로 작성하면 앞쪽에 보관한 것을 꺼내도 빈 공간을 사용할 수 없는 문제가 발생합니다. 이를 개선하는 방법은 몇 가지가 있는데 그 중에 가장 많이 사용하는 것이 원형 큐입니다.

원형 큐에서는 rear와 front를 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동합니다. 여기에서는 이를 수행하는 멤버 메서드 Next를 별도로 구현하기로 할게요.

원형 큐의 동작

front 위치에 보관한 자료를 꺼내는 Put 메서드를 구현합시다. rear와 마찬가지로 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동합니다.

비었는지 확인하는 IsEmpty 메서드를 제공합시다.

꽉 찼는지 확인한느 IsFull 메서드를 제공합시다. 원형 큐에서 버퍼에 모든 자료를 보관하면 front와 rear가 같아집니다. 보통 rear의 다음 위치가 front가 같으면 꽉 찬 것으로 처리합니다. 따라서 버퍼를 하나 사용하지 않는 것이죠. 이를 완충 지대라고 말해요.원형 큐의 완충지대

큐 내부에서 사용할 다음 인덱스를 계산하는 Next 메서드를 구현합시다. front나 rear는 0, 1, 2, …, size-1, 0, 1, 2, …. 형태로 이동해야 합니다. 이를 위해 1을 더한 값을 버퍼 크기로 나머지 연산하세요.

간단히 테스트하는 코드를 작성합시다.

▷ 실행 결과