[ch 07-2] 큐의 배열 기반 구현_1(데이터 저장/반환, 원형 큐 개념)

[enqueue의 연산방식]

※ F(Front): 큐의 앞(출구)을 가리키는 포인터 변수

※ R(Rear): 큐의 뒤(입구)를 가리키는 포인터 변수

- enqueue 연산 시 R이 배열의 다음 칸을 가리키고 그 자리에 새로 입력된 데이터를 저장

- 첫 데이터가 저장될 때는 F와 R이 같은 위치를 가리킴

[dequeue]

■ 보편적인 배열의 삭제방식

- dequeue 연산 시 반환할 데이터를 배열의 맨 앞부분으로 이동 시키는 방식

- F의 위치는 고정된 채로 데이터가 이동하기 때문에 F가 불필요

- dequeue 연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 존재 ★

■ 일반적인 방식

- F를 R처럼 한 칸씩 오른쪽으로 이동하면서 데이터를 삭제

- 데이터의 위치를 옮길 필요없음

■ 문제가 되는 상황

- 배열의 앞 자리의 데이터가 삭제되고 다시 데이터가 추가됨으로써 뒤 끝까지 채워진 상황

- 때문에 R은 더 이상 오른쪽 이동시킬 수 없음

- 데이터를 더 넣을 수 있는 공간이 존재함에도 불구하고 더 이상 데이터를 채울 수 없는 문제 발생

- 해결 방법으로 F, R은 배열의 끝에 도달한 상태에서 데이터의 추가/삭제 처리가 발생되면 배열의 앞으로 이동시켜서 무한하게 

  회전할 수 있도록 함(=원형 큐) ★

[원형 큐(Circular Queue)]

- 원형 큐를 논리적인 구조로 그려진 형태

■ 원형 큐의 enqueue 연산

■ 원형 큐의 dequeue 연산

■ FULL 상태와 Empty 상태

- FULL: 3개의 데이터가 채워진 상태에서 한번 더 enqueue 연산 처리가 되어 배열에 데이터가 전부 채워진 상태

- Empty: 3개의 데이터가 채워진 상태에서 다시 3번의 dequeue 연산 처리가 되어 배열에 데이터가 전부 비워진 상태

- 두 경우 모두 F가 R보다 한 칸 앞서 있는 상태로 있다는 것이 공통점

- 하지만 그렇기 때문에 F와 R의 위치 갖고만으로는 FULL 상태와 Empty 상태를 구분할 수 없음

- 해결 방법으로 FULL 상태를 '배열의 길이가 N개일 때 데이터가 N-1개가 채워진 상태를 FULL 상태로 간주'하는 것으로 처리

  ※ 저장 공간 하나를 낭비하는 문제가 있지만, 핵심 문제가 해결됨으로써 잃는 것보다 얻는 것이 많은 셈

■ 변경된 FULL과 Empty 상태

■ 원형 큐의 특성

- 원형 큐가 텅빈 상태: F와 R이 동일한 위치를 가리킴

- 원형 큐가 꽉찬 상태: R+1의 가리키는 위치와 F의 가리키는 위치가 같은 상태