[C 언어] Array Circular Queue 배열 원형 큐 구현

Array Circular Queue 배열 원형 큐

왜 원형 큐 (Circular Queue) 를 사용할까?

1. 기존의 배열 큐 (Array Queue) Memory Overflow 문제를 해결하기 위해서이다.

- 배열의 Front 에 빈 노드가 있다고 할지라도, Front에 새로운 노드를 추가하려고 할때 Memory Overflow가 발생한다. 배열 큐의 특성상 배열의 크기는 이미 정해져있기 때문이다.

- 배열을 이동시키는 방법으로 이 문제를 해결할 수 있다. 하지만 배열을 이동하는데 O(N)의 시간 복잡도가 필요하다. 따라서 배열의 크기가 커질수록 이 문제는 효율적이지 않은 방법이 된다.

- 이 문제를 위한 효과적인 방법은 원형 큐(Circular Queue)를 이용하는것이다.

처럼 dequeue를 실행해서 Front에 빈 노드가 있다고 하더라도 새로운 노드를 추가하는것이 불가능하다. Front에 새로운 노드를 삽입하기 위해서는 기존의 A, B, C 노드의 위치를 1, 2, 3 에서 1 칸씩 이동시켜 0, 1, 2로 변경해야 한다. 하지만 원형 큐는 Front와 Rear을 연결시키기 때문에 이 과정이 필요하지 않다.

원형 큐(Circular Queue)의 특징

1. 배열의 Front와 Rear를 연결한다.

- Front와 Rear를 연결하기 위해서, mod 연산자를 사용한다.

- rear = (rear + 1) % array size

기존의 배열에서 Dequeue(A)로 인덱스 0에서 A가 제거되며 이후 Front는 인덱스 1에 있는 B로 변경된다. 그 다음 Enqueue(E)를 하면 E는 빈 노드가 있는 인덱스 0에 삽입되며 E는 새로운 Rear가 된다.

원형 큐(Circular Queue) 구현

Github