----------------------------------------------------
----------------------------------------------------
이전에 했던
일자 선형 큐는
재사용이 불가능하여 문제가 조금 있습니다.
그래서 만약 선형큐를 재사용 하려면
다시 front나 rear값을 초기화 해주어야 하는데
원형큐는 재사용이 가능해서 그럴 필요가 없습니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
'
----------------------------------------------------
----------------------------------------------------
원형큐도 마찬가지로 배열로 만드는데
사실 메모리상에서 구조는 선형이지만
원형처럼 그려서 보기쉽게 표현해놓았습니다.
길이가 8인 배열을 원형형태로 표현한것입니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
이렇게
인큐 7번 하고
디큐 7번 하고
또
인큐 7번 하고
디큐 7번 할수 있어야 합니다.
왜냐하면
원형큐는 재사용이 가능한 큐 이기 때문입니다.
원처럼 돌면서 넣고 빼고를 반복하기 때문입니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
큐에 데이터를 넣는
인큐 연산을 살펴보겠습니다.
----------------------------------------------------
인큐 영상
F와 R은 0부터 시작해서
마찬가지로 인큐하면
R이 증가해서 데이터를 집어넣습니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
만약 배열을 꽉 채우게 된다면
F와 R이 같아져서
처음에 비어있는 상태와 모양이 같아지게 됩니다.
그러면
두 상태를 구분할수가 없으므로
R이 F보다 한칸 뒤에있는 상태
한 개 덜채운 상태를 꽉찬 상태로 정의해줍니다
----------------------------------------------------
그래서 지금 이 상태가
원형큐에서 데이터가 꽉찬 상태인데
꽉찬것을 점검하는 포화점검식이
F와 R+1을 8로 나눈 나머지가 같은가?
입니다.
우선 이 포화점검식은
지금 상태에선 잘 동작합니다.
----------------------------------------------------
F에 0을 넣고
R에 7을 넣으면
지금 현재 상태가
포화상태, 즉 꽉찬상태라는것이 점검이 잘 됩니다.
----------------------------------------------------
포화 점검식이 왜
F와 R+1을 8로 나눈 나머지가 같은가?
인가에 대한 설명은
이것이 원형큐 이기 때문입니다.
F와 R은 계속 위치가 변하고
꽉 찼을때의
F와 R의 위치도 계속 변하기 때문에
이식은
R이 F한칸 뒤에 있는
즉 한 개 덜채운 상태를 표현한 식입니다.
그렇다면
이 식이 과연
모든 경우에 대해서 적용이 되는지 살펴보겠습니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
그 다음 포화 점검식
F가 R+1을 8로 나눈 나머지와 같은가?를
사용해보면
----------------------------------------------------
----------------------------------------------------
그래서
최종적으로 구현된
원형큐의 인큐 함수는 다음과 같습니다.
----------------------------------------------------
첫번째는
포화상태 점검식
F와 R+1을 큐의 길이로 나눈 나머지가 같으면
더 이상 인큐 할 수 없습니다.
----------------------------------------------------
두번째는
포화가 아닐 경우
R이 원형처럼 돌게
R을 1증가하여
큐의 길이로 나눈 나머지를 저장하여
R위치의 배열에 데이터를 저장합니다.
----------------------------------------------------
그 다음 디큐 함수에 대해서 살펴보겠습니다.
디큐 함수는
큐에서 데이터를 빼내는 함수인데
----------------------------------------------------
디큐 영상
디큐 하면
마찬가지로
FRONT인
F가 증가해서 데이터를 뽑아냅니다.
----------------------------------------------------
디큐 하면
FRONT인
F가 증가해서 데이터를 뽑아내고
이제 데이터를 다 뽑아내면
F와 R이 같아져서
더 이상 데이터를 뽑아낼 수 없습니다.
그래서 공백 상태 점검식은
F와 R이 같으면?
입니다.
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
----------------------------------------------------
F와 R이 둘다 2이고
결국 F와 R이 같아져
더 이상 디큐 할 수 없게 됩니다.
즉, 인큐한만큼 디큐하면
F와 R이 같아져 더 이상
디큐 할수 없게 됩니다.
----------------------------------------------------
그래서 공백 상태 점검식은
F와 R이 같으면?
이 됩니다.
----------------------------------------------------
그래서
원형큐의 디큐 함수는
다음과 같은 모양이 됩니다.
----------------------------------------------------
첫번째는
공백상태 점검식
F와 r이 같아지면 데이터가 없는 상태입니다.
그래서 캔트 디큐를 출력해줍니다.
----------------------------------------------------
두번째는
데이터를 빼는 작업인데
F의 위치가 원처럼 돌게 만들어주고
디큐할 데이터를 뽑아내고
0을 넣어 데이터를 제거합니다.
----------------------------------------------------
----------------------------------------------------
인큐 디큐
인큐 디큐
두번 해도
잘 동작하는
즉, 재사용이 가능한
원형큐의 특성을 잘 만족했다고 볼 수 있습니다.
----------------------------------------------------
----------------------------------------------------
공백상태를 점검하는 식과
포화상태를 점검하는 식이 다른것이
가장 중요합니다.
----------------------------------------------------
그래서 원형큐는
원처럼 돌게 만드는 것을 구현할수 있도록
나머지 연산자를 사용하는것이 매우 중요합니다.
----------------------------------------------------
'자료구조' 카테고리의 다른 글
| [자료구조] 7장. 연결 리스트 스택 (전역변수) (Stack Linked List) (0) | 2020.04.10 |
|---|---|
| [자료구조] 6장. 연결 리스트 설명과 구현 (Linked List) (0) | 2020.04.10 |
| [자료구조] 4장. 선형 큐(Queue) 구현 (배열) (0) | 2020.04.09 |
| [자료구조] 3장. 큐(Queue) 설명 (0) | 2020.04.09 |
| [자료구조] 2장. 배열 스택(Stack) 구현 (0) | 2020.04.09 |
