방송대 방통대 자료구조 4강 - 큐와 원형 큐의 이해 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 4강 - 큐와 원형 큐의 이해

큐의 선입선출 원리와 추상 자료형 연산을 익히고, CPU 스케줄링에서 큐가 어떻게 활용되는지 살펴본다. 배열로 구현한 선형 큐의 공간 낭비 문제와 이를 해결하는 원형 큐의 구조까지 시험에 자주 나오는 흐름으로 정리한다.

01. 큐의 개념과 기본 구조

먼저 들어온 원소가 먼저 나가는 자료구조

큐(queue)는 0개 이상의 원소를 갖는 유한 순서 리스트이다. 한쪽 끝에서는 삽입만 일어나고 다른 쪽 끝에서는 삭제만 일어나므로, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다. 이 처리 원리를 선입선출(First-In First-Out, FIFO) 또는 선착순 서비스(First-Come First-Serve, FCFS)라고 한다.

택시 승강장이나 병원 접수대의 대기 줄을 떠올리면 이해하기 쉽다. 먼저 줄을 선 사람이 먼저 서비스를 받는다. 작업 큐에 들어온 프로세스를 도착 순서대로 처리하는 CPU 스케줄링도 같은 원리를 사용한다.

구분	위치	역할
앞(front)	큐의 삭제 쪽	가장 먼저 들어온 원소를 꺼내는 곳
뒤(rear)	큐의 삽입 쪽	새 원소를 넣는 곳

예를 들어 큐에 A, B, C의 순서로 삽입하면 front는 A를 가리키고 rear는 C를 가리킨다. D를 삽입하면 rear 쪽에 D가 추가되고, 삭제하면 front 쪽의 A가 제거된다. 따라서 남은 원소의 상대적 순서는 B, C, D로 유지된다.

시험 핵심: 큐는 삽입과 삭제가 서로 다른 끝에서 일어난다. 삽입은 rear, 삭제는 front에서 수행되며 처리 원칙은 FIFO이다.

02. 큐의 추상 자료형과 핵심 연산

큐 객체와 연산의 정의

큐의 추상 자료형은 구현 방법보다 큐가 제공해야 하는 동작에 초점을 둔다. 큐 객체는 0개 이상의 원소를 갖는 유한 순서 리스트이며, 최대 크기 maxQueueSize를 가질 수 있다. 강의에서는 생성, 삽입, 삭제, 빈 큐 검사, 만원 큐 검사를 주요 연산으로 제시한다.

연산	기능	오류 조건
Create_q(n)	최대 크기 n인 빈 큐를 생성	n이 유효한 양의 크기가 아닌 경우
Add_q(queue, item)	rear에 item을 삽입	큐가 가득 찬 경우 queueFull
Delete_q(queue)	front의 원소를 삭제하고 반환	큐가 빈 경우 queueEmpty
IsEmpty_q(queue)	rear와 front를 비교해 빈 상태 검사	없음
IsFull_q(queue, n)	원소 수가 최대 크기 n인지 검사	없음

연산 순서로 상태 추적하기

크기가 4인 빈 큐를 만든 뒤 A, B, C를 차례로 삽입하고 세 번 삭제하면 A, B, C의 순서로 제거되어 다시 빈 큐가 된다. 그 뒤 D를 삽입하면 D가 새 원소가 된다. 큐 문제에서는 배열 칸만 보지 말고, 각 단계에서 front와 rear가 어느 위치로 이동하는지 함께 추적해야 한다.

삭제 연산은 원소를 단순히 읽는 것이 아니라 front 쪽 원소를 큐에서 제거한 뒤 그 값을 반환한다. 빈 큐에서 삭제를 시도하는 언더플로와 가득 찬 큐에서 삽입을 시도하는 오버플로를 구분한다.

03. 큐의 응용: CPU 스케줄링

FCFS 스케줄링

FCFS(First-Come First-Served) 스케줄링은 준비 큐에 도착한 순서대로 CPU를 할당한다. 한 작업이 CPU를 받으면 그 작업이 완료될 때까지 사용하는 비선점 방식으로 설명할 수 있으며, 가장 먼저 도착한 작업이 가장 먼저 처리된다는 점에서 FIFO 큐의 전형적인 응용이다.

RR 스케줄링

RR(Round Robin) 스케줄링은 대화형 시스템에 적합하다. 각 작업에 일정한 크기의 시간 할당량인 타임 슬라이스(time slice)를 주고, 그 시간 안에 끝나지 않은 작업은 준비 큐의 맨 뒤로 이동한다. 모든 작업이 큐를 순환하며 CPU를 나누어 사용하므로 원형 큐의 순환 구조와 연결해 이해할 수 있다.

구분	FCFS	RR
선택 기준	준비 큐 도착 순서	도착 순서와 시간 할당량
CPU 사용	작업 완료까지 계속 사용	타임 슬라이스만큼 번갈아 사용
미완료 작업	해당 작업이 계속 실행	준비 큐의 맨 뒤로 이동
적합한 환경	단순한 일괄 처리	대화형 시스템

04. 배열을 이용한 선형 큐 구현

초기화와 삽입

크기가 QUEUE_SIZE인 배열로 큐를 구현할 때 강의의 선형 큐는 front = -1, rear = -1에서 시작한다. 원소를 삽입하면 rear를 먼저 1 증가시키고 그 위치에 값을 저장한다. 따라서 삽입의 핵심 표현은 queue[++rear] = item이다. rear가 QUEUE_SIZE - 1이면 배열의 마지막 칸에 도달했으므로 더 삽입할 수 없다고 판단한다.

삭제와 빈 상태

삭제할 원소가 있는지는 front == rear인지 검사한다. 두 값이 같으면 큐가 비어 있다. 비어 있지 않다면 front를 먼저 1 증가시키고 queue[++front]의 값을 반환한다. 예를 들어 100, 200, 300이 저장되어 있고 front가 -1, rear가 2라면 한 번 삭제한 뒤 100이 반환되고 front는 0이 된다.

포인터 변화: 삽입 때 rear가 오른쪽으로 이동하고, 삭제 때 front가 오른쪽으로 이동한다. 강의의 배열 구현에서는 front가 마지막으로 삭제한 위치, rear가 마지막으로 삽입한 위치를 나타낸다.

거짓 포화 문제

선형 큐에서는 앞쪽 원소를 삭제해 빈 칸이 생겨도 rear가 배열 끝에 도달하면 더 삽입할 수 없다고 판단한다. 실제 배열에는 비어 있는 칸이 있지만 새 원소를 넣지 못하므로 공간이 낭비된다. 모든 원소를 매번 앞으로 이동하면 공간을 재사용할 수 있지만 이동 비용이 발생한다. 이 문제를 구조적으로 해결하기 위해 원형 큐를 사용한다.

05. 원형 큐의 원리와 상태 변화

배열의 끝과 처음을 연결하기

원형 큐(circular queue)는 배열의 마지막 위치 다음을 첫 위치로 연결해 파이프의 입구와 출구를 이어 놓은 것처럼 사용하는 구조이다. rear 또는 front가 마지막 인덱스를 지나면 0으로 돌아가므로, 앞쪽에서 삭제되어 생긴 공간을 다시 삽입에 사용할 수 있다. 인덱스의 순환은 보통 (인덱스 + 1) % QUEUE_SIZE로 계산한다.

크기 5인 큐에서 0번부터 4번 칸까지 사용한 뒤 rear가 4에 있다면 다음 삽입 위치는 (4 + 1) % 5 = 0이다. 다만 0번 칸이 이미 유효한 원소로 사용 중인지, 삭제되어 비어 있는지는 front와 rear의 상태 규칙으로 판단해야 한다.

공백 상태와 포화 상태 구분

원형 큐에서는 front와 rear가 같은 위치인 상태를 빈 큐로 사용하는 경우가 많다. 이 규칙만 사용하면 모든 칸을 원소로 채웠을 때도 두 포인터가 같아져 빈 상태와 구별하기 어렵다. 강의는 이 모호성을 피하기 위해 한 칸을 항상 비워 두는 방식을 설명한다. 그러면 다음 rear 위치가 front와 같을 때 큐가 가득 찼다고 판단할 수 있고, 실제 저장 가능한 원소 수는 배열 크기보다 하나 적다.

항목	선형 큐	원형 큐
인덱스 진행	오른쪽으로만 증가	끝에서 0으로 순환
삭제된 앞 공간	바로 재사용하기 어려움	rear가 순환해 재사용
주요 문제	거짓 포화와 공간 낭비	빈 상태와 포화 상태의 구분 필요
대표 해결 규칙	원소 이동 또는 구조 변경	한 칸을 비워 상태를 구분

원형 큐에서 배열 크기가 n이고 한 칸을 비워 두면 최대 저장 원소 수는 n - 1이다. “배열의 모든 칸이 채워져야만 full”이라는 설명은 이 구현 규칙에서는 옳지 않다.

06. 핵심 개념 정리

큐는 삽입과 삭제가 서로 다른 끝에서 수행되는 FIFO 자료구조이다. rear에서 삽입하고 front에서 삭제하며, Add_q·Delete_q·IsEmpty_q·IsFull_q 등의 연산으로 추상화한다.

응용에서는 FCFS가 준비 큐 도착 순서를 그대로 따르고, RR은 시간 할당량이 끝난 미완료 작업을 준비 큐 맨 뒤로 보낸다는 차이를 기억한다.

배열 큐에서는 삽입 때 rear, 삭제 때 front가 증가한다. 선형 큐는 rear가 끝에 도달하면 앞쪽 빈 공간을 재사용하지 못하는 문제가 있고, 원형 큐는 나머지 연산으로 인덱스를 순환시켜 이를 해결한다.

최종 암기: FIFO · 삽입 rear · 삭제 front · 빈 선형 큐 front == rear · 원형 인덱스 (i + 1) % n · 한 칸을 비우면 최대 저장량 n - 1.

예상문제 20개

1. 큐의 처리 원칙으로 옳은 것은?

① 가장 나중에 삽입된 원소를 먼저 삭제한다. ② 가장 먼저 삽입된 원소를 먼저 삭제한다. ③ 우선순위가 가장 낮은 원소를 먼저 삭제한다. ④ 가운데 원소부터 차례로 삭제한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
큐는 먼저 들어온 원소가 먼저 나가는 FIFO 자료구조이다.

2. 큐에서 새 원소가 삽입되는 위치를 나타내는 것은?

① top ② head ③ front ④ rear

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삽입은 큐의 뒤인 rear에서, 삭제는 앞인 front에서 수행된다.

3. 큐에서 원소의 삭제가 이루어지는 위치는?

① front ② rear ③ top ④ middle

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
front는 가장 먼저 들어온 원소가 위치한 삭제 쪽을 나타낸다.

4. 큐의 추상 자료형 연산과 기능의 연결로 옳은 것은?

① IsEmpty_q — rear에 원소 삽입 ② Add_q — front의 원소 삭제 ③ Delete_q — front의 원소를 삭제하고 반환 ④ IsFull_q — 빈 큐 생성

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
Delete_q는 front 쪽 원소를 제거하고 그 값을 반환하는 삭제 연산이다.

5. 빈 큐에서 Delete_q를 실행했을 때의 상황은?

① 오버플로 ② 언더플로 또는 queueEmpty 오류 ③ rear 자동 초기화 ④ 원소 자동 생성

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
삭제할 원소가 없는 빈 큐에서 삭제를 시도하면 queueEmpty에 해당하는 언더플로가 발생한다.

6. A, B, C를 차례로 큐에 삽입한 뒤 한 번 삭제하면 제거되는 원소는?

① A ② B ③ C ④ 삭제할 수 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
FIFO 원칙에 따라 가장 먼저 삽입된 A가 가장 먼저 삭제된다.

7. FCFS CPU 스케줄링에 대한 설명으로 옳은 것은?

① 실행 시간이 가장 짧은 작업부터 처리한다. ② 우선순위가 낮은 작업부터 처리한다. ③ 모든 작업을 한 명령씩 교대로 처리한다. ④ 준비 큐에 도착한 순서대로 CPU를 할당한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
FCFS는 First-Come First-Served의 약자로 준비 큐 도착 순서를 따른다.

8. RR 스케줄링에서 시간 할당량 안에 끝나지 않은 작업은 어떻게 되는가?

① 즉시 삭제된다. ② 준비 큐의 맨 앞에 고정된다. ③ 준비 큐의 맨 뒤에 다시 배치된다. ④ FCFS 작업으로 변환된다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
RR은 타임 슬라이스가 끝난 미완료 작업을 준비 큐의 뒤로 보내 다시 차례를 기다리게 한다.

9. 강의의 선형 배열 큐에서 초기 front와 rear의 값은?

① front = -1, rear = -1 ② front = 0, rear = 0 ③ front = 0, rear = -1 ④ front = 1, rear = 1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
강의의 C 배열 구현은 두 변수를 모두 -1로 초기화해 공백 상태를 나타낸다.

10. 선형 배열 큐에서 삽입 연산을 올바르게 표현한 것은?

① queue[--front] = item ② queue[front++] = item ③ item = queue[rear--] ④ queue[++rear] = item

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삽입할 때 rear를 먼저 증가시키고 그 배열 위치에 item을 저장한다.

11. 선형 배열 큐에서 삭제 연산이 반환하는 값의 표현은?

① queue[++rear] ② queue[++front] ③ queue[--rear] ④ queue[front--]

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
강의 구현에서는 front를 먼저 증가시킨 뒤 해당 위치의 원소를 반환한다.

12. 선형 배열 큐가 비어 있음을 판단하는 조건은?

① rear == QUEUE_SIZE - 1 ② front == -1 ③ front == rear ④ front > QUEUE_SIZE

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
모든 삽입 원소가 삭제되면 front가 rear를 따라잡아 두 값이 같아진다.

13. 선형 배열 큐의 거짓 포화 문제를 가장 정확히 설명한 것은?

① front와 rear가 항상 0에 머무는 현상 ② 삽입한 원소의 순서가 뒤집히는 현상 ③ 빈 큐에서도 삭제가 가능한 현상 ④ 앞에 빈 칸이 있어도 rear가 끝에 도달해 삽입하지 못하는 현상

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
삭제된 앞쪽 공간이 남아 있어도 선형 rear는 되돌아가지 않으므로 공간을 재사용하지 못한다.

14. 원형 큐를 사용하는 주된 이유는?

① 삭제로 생긴 앞쪽 공간을 순환하여 재사용하기 위해 ② 원소를 자동 정렬하기 위해 ③ 후입선출 구조로 바꾸기 위해 ④ 모든 삭제 연산을 제거하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
원형 큐는 배열 끝과 처음을 논리적으로 연결하여 삭제된 공간을 다시 활용한다.

15. 크기가 5인 원형 큐에서 현재 인덱스가 4일 때 다음 인덱스는?

① 5 ② -1 ③ 0 ④ 4

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
(4 + 1) % 5 = 0이므로 배열의 첫 위치로 순환한다.

16. 원형 큐에서 한 칸을 비워 두는 까닭은?

① 원소의 정렬 상태를 유지하기 위해 ② 빈 상태와 가득 찬 상태를 구별하기 위해 ③ 삭제 연산을 금지하기 위해 ④ 배열 인덱스를 1부터 시작하기 위해

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
front와 rear가 같은 상태를 공백으로 쓸 때 한 칸을 비우면 포화 상태와 혼동하지 않는다.

17. 한 칸을 비우는 방식의 원형 큐에서 배열 크기가 8일 때 최대 저장 가능한 원소 수는?

① 5개 ② 6개 ③ 8개 ④ 7개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
상태 구분을 위해 한 칸을 비우므로 최대 저장량은 n - 1, 즉 7개이다.

18. 원형 큐의 다음 위치를 계산하는 일반적인 식은?

① index - QUEUE_SIZE ② (index + 1) % QUEUE_SIZE ③ index * QUEUE_SIZE ④ QUEUE_SIZE / index

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
나머지 연산을 사용하면 마지막 인덱스 다음에 0으로 자연스럽게 돌아간다.

19. 큐와 스택의 처리 순서를 바르게 비교한 것은?

① 큐는 FIFO, 스택은 LIFO이다. ② 큐와 스택 모두 FIFO이다. ③ 큐는 LIFO, 스택은 FIFO이다. ④ 큐와 스택 모두 임의 순서로 삭제한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
큐는 먼저 들어온 원소를 먼저 꺼내고, 스택은 가장 나중에 들어온 원소를 먼저 꺼낸다.

20. 큐에 A, B, C를 삽입한 뒤 두 번 삭제하고 D를 삽입했다. 남은 원소의 순서는?

① A, D ② B, D ③ C, D ④ D, C

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
두 번의 삭제로 A와 B가 제거되고, C 뒤에 D가 삽입되므로 C, D가 남는다.