[게임자료구조] 원형 큐

참조 사이트 : http://blog.daum.net/7icdi7/28

초기 공백 상태 : front = rear = 0
사용조건 : 공백 상태와 포화 상태를 구분을 쉽게 하기 위해서 front가 있는 자리
초기 공백 원형 큐 생성 알고리즘

front 와 rear 구간 이외의 값은 쓰레기값으로 취급하여 front,rear 값 변경시 별도의 공간 초기화는 필요 없다.



----------------------------------
순차 자료구조의 문제점
삽입연산이나 삭제연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요
 - 원소들의 이동 작업으로 인한 오버헤드는 원소의 개수가 많고 삽입, 삭제 연산이 많이 발생하는 경우에 성능상의 문제 발생

연결 자료구조(Linked Data Structure)
자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조
 - 각 원소에 저자오디어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식
   - 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음
 - 여러개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현
   - 크기 변경이 유연하고 더 효율적으로 메모리를 사용

연결 리스트
 - 리스트를 연결 자료구조로 표현한 구조
 - 연결하는 방식에 따라 단순 연결 리스트오 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

연결리스트의 노드(node)
 - 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조
 - <Data, Link(주소)>의 형태로 이루어짐

선형 리스트와 연결 리스트의 비교
리스트 이름 - 연결 리스트의 시작을 가리키는 포인터 변수


-----------------
자유 공간 리스트
 자유공간 리스트에서의 노드 할당 과정
  - 자유공간 리스트 free에서 노드를 할당할 때는 항상 첫 번째 노드 할당