열혈 자료구조 - 7-2 큐의 배열 기반 구현(1)

큐의 구현 논리

- 큐의 가장 앞의 데이터의 인덱스를 가르키는 front, 가장 뒤를 가르키는 Rear를 가지고 있음

- enqueue시 rear를 한칸 뒤로 옮기고 데이터를 넣고 dequeue시 front의 데이터를 꺼낸 후 한칸 뒤로 옮김

- 배열은 크기가 정해져 있기 때문에 Rear가 배열의 끝까지 이동했다면 다시 0번 인덱스로 가야함

    -> 그렇지 않으면 나머지 배열 공간이 낭비

    -> 이런 방식을 원형 큐라고 함

    -> 계속 순환하는 구조

- 원형 큐의 단순한 연산의 문제점

    -> enqueue, dequeue 시 Front와 Rear는 같은 방향으로 순환

    -> 데이터가 하나 있을 때 Front와 Rear의 위치가 같다면 주어진 공간을 모두 사용하겠다는 의미

    -> 3번째 그림의 상황에서 dequeue시에 4번째 그림처럼 Front가 Rear를 넘는 상황이 발생

    -> 이렇게 되면 큐가 다 채워졌는지 확인하기 위해 Front와 Rear의 관계를 비교하는데 다 채워졌을 때와 다 비워졌을 때가 동일한 관계를 가지게 되면서 모호해짐

- 문제의 해결

    -> 데이터가 모두 비어있을 때 Front와 Rear의 위치를 같게 함

    -> 4번째의 경우와 같은 Front와 Rear의 관계일 때 꽉 찼다고 생각

    -> 이러면 emtpy와 full을 구분할 수 있음

    -> 메모리 공간 하나를 희생해서 두 상태를 구분할 수 있음

    -> 저 위치가 꼭 고정이 아니고 dequeue연산으로 Front가 이동되면 enqueue연산으로 Rear을 이동시킬 수 있음 (= 무조건 한 칸을 비워야 함)