원형큐 알고리즘 질문입니다. 같이 고민해주세요 !
하림
일반적인 원형큐는 front = 항상 큐의 첫 번째 요소의 하나 앞
rear = 마지막 요소
인데. 이것을
front = 항상 큐의 첫 번째 요소
rear = 마지막 요소
이렇게 함으로써 그리고 front == rear : 공백 이라는 조건을 만족하고,
하나의 저장 공간이 비워져 있어야 하는 원형 큐를
비워져 있는 공간이 없이 공간을 활용할 수 있게
알고리즘을 구현해야 하는데, carry 함수를 쓰자니 하나 앞으로 나가게 되서 첫번째 요소를 표시 하라는 조건에
부합히질 않습니다.
질문을 좀 더 확실히 하기 위해 아래가 그림입니다..
http://img2.ruliweb.daum.net/img/img_link7/848/847405_1.jpg
이것이 정상적인 상태의 원형 큐 이며,
아래가
http://img2.ruliweb.daum.net/img/img_link7/848/847405_2.jpg
질문하는 큐 입니다.
하나의 빈 공간도 없게, 리어는 꽉 차고, 프론트는 그 꽉 찬 것의 처음을 가리키는...
스택과 malloc 을 섞어쓰면 가능할까요?
어떤알고리즘 구현 방법이 있을까요?
-
하늘이
rear의 Next 노드를 front로 두면 될거 같군요.
대가리(...)가 없어짐에 따라 따로 필요한 정보는 클래스로 구현할 경우 멤버 변수에, 함수 베이스로 구현할 경우 각 노드의 멤버 변수에 넣어서 관리하시면 될겁니다.
대가리를 쓰는건 얘가 대가리다!라는 것을 편하게 알기위해서가 아닐까 싶네요.
제가 학생때 봤던 알고리즘중에 대가리 없는게 많았어서 -_-;;