2024. 7. 8. 15:16ㆍ자료구조
큐 - 선형 list에서 자료의 삽입과 제거를 각각 다른 쪽 끝에서 이루어지도록 제한한 자료구조
가장 먼저 입력된 자료가 가장 먼저 출력되는 방식이다. (FIFO)
● 스택과는 다르게 큐는 2개의 포인터를 가지고 있다. (Front,Rear)
● 가장 먼저 입력된 자료의 위치는 Front의 다음위치에 있다.
● 가장 나중에 입력된 자료의 위치는 Rear의 위치에 있다.
Queue를 배열을 이용하여 간단하게 구현한 결과 작업이나 데이터를 순차적으로 처리해야 할 때 큐를 사용하면 스택보다 효율적인 방법이다라는 생각이 들었다.
하지만 Front와 Rear의 값이 모두 증가만 하기 때문에 공간이 낭비된다. 이 코드의 실행 결과는 2,3,4,underflows가 나타난다. 4를 입력하기전에 1의 공간이 비었음에도 불구하고 1의 공간을 사용하지 않기 때문이다.
이러한 단점은 환형 큐 (circular queue)를 통해서 해결할 수 있다.
● 입력이 들어오면 순서대로 queue에 저장하는 것은 기존 queue와 같음
● 출력으로 인하여 빈 공간이 생긴 경우, 새로운 입력을 빈 공간에 저장함
● Rear이 최대 queue index에 도달 한 경우 다시 0 index로 이동
● 다만, Rear이 가리키는 index가 빈 공간인지 확인하는 것이 중요함.
환형 큐 구현
일단 max_size는 큐 구현할 때와 동일하게 4로 설정했다.
여기서는 Front와 Rear말고 check와 result변수가 추가되었다. check함수는 Queue에 값이 모두 채워져있지 않지만 Full이라고 오인하는 것을 방지하기 위해
Queue에 값이 모두 비워져있지 않지만 Empty라고 오인하는 것을 방지하기 위해
추가하였다.
result 변수는 DeQueue 함수를 선언할 시 값이 빠져나가면서 삭제가 되야하기 때문에 삭제되어야 하는 값을 미리 저장해놓고 값을 삭제시키기 위해 추가햐였다.
Queue의 모든 값이 비워져있는지 채워져있는지 확인하는 checkFull,checkEmpty함수를 추가하였다. (위에 예시그림을 방지하기 위해)
기존의 Full과 Empty 코드도 수정하였다. 만약 Rear의 값이 배열의 끝에 도달했을 경우 Rear를 0으로 보내서 처음부터 값을 채운다.
EnQueue는 기존과 동일하지만 DeQueue는 값을 출력 후 삭제시켜야하기 때문에 그 부분을 추가하였다.
코드를 수정한 후 확인한 결과
1,2,3,4가 차례대로 추가된 후 1을 삭제하고 삭제한 1부분에 5를 추가한 후 2와 3을 삭제한 것을 확인할 수 있다.
간단하게 설명하면 Rear는 여기까지 저장했다라는 뜻이고, Front는 여기까지 삭제했다라는 뜻이다.