원형 큐의 이해
오늘은 원형 큐에 대해 공부한 내용을 정리해 볼것이다
원형 큐는 저번글에서 큐에 더이상 데이터를 추가할 공간이 부족한 상황에서 앞서
사용하지 않는 메모리 공간을 활용하는 방법이다
그림은 일반적인 형태의 큐이다 하지만 우리가 이것을 원형의 순환되는 구조로서 생각해 본다면
다음과 그림과 같이 확인할수 있을거다 그렇다면 어떻게 원형 큐가 연산되는지 정리해보자
원형 큐의 연산
그림에서 데이터가 하나 추가되니 R이 오른쪽으로 한칸 이동했다
(이해를 돕기위해 오른쪽 이동으로 일관 통일 했다)
그렇다면 반대로 데이터를 삭제하면 어떻게 될까?
F가 오른쪽 한칸 이동하고 "A"가 삭제 된것을 확인할수 있다
원형큐의 기본적인 동작을 알아보았다
하지만 이러한 원형 큐도 한가지 문제점이 있다
비어있는 큐와 꽉찬큐를 컴퓨터가 구분하기어렵다
그림처럼 원형 큐에 데이터를 게속 추가하거나 계속 삭제했다면
다음 그림처럼 포인터 변수들이 존재할텐데 컴퓨터로서는 이둘의 포인터 위치관계가 같기 때문
(F,R이 1칸 차이나는 상황)
구분하기가 어렵다 그렇다면 이러한 문제점을 개선하기 위해서는 어떻게 해야할까?
개선된 원형 큐
개선된 원형 큐는 딱히 거창한게 없다
단순히 1번째 배열에는 아무런 값을 넣지 않는것이다
이로 인해 F는 오직 삭제의 역활만을 담당 할수 있게 되어서
구분이 용이해 짐을 알수있다
단순연결 리스트를 공부할때 더미노드를 만드는것과 굉장히 유사한 원리라고생각한다
방구석여포