C언어 원형 큐 (Circular Queue)
선수학습(1개)
요약
C언어 원형 큐의 개념, front/rear 포인터, 모듈러 연산을 이용한 순환 구조를 알아봅니다. 정보처리기사 실기에 출제된 원형 큐 문제를 풀기 위한 핵심 개념을 정리합니다.
원형 큐 핵심 정리
| 개념 | 설명 | 예시 |
|---|---|---|
| 원형 큐 | 배열의 끝과 처음이 연결된 큐 | SIZE=3이면 [0], [1], [2] 사용 |
| front | 맨 앞 데이터 위치 | 다음에 나갈 데이터 |
| rear | 다음 빈 칸 위치 | 새 데이터가 들어갈 자리 |
| 모듈러 연산 | 인덱스 순환을 위한 나머지 연산 | (rear + 1) % 3 |
원형 큐란?
원형 큐(Circular Queue) 는 배열의 끝과 처음을 연결하여 원형으로 동작하는 큐입니다.
선형 큐는 데이터를 삭제하면 앞쪽 공간이 비어도 재사용할 수 없습니다. 원형 큐는 이 문제를 해결합니다.
front와 rear 포인터
원형 큐는 두 개의 포인터로 데이터 위치를 관리합니다. 줄 서기로 비유하면 이해하기 쉽습니다.
| 포인터 | 역할 | 비유 |
|---|---|---|
front | 맨 앞 데이터 위치 | 다음에 서비스 받을 손님 |
rear | 다음 빈 칸 위치 | 새 손님이 줄 설 자리 |
typedef를 사용하면 구조체에 별명을 붙여서 Queue라는 짧은 이름으로 쓸 수 있습니다.
{{0}, 0, 0}에서 안쪽 {0}은 배열 a를 모두 0으로 초기화하고, 나머지 0, 0은 front와 rear를 각각 0으로 설정합니다.
어떻게 원형으로 이어지나?
실제 배열은 일렬이지만, 인덱스가 끝에 도달하면 처음으로 돌아가도록 처리합니다.
이 "돌아가기"를 구현하는 것이 모듈러 연산 % SIZE 입니다. 다음 섹션에서 자세히 설명합니다.
모듈러 연산 (% SIZE)
원형 큐의 핵심은 모듈러(나머지) 연산입니다. 나머지 연산자 %는 나눗셈의 나머지를 구합니다. 인덱스가 배열 끝에 도달하면 처음으로 돌아갑니다.
#define SIZE 3은 코드에서 SIZE가 나올 때마다 3으로 바꾸라는 뜻입니다. 자세한 내용은 전처리기를 참고하세요.
| 현재 인덱스 | 연산 | 결과 |
|---|---|---|
| 0 | (0 + 1) % 3 | 1 |
| 1 | (1 + 1) % 3 | 2 |
| 2 | (2 + 1) % 3 | 0 (순환) |
삽입 (enqueue)
데이터를 삽입하면 rear 위치에 저장하고, rear를 다음 칸으로 이동합니다.
Queue* q의 *는 포인터를 뜻합니다. 큐의 원본을 직접 수정하기 위해 주소를 받는 것입니다. ->는 포인터로 구조체 멤버에 접근하는 화살표 연산자입니다. q->rear는 "q가 가리키는 큐의 rear"라는 뜻입니다.
삽입 예시
| 동작 | a[0] | a[1] | a[2] | front | rear |
|---|---|---|---|---|---|
| 초기 | 0 | 0 | 0 | 0 | 0 |
| enq(1) | 1 | 0 | 0 | 0 | 1 |
| enq(2) | 1 | 2 | 0 | 0 | 2 |
삭제 (dequeue)
데이터를 삭제하면 front 위치의 값을 반환하고, front를 다음 칸으로 이동합니다.
삭제 예시
| 동작 | 반환값 | a[0] | a[1] | a[2] | front | rear |
|---|---|---|---|---|---|---|
| 이전 | - | 1 | 2 | 0 | 0 | 2 |
| deq() | 1 | 1 | 2 | 0 | 1 | 2 |
왜 값을 실제로 지우지 않나요?
dequeue는 배열에서 값을 지우지 않고 front만 이동합니다.
| 이유 | 설명 |
|---|---|
| 효율성 | 값을 0으로 초기화하는 것도 연산입니다. 불필요한 작업은 생략합니다. |
| 덮어쓰기 | 나중에 그 자리에 enqueue하면 새 값으로 덮어씁니다. |
| 위치로 관리 | "큐에 있다/없다"는 값이 아니라 front/rear 위치로 판단합니다. |
비유: 책을 버릴 때 내용을 지우지 않고, "읽을 책 목록"에서 빼는 것과 같습니다.
front == rear이면 빈 큐
front는 맨 앞 데이터 위치, rear는 다음 빈 칸 위치입니다. 둘이 같으면 뺄 데이터가 없다는 뜻입니다.
| 상태 | front | rear | 의미 |
|---|---|---|---|
| 초기 (빈 큐) | 0 | 0 | front == rear → 비어있음 |
| enqueue(10) 후 | 0 | 1 | front ≠ rear → 데이터 있음 |
| dequeue() 후 | 1 | 1 | front == rear → 다시 비어있음 |
실기 문제 풀이 전략
문제 풀이 순서
- SIZE 확인: 배열 크기가 몇인지 확인
- 초기 상태 표 작성: front, rear, 배열 상태
- 연산 순서대로 추적: enq/deq 하나씩 표에 기록
- % SIZE 계산 주의: 특히 rear가 SIZE-1일 때 다음 값 확인
문제 유형
| 유형 | 설명 |
|---|---|
| 출력값 묻기 | deq() 반환값 순서대로 출력 |
| 빈칸 채우기 | enq/deq 함수 내 % SIZE 부분 |
| 상태 추적 | 특정 연산 후 front, rear 값 |