Page 144 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

37, 53)의 데이터가 들어가 있는 모습입니다. 배열 이름을 que라 할 경우 que[0]부터 que[3]

까지의 데이터가 저장되어 있습니다. 인덱스가 0인 요소를 큐의 맨 앞(front)이라 합니다.

a b c
24를 인큐 19를 디큐
맨 앞(front)
０ 19 19 22
１ 22 22 37
２ 37 37 53
３ 53 53 24
４ 24
５
６
７
맨 뒤(rear)
디큐를 하면서 두 번째 이후의 모든 요
소를 하나씩 앞쪽으로 옮겨야(shift)
합니다.

[그림 4-8] 배열에 의한 큐의 구현 예

위 그림을 보면서 인큐와 디큐에 대해서 살펴보겠습니다. 24를 인큐하고 19를 디큐합니다.

1. 24 인큐
먼저 데이터 24를 인큐합니다. 그림의 b 처럼 리어(rear)의 데이터가 저장된 que[3]의 다음
요소 que[4]에 24를 저장합니다. 이 처리의 복잡도는 O(1)이고 적은 비용으로 구현할 수 있
습니다.

2. 19 디큐
이번에는 19를 디큐합니다. 그림의 c 처럼 que[0]에 저장된 19를 꺼낸 다음 두 번째 이후의
요소를 모두 맨 앞으로 옮깁니다. 이 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때마다 이런

처리를 하게 되면 효율이 떨어집니다.

연습 Q3 이 페이지의 아이디어를 기반으로 큐를 구현하는 프로그램을 만드세요. 큐를 관리하는 구
문제 조체는 아래의 멤버를 갖는 ArrayIntQueue를 사용하세요.

typedef struct {
int max; /* 큐의 용량 */
int num; /* 현재 데이터 수 */
int *que; /* 큐의 첫 요소에 대한 포인터 */
} ArrayIntQueue;

실습 4-5에 사용된 함수를 참고하여 프로그램을 완성하세요.

144 C 알고리즘