[자료구조] 큐(Queue)(7-2) 큐의 배열 기반 구현

큐의 구현에 대한 논리

큐의 머리를 F 꼬리를 R이라고 생각하자 !
enqueue(데이터추가)연산 시 F는 그대로 있는 채 꼬리인 R이 한칸씩 뒤로가리키면서 연산이 진행된다.
그렇다면 ! dequeue연산시에는 이와는 반대로 F를 참조하여 머리를 삭제해 나가는 방식이다

Dequeue연산

에는 일반적이지 않은 방식과 일반적인 방식이 있다.

• 일반적이지 않은 방식
  F가 가리키는 부분을 삭제하며 반환할 데이터를 배열의 맨 앞부분에 위치시키는 방법으로 가장 보편적인 배열의 삭제방법이다.
  하지만 이 방식을 사용할 경우 연산의 대상이 항상 맨 앞에 위치하므로 F가 불필요하다, 그리고 이 방식은 연산시마다 저장된 데이터를 한 칸 씩 이동시켜야하는 단점이 있다.

• 일반적인 방식
  F에 있는 데이터를 삭제하는 것이 아니라 F를 이동시킨다.
  이렇게 한다면 dequeue의 과정에서 데이터의 이동이 필요치 않다.
  그저 F가 가리키는 위치만 한 칸 오른쪽으로 옮기면 되기때문이다 !
  하지만.. 이 방법도 완전치 않은데 바로 ..더 이상 R을 오른쪽으로 이동시킬 수 없을때이다!

그렇다면... 이것을 해결할 방법은 바로!!!!
R을 맨 앞으로 이동시키면 되는것이다 !
왜냐하면 충분히 앞부분이 삭제가 이루어져있어 문제가 발생한것이니 배열의 앞부분은 비었다는 말이다 !
그리하여 R을 배열의 앞부분으로 이동시키면 추가로 Enqueue연산을 진행 할 수 있다 !

이리하여!!!!!
이러한 방식으로 동작하는 배열 기반의 큐를 가리켜

원형 큐 라고 한다 !!!