728x90
원형 큐
-
[자료구조] 배열로 구현한 원형 큐(Circular Queue) - C/C++자료구조 2017. 7. 23. 18:19
- 선형구조로 자료를 차례대로 저장하고, 가장 먼저 들어간 자료가 가장 먼저 나오는 FIFO(First In First Out, 선입선출)의 특성을 지닌다. - 자료 반환은 큐의 제일 앞(front)에서만 가능하고 자료 추가는 큐의 제일 끝(rear)에서만 가능하다. --> 선형 큐의 단점 : dequeue가 실행되고 생긴 front 앞의 빈 노드가 있어도, rear가 이동할 오른쪽에 빈 노드가 없으면 overflow현상이 발생한다. = 선형 큐는 메모리 비효율적이다. --> 선형 큐의 대안으로 원형 큐가 제시되었다. - rear의 오른쪽과 front의 왼쪽을 (가상적으로) 연결시켜, rear의 오른쪽으로 front의 왼쪽 빈 노드를 사용할 수 있도록한다. - rear 노드 이동에 mod 연산자를 이용한..