자료구조(11) - 원형 큐 ( Queue )

 - 원형 큐( Queue )

            : 책의 설명보다는 이해한바로 전달하도록 하겠다. 책의 표현이 너무 복잡해서 한참을 읽어보았다.

            : 전체 크기가 5인 큐( Queue )가 있다.

            : 우선 원소 5개를 enQueue 했다고 하자, rear는 4가 되었다.

               -> 4개의 원소를 deQueue를 하자.

               -> rear = 4, front = 3이 되었다. 

               -> 실제 들어간 원소는 1개, 

               -> rear는 최대치까지 올랐기때문에 더이상 들어갈 자리가 없다.

 

               -> 입/출력이 서로 다르며, 유기적인 변화가 없기때문에 1회용 저장공간이 된 것이다.

               -> 이를 잘못 인식된 포화상태라고 표현하며 이름 해결하기위해 원형 큐( Queue )를 구성하게된다.

 

까지 확인했었다.

            : 원형 큐를 문자화하려면 %연산자가 필요하다.

              상기의 내용으로 인해 인덱스가 반복될 수 있어야 하기 때문이다.

            ex) 길이가 4인 큐( Queue )를 생각해보자. 

                         : 첫번째 삽입이 이루어지면 rear는 -1 -> 0 이 되고, 0번째 칸에 삽입이 된다. 

                           두번째 삽입이 이루어지면 rear는  0 -> 1 이 되고, 1번째 칸에 삽입이 된다. 

                           세번째 삽입이 이루어지면 rear는  1 -> 2 이 되고, 2번째 칸에 삽입이 된다.

                           네번째 삽입이 이루어지면 rear는  2 -> 3 이 되고, 3번째 칸에 삽입이 된다.

                           

                           이렇게 모든 칸이 다 찼고, 삭제부분은 우선 생각하지 않고 흐름을 보도록 하자.

                           삭제가 되어서 빈칸이 있어 더 입력하려 한다고 가정했을때

 

                           다섯번째 삽입이 이루어지면 rear는 3->0이 되고, 0번째 칸에 삽입이 된다.

                           이런 흐름이 연이어지려면 rear%4 를 해주고 rear++; 처리가 되면 된다.

                           더불어 front도 같은 방식이기 때문에 원형 큐( Queue )에서는

                           큐를 얼마든지 재사용할 수 있게 된다.

 

                           코드로 만들어보는 것은 먼저 일반 큐 ( Queue  ) 의 문제가 해결되면 진행해보도록 하겠다.