5.3 큐

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

큐는 순차적으로 자료를 보관하고 가장 최근에 보관한 자료를 꺼내는(FIFO, First In First Out) 버퍼예요.

 

여기에서는 버퍼의 크기가 정적인 배열로 정의하는 것을 먼저 구현할 거예요.

그리고 난 후에 이미 작성한 연결리스트를 이용하는 큐를 만들기로 해요.

 

배열로 큐를 정의할 때 자료를 보관하는 버퍼 외에 자료를 보관할 위치와 꺼낼 인덱스를 기억하고 있어요.

보관할 위치는 맨 뒤에 보관해서 rear라고 부르고 꺼낼 위치는 맨 앞이어서 front라 불러요.

그리고 큐에 자료를 보관하는 행위를 EnQueue 혹은 Put이라 불러요.

큐에서 자료를 꺼내는 행위는 DeDueue 혹은 Get이라 불러요.

그리고 배열로 큐를 구현할 때는 큐가 비었는지 혹은 꽉 찼는지 확인할 수 있는 기능을 제공하죠.

 

다음은 배열로 구현한 원형 큐예요.

원형 큐는 맨 뒤에 보관한 다음 다시 앞에 보관하는 큐를 말해요.

이와 같이 보관하면 큐가 꽉 찼을 때와 비었을 때 구분하지 못하는 문제가 있어요.

이를 해결하는 방법 중에 rear 다음이 front일 때 꽉 찬 것으로 취급하는 방법이 있어요.

여기에서는 이 방법을 사용하여 구현하였어요.

이 외에도 다양한 방법으로 큐를 구현할 수 있어요.

다음 글에서는 이미 앞에서 만들었던 연결리스트를 이용하는 큐를 설계하고 구현해 볼 거예요.


5.3.1 큐 설계

5.3.2 큐 구현

5.3.3 큐 테스트

5.3.4 큐 소스 코드