방송대 자료구조 4강: 큐의 상태 변화와 원형 큐
앞에서 두 항목을 꺼내 빈 칸이 생겼는데도 새 항목을 넣을 수 없다는 판정이 나올 수 있습니다. 큐의 원리보다 배열의 끝에 도달했다는 사실만 검사했기 때문입니다. 이 글은 큐의 선입선출 원칙을 front와 rear의 이동으로 추적하고, 추상 자료형·작업 스케줄링·선형 배열 큐·원형 큐를 하나의 상태 변화 과정으로 연결합니다.
빈 칸이 있는데도 가득 찼다고 판정되는 이유부터 보자
정원이 5칸인 선형 배열 큐에 세 항목을 넣고 앞의 두 항목을 삭제했다고 하자. 배열 앞쪽 두 칸은 더 이상 사용하지 않지만, 삭제는 front만 뒤로 움직일 뿐 rear를 앞으로 되돌리지 않는다. 이후 삽입을 계속해 rear가 마지막 인덱스 4에 닿으면, 앞에 빈 칸이 있어도 단순한 선형 구현은 더 넣지 못한다.
이 현상을 이해하려면 세 층을 분리해야 한다. 첫째, 큐라는 논리 구조는 먼저 들어온 항목을 먼저 내보낸다. 둘째, 추상 자료형은 삽입·삭제·공백·포화 연산의 의미를 정한다. 셋째, 배열 구현은 그 의미를 인덱스 이동으로 실현한다. 원형 큐는 첫째와 둘째를 바꾸는 구조가 아니라, 셋째의 공간 사용 방식을 개선한 구현이다.
이 강의의 추적 질문: 각 연산 뒤에 첫 원소의 바로 앞을 가리키는 front와 마지막 원소를 가리키는 rear가 어디에 있는가? 이 두 위치와 공백·포화 조건을 함께 기록하면 선형 큐의 한계와 원형 큐의 해결 원리를 설명할 수 있다.
큐는 양쪽 끝에 서로 다른 임무를 준다
큐는 한쪽 끝에서만 새 원소를 삽입하고 반대쪽 끝에서만 기존 원소를 삭제하는 유한 순서 리스트다. 삽입이 일어나는 뒤쪽을 rear, 삭제가 일어나는 앞쪽을 front라고 한다. 먼저 들어온 원소가 먼저 나가는 선입선출(FIFO) 원칙이 유지되므로, 도착 순서를 처리 순서로 삼는 대기 행렬을 표현하기에 알맞다.
수도꼭지 앞에서 물을 받는 사람, 택시 승강장, 은행 창구와 계산대의 대기 줄을 떠올리면 된다. 새로 온 사람은 줄의 뒤에 서고, 서비스를 받을 사람은 줄의 앞에서 빠져나간다. 반면 스택은 삽입과 삭제가 같은 끝에서 일어나므로 나중에 들어온 항목이 먼저 나온다. 두 구조의 차이는 항목의 모양이 아니라 삽입 끝과 삭제 끝의 관계에 있다.
| 판단 항목 | 큐 | 스택 |
|---|---|---|
| 삽입 위치 | 뒤쪽 rear | 한쪽 끝 top |
| 삭제 위치 | 앞쪽 front | 삽입과 같은 끝 top |
| 처리 원칙 | 먼저 들어온 원소를 먼저 삭제 | 나중에 들어온 원소를 먼저 삭제 |
| 핵심 질문 | 누가 가장 오래 기다렸는가? | 가장 최근에 넣은 것은 무엇인가? |
추상 자료형은 저장 칸보다 연산의 계약을 먼저 정한다
큐 추상 자료형의 객체는 0개 이상의 원소로 이루어진 유한 순서 리스트다. 이 수준에서는 배열의 몇 번째 칸에 저장할지 결정하지 않는다. 대신 큐를 만들고, 뒤에 넣고, 앞에서 꺼내고, 비었는지와 가득 찼는지를 판단하는 연산의 의미를 명확히 한다.
| 연산 | 정상 상태의 결과 | 경계 상태의 처리 |
|---|---|---|
Create_q(maxSize) | 최대 크기를 가진 빈 큐를 만든다. | 처음에는 원소 수가 0이다. |
Add_q(queue, item) | item을 rear 쪽에 삽입한다. | 가득 찼다면 포화 오류를 알린다. |
Delete_q(queue) | front 쪽의 첫 원소를 삭제해 돌려준다. | 비었다면 공백 오류를 알린다. |
IsEmpty_q(queue) | 원소가 없으면 참을 돌려준다. | 구현에서 정한 공백 조건을 검사한다. |
IsFull_q(queue) | 더 삽입할 수 없으면 참을 돌려준다. | 최대 크기와 현재 상태를 비교한다. |
포화 큐에 삽입하거나 빈 큐에서 삭제하는 행동은 정상 연산이 아니다. 특히 삭제 연산은 단순히 위치만 움직이는 것이 아니라 삭제된 원소를 반환해야 한다. 이 계약을 먼저 세워 두면 배열 큐와 원형 큐처럼 구현이 달라져도 사용자가 기대하는 동작은 일관되게 유지된다.
오개념 교정: front와 rear가 같다는 식만 외우면 위험하다. 그 식이 공백을 뜻하는지는 구현의 포인터 규칙에 달려 있다. 이 강의의 배열 구현에서는 front가 첫 원소 자체가 아니라 첫 원소의 바로 앞을 가리키며, rear는 마지막 원소를 가리킨다는 약속을 사용한다.
연산 열은 값의 순서와 경계 검사를 함께 바꾼다
학습용으로 최대 4개를 담는 추상 큐를 만들고 다음 연산을 차례로 수행해 보자. 항목 이름과 연산 열은 상태 추적을 위해 별도로 구성한 예시다. 큐의 왼쪽이 삭제되는 앞쪽, 오른쪽이 삽입되는 뒤쪽이다.
| 단계 | 수행 연산 | 연산 뒤의 큐 | 읽어야 할 변화 |
|---|---|---|---|
| 1 | Create_q(4) | [ ] | 빈 큐가 만들어진다. |
| 2 | Add_q(도담) | [도담] | 첫 항목이 뒤에 들어간다. |
| 3 | Add_q(라온) | [도담, 라온] | 도담의 앞선 도착 순서는 유지된다. |
| 4 | Add_q(마루) | [도담, 라온, 마루] | 새 항목은 항상 뒤에 붙는다. |
| 5 | Delete_q() | [라온, 마루] | 도담이 삭제되어 반환된다. |
| 6 | Add_q(보람) | [라온, 마루, 보람] | 삭제 뒤 삽입해도 기존 순서를 건드리지 않는다. |
| 7 | Delete_q() | [마루, 보람] | 현재 가장 앞선 라온이 반환된다. |
이 표에서 중요한 것은 배열 칸이 아니라 논리적 순서다. 삭제된 도담과 라온이 어느 주소에 남아 있는지는 추상 큐의 사용자가 알 필요가 없다. 배열 구현 단계에 들어가면 같은 연산 열을 front와 rear의 숫자로 다시 추적해야 한다.
선착순과 라운드 로빈은 큐에서 꺼낸 뒤의 행동이 다르다
큐는 중앙처리장치의 작업 대기 순서를 정하는 데 쓰인다. 선착순 서비스(FCFS)에서는 준비 큐에 먼저 도착한 작업이 중앙처리장치를 먼저 얻고, 실행을 마칠 때까지 계속 사용한다. 앞의 긴 작업이 끝나야 뒤의 짧은 작업이 시작된다는 특징이 있다.
라운드 로빈(RR)은 각 작업에 일정한 시간 할당량을 준다. 할당량 안에 끝난 작업은 큐에서 사라지지만, 끝나지 않은 작업은 준비 큐의 rear로 돌아간다. 따라서 라운드 로빈의 핵심은 단순한 순환 모양이 아니라 시간이 끝난 미완료 작업을 뒤에 재삽입하는 규칙이다.
| 비교 기준 | 선착순 서비스 | 라운드 로빈 |
|---|---|---|
| 선택 기준 | 준비 큐에 먼저 도착한 작업 | 준비 큐의 맨 앞 작업 |
| 한 번 선택된 뒤 | 작업 완료까지 계속 실행 | 정해진 시간만 실행 |
| 시간 안에 못 끝나면 | 별도 시간 제한이 없다. | 큐의 뒤에 다시 들어간다. |
| 큐가 하는 일 | 최초 도착 순서를 보존 | 차례를 반복해서 배분 |
예를 들어 필요한 실행 시간이 각각 5, 2, 4인 세 작업 가·나·다가 그 순서로 도착하고 시간 할당량이 2라고 하자. 라운드 로빈의 실행 차례는 ‘가 2 → 나 2 완료 → 다 2 → 가 2 → 다 2 완료 → 가 1 완료’가 된다. 가가 먼저 도착했어도 한 번에 5만큼 독점하지 않고, 미완료일 때마다 뒤로 이동하기 때문이다.
선형 배열 큐는 포인터를 오른쪽으로만 이동시킨다
크기 5인 배열 큐를 만들면 인덱스는 0부터 4까지다. 처음에는 front=-1, rear=-1로 두어 빈 상태를 나타낸다. 삽입할 때는 먼저 rear를 1 증가시키고 그 칸에 원소를 저장한다. 삭제할 때는 먼저 front를 1 증가시키고 그 칸의 원소를 반환한다.
- 공백 검사:
front == rear이면 아직 반환할 원소가 없다. - 포화 검사: 선형 구현에서는
rear == 4이면 배열 끝에 도달했다. - 삽입: 포화가 아니면
rear를 증가시킨 뒤 새 원소를 저장한다. - 삭제: 공백이 아니면
front를 증가시킨 뒤 해당 원소를 반환한다.
직접 구성한 상태 추적을 보자. 5칸 배열에 ‘가, 나, 다’를 넣으면 front=-1, rear=2다. 두 번 삭제하면 가와 나가 반환되고 front=1, rear=2가 된다. 이어 라와 마를 넣으면 rear=4가 된다. 논리적으로 남은 원소는 다·라·마 세 개뿐이지만, 다음 삽입은 실패한다. 인덱스 0과 1은 비어 보여도 rear를 더 오른쪽으로 보낼 수 없기 때문이다.
잘못된 접근과 교정: “원소가 3개이므로 5칸 배열에는 두 개를 더 넣을 수 있다”라고 판단하면 논리적 원소 수와 선형 구현의 사용 가능 위치를 혼동한 것이다. 선형 큐에서는 먼저 rear가 마지막 인덱스에 닿았는지 확인해야 한다. 삭제된 앞 칸을 다시 쓰고 싶다면 포인터를 임의로 되돌리는 대신 원형 큐 규칙을 사용한다.
원형 큐는 마지막 칸의 다음을 첫 칸으로 연결한다
원형 큐는 배열의 물리적 모양을 둥글게 바꾸는 것이 아니다. 다음 위치를 계산할 때 배열 크기 n으로 나눈 나머지를 사용하여, 마지막 인덱스 다음을 인덱스 0으로 해석한다. 즉 다음 위치는 (현재 위치 + 1) % n이다. 크기 5에서 인덱스 4의 다음은 (4+1)%5=0이 된다.
이 강의의 포인터 약속을 원형 큐에도 적용하면 삽입은 rear=(rear+1)%n으로 이동한 뒤 저장하고, 삭제는 front=(front+1)%n으로 이동한 뒤 반환한다. 앞에서 삭제해 생긴 칸으로 rear가 순환할 수 있으므로 선형 큐의 공간 낭비를 줄인다.
| 구분 | 선형 배열 큐 | 원형 큐 |
|---|---|---|
| 다음 인덱스 | 현재 인덱스에 1을 더한다. | (현재 인덱스+1)%n |
| 마지막 칸 뒤 | 더 이동할 수 없다. | 인덱스 0으로 순환한다. |
| 삭제된 앞 칸 | 단순 구현에서는 재사용하지 못한다. | rear가 돌아와 재사용할 수 있다. |
| 공백 조건 | front == rear | front == rear |
| 포화 조건 | rear == n-1 | (rear+1)%n == front |
같은 위치 관계로 공백과 포화를 구별하려면 한 칸을 비운다
원형으로 계속 이동시키기만 하면 front == rear가 ‘원소가 하나도 없음’과 ‘배열을 한 바퀴 가득 채움’을 동시에 나타낼 수 있다. 포인터 두 개만으로 두 상태를 구별하려면 한 칸을 의도적으로 사용하지 않는다. 그래서 크기 n인 원형 배열이 이 규칙으로 저장할 수 있는 최대 원소 수는 n-1개다.
포화 여부는 rear의 다음 위치가 front와 같은지로 검사한다. 크기 5인 원형 큐에서 front=1, rear=0이라면 활성 원소는 인덱스 2, 3, 4, 0에 네 개 있을 수 있다. 다음 rear는 (0+1)%5=1이고 front와 같으므로 포화 상태다. 인덱스 1은 공백과 포화를 구별하는 빈 칸으로 남겨 둔다.
조건을 고르는 순서: ① front가 무엇을 가리키는지 확인한다. ② 선형인지 원형인지 확인한다. ③ 공백은 현재 두 포인터를 비교한다. ④ 원형 포화는 rear 자체가 아니라 rear의 다음 위치를 front와 비교한다. ⑤ 실제 저장 가능량이 배열 크기보다 하나 작음을 반영한다.
새 연산 열은 다섯 단계로 검산할 수 있다
큐 문제에서 값만 적어 나가면 포인터 갱신 시점과 경계 조건을 놓치기 쉽다. 다음 절차를 사용하면 추상 큐, 선형 배열 큐와 원형 큐 문제를 같은 틀에서 풀 수 있다.
- 구현 규칙을 적는다. 배열 크기, 초기값,
front와rear가 가리키는 대상을 먼저 확정한다. - 연산 전에 경계를 검사한다. 삽입 전에는 포화, 삭제 전에는 공백 조건을 계산한다.
- 포인터를 규칙대로 이동한다. 이 강의의 구현에서는 증가 또는 나머지 연산을 먼저 적용한 뒤 저장·반환한다.
- 논리적 순서를 별도로 적는다. 배열의 왼쪽부터 읽지 말고
front다음에서 시작해rear까지 따라간다. - 반환값과 다음 가능 연산을 확인한다. 삭제된 값이 가장 먼저 들어온 활성 원소인지, 다음 삽입이 가능한지 다시 검사한다.
짧은 자가 점검을 해 보자. 크기 6인 원형 큐에서 front=4, rear=2라면 다음 삽입 위치는 3이다. 3은 front 4와 다르므로 삽입할 수 있다. 삽입 후 rear=3이 되면 다음 위치는 4로 front와 같아져 포화 상태가 된다. 이처럼 현재 원소 수를 눈짐작하기보다 다음 위치를 계산해야 한다.
핵심 내용을 상태 변화로 묶어 정리한다
- 큐는
rear에서 삽입하고front에서 삭제하여 선입선출 순서를 유지한다. - 추상 자료형은 생성·삽입·삭제·공백·포화 연산의 의미와 오류 조건을 구현과 분리해 명세한다.
- 선착순 서비스는 먼저 도착한 작업을 완료까지 실행하고, 라운드 로빈은 시간 할당량 뒤 미완료 작업을 큐의 뒤에 다시 넣는다.
- 선형 배열 큐는
rear가 끝에 닿으면 앞쪽 빈 칸이 있어도 더 삽입하지 못하는 한계가 있다. - 원형 큐는 나머지 연산으로 마지막 칸과 첫 칸을 논리적으로 연결해 삭제된 앞쪽 공간을 다시 사용한다.
- 한 칸을 비우는 원형 큐에서는 공백이
front==rear, 포화가(rear+1)%n==front이며 최대 저장량은 n-1개다.
마지막 판단: 큐의 배열 그림을 볼 때 빈 칸의 개수만 세지 말자. 삽입과 삭제의 방향, 포인터의 의미, 선형·원형 여부와 다음 위치의 경계 조건을 차례로 확인해야 한다. 이 순서를 지키면 같은 선입선출 큐라도 왜 선형 구현에서 조기 포화가 생기고, 원형 구현에서 왜 한 칸을 비워야 하는지 스스로 설명할 수 있다.
예상문제 10선
1. 큐의 삽입과 삭제 위치를 가장 정확하게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 두 끝의 역할을 서로 바꾸었다. 새 원소는 뒤쪽에 들어가고 기존 첫 원소는 앞쪽에서 나온다.
- ② 오답: 같은 끝에서 삽입과 삭제를 하면 스택의 동작에 가까워 선입선출을 보장하지 못한다.
- ③ 오답: 뒤쪽에서 방금 넣은 원소를 삭제하면 나중에 들어온 원소가 먼저 나가게 된다.
- ④ 정답: 삽입 끝과 삭제 끝을 분리해야 먼저 들어온 원소가 먼저 삭제되는 큐의 순서가 유지된다.
2. 큐와 스택을 구분하는 기준으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 두 구조 모두 원소 자료형과 무관하게 정의할 수 있으며 저장 값의 종류가 구분 기준은 아니다.
- ② 정답: 삽입과 삭제가 일어나는 끝의 관계가 각각 선입선출과 후입선출의 차이를 만든다.
- ③ 오답: 큐와 스택 모두 배열이나 연결 구조로 구현할 수 있으므로 구현 재료로 구분할 수 없다.
- ④ 오답: 배열 스택도 공백과 포화 검사가 필요하며 경계 오류는 두 구조 모두에서 생긴다.
3. 빈 큐에 가, 나, 다를 차례로 삽입한 뒤 한 번 삭제할 때 반환값과 남은 순서는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 가장 먼저 삽입된 가가
front에서 삭제되고 나와 다의 기존 순서는 유지된다. - ② 오답: 마지막에 삽입된 다를 먼저 꺼내는 것은 후입선출을 적용한 결과다.
- ③ 오답: 중간 원소를 임의로 삭제하면 큐가 허용하는 앞쪽 삭제 규칙을 어긴다.
- ④ 오답: 삭제는 남은 원소의 도착 순서를 뒤집지 않으므로 다와 나의 순서가 바뀔 수 없다.
4. 크기 5인 선형 배열 큐가 front=-1, rear=-1에서 시작한다. 세 번 삽입하고 두 번 삭제한 직후의 포인터는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 삽입과 삭제의 이동을 서로 상쇄한 결과다. 삭제는
rear를 줄이지 않는다. - ② 오답: 두 번 삭제하면
front는 -1에서 1이 되며, 2가 되려면 세 번 삭제해야 한다. - ③ 정답: 세 번 삽입해
rear는 2, 두 번 삭제해front는 1이 된다. - ④ 오답:
rear=4는 처음 상태에서 다섯 번 삽입했을 때 도달하는 값이다.
5. 시간 할당량이 끝났지만 작업이 완료되지 않은 라운드 로빈의 처리로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 미완료 작업을 뒤로 보내야 다음 대기 작업에 차례를 주고 이후 다시 실행할 수 있다.
- ② 오답: 완료까지 계속 실행하는 방식은 시간 할당량을 사용하는 라운드 로빈의 차례 배분과 다르다.
- ③ 오답: 앞에 다시 넣으면 같은 작업이 곧바로 선택되어 다른 작업의 실행 기회를 막는다.
- ④ 오답: 할당량 소진은 작업 완료가 아니며 남은 실행을 위해 큐에 보존해야 한다.
6. 크기 5인 선형 배열 큐에서 front=1, rear=4이고 활성 원소가 3개다. 다음 삽입에 대한 옳은 판단은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
- ① 오답: 전체 빈 칸 수가 아니라
rear뒤의 사용 가능 위치를 검사해야 하며 현재는 배열 끝이다. - ② 오답:
front만 초기화하면 활성 원소의 앞 경계가 깨져 삭제 순서를 잃는다. - ③ 오답: 순환 규칙과 포화 조건 없이
rear만 바꾸면 아직 활성인 원소를 덮어쓸 수 있다. - ④ 정답: 선형 배열 큐의 포화 조건
rear==n-1을 만족하므로 앞쪽 빈 칸이 있어도 삽입이 막힌다.
7. 크기 5인 원형 큐에서 rear=4이고 포화가 아니라면 다음 삽입 위치는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
- ① 오답: 인덱스 4는 현재
rear위치이며 삽입 전에 다음 위치로 이동해야 한다. - ② 정답:
(4+1)%5=0이므로 마지막 인덱스 다음은 첫 인덱스로 순환한다. - ③ 오답: 인덱스 1은 0에서 한 번 더 이동해야 도달하며 현재 계산 결과가 아니다.
- ④ 오답: 크기 5인 배열의 유효 인덱스는 0부터 4까지여서 인덱스 5는 존재하지 않는다.
8. 한 칸을 비우는 크기 6 원형 큐의 공백 조건과 포화 조건을 바르게 짝지은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 선형 배열의 끝 조건을 원형 큐에 적용하면 인덱스 순환과 현재 상태를 판정할 수 없다.
- ② 오답: 공백과 포화의 관계를 뒤섞었다. 같은 위치는 공백이고
rear의 다음이front이면 포화다. - ③ 정답: 한 칸을 비워 두는 규칙은 두 포인터가 같을 때 공백, 다음
rear가front일 때 포화로 구분한다. - ④ 오답: 원소가 하나면 비어 있지 않고, 이 규칙의 최대 저장량은 6이 아니라 5다.
9. 한 칸을 비우는 크기 5 원형 큐에서 front=1, rear=0인 상태에 대한 옳은 해석은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
- ① 오답: 원형 큐의 공백 조건은 이웃 여부가 아니라
front==rear이며 현재 값은 다르다. - ② 오답: 인덱스 1은 공백과 포화를 구별하기 위해 남겨 둔 칸이므로 활성 원소를 넣을 수 없다.
- ③ 정답:
(0+1)%5=1이front와 같아 포화 조건을 만족한다. - ④ 오답:
rear의 숫자만으로 원소 수를 판단할 수 없으며 순환 뒤 0에 도달한 상태일 수 있다.
10. 배열 큐의 연산 열을 정확히 추적하는 절차로 가장 타당한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
- ① 정답: 표현 규칙을 먼저 확정하고 오류 가능성을 검사한 뒤 상태를 바꾸며, 마지막에 선입선출 결과까지 확인하는 순서다.
- ② 오답: 구현과 포인터 의미를 나중에 정하면 같은 빈 칸도 사용 가능한지 판단할 근거가 없다.
- ③ 오답: 큐 연산마다 값을 왼쪽으로 정렬하지 않으며 경계 검사는 상태 변경 전에 해야 한다.
- ④ 오답: 선형과 원형은 같은 원소 수에서도 포화 판단이 다르므로 포인터와 구현 규칙을 무시할 수 없다.
참고 자료와 작성 기준
이 글은 한국방송통신대학교 자료구조 4강 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 강의의 큐 연산과 구현 범위를 유지하면서 포인터 상태 추적, 선형 큐의 조기 포화 사례, 원형 큐의 경계 검산과 작업 스케줄링 예시는 초급 학습자가 과정을 재현할 수 있도록 별도로 구성하고 확인했습니다.
- 작성·편집: 올에이클래스 학습연구팀
- 주요 근거: 한국방송통신대학교 자료구조 4강 「큐」 강의록 전체 50쪽
- 외부 보충 자료: 사용하지 않음
- 편집 원칙: 올에이클래스 편집 정책
- 최종 내용 검토: 2026-08-18
댓글
댓글 쓰기