<조건>을 만족하고 front와 rear의 값이 모두 0인 … | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 20년 1회차
<조건>을 만족하고 front와 rear의 값이 모두 0인 원형 큐(circular queue)에서 <동작>에 나열된 연산을 순서대로 모두 수행하였다. 연산 완료 후 원형 큐에 존재하는 모든 유효 데이터와 front 및 rear의 값을 바르게 연결한 것은? (단, enqueue(x)에 의해 삽입된 후 dequeue()에 의해 삭제되지 않은 데이터만 유효 데이터로 인정한다)<조 건>
○ 원형 큐는 원소 개수가 6개인 1차원 배열로 구현되었다.
○ front와 rear의 값이 같을 때 원형 큐는 공백 상태이다.
○ front와 ((rear + 1) mod 6)의 값이 같을 때 원형 큐는 포화 상태이다.
○ enqueue(x)에 의해 rear의 값을 ((rear + 1) mod 6)로 변경한 후 rear가 가리키는 위치에 데이터 x를 삽입한다. 단, 포화 상태일 때에는 데이터 삽입이 이루어지지 않아 원형 큐의 상태가 변하지 않는다.
○ dequeue()에 의해 front의 값을 ((front + 1) mod 6)로 변경한 후 front가 가리키는 위치에서 데이터를 빼내어 삭제한다. 단, 공백 상태일 때에는 데이터 삭제가 이루어지지 않아 원형 큐의 상태가 변하지 않는다.<동 작>모든 유효 데이터 / front / rear
enqueue(2) → enqueue(5) → enqueue(7) → enqueue(10) → dequeue() → enqueue(11) → enqueue(15) → enqueue(17) → dequeue() → dequeue() → enqueue(20)
1
10, 11, 15, 17, 20 / 3 / 1
2
10, 11, 15, 20 / 3 / 1
3
10, 11, 15, 17, 20 / 4 / 2
4
10, 11, 15, 20 / 4 / 2
해설
연산 후 유효 데이터는 10, 11, 15, 20이고 front는 3, rear는 1이다.
enqueue(2), (5), (7), (10)으로 rear가 4, dequeue()로 front가 1이 된다. enqueue(11)로 rear가 5, enqueue(15)로 rear가 0으로 돌아온다.
이때 front와 (0 + 1) mod 6이 모두 1로 같아 포화 상태이므로 enqueue(17)은 무시된다. 이후 dequeue() 두 번으로 5와 7이 삭제되어 front가 3, enqueue(20)으로 rear가 1이 되어 위치 4, 5, 0, 1에 10, 11, 15, 20이 남는다.
- 10, 11, 15, 17, 20 / 3 / 1: 포화 상태에서 17은 삽입되지 않는다.
- 10, 11, 15, 17, 20 / 4 / 2: 17은 삽입되지 않으며 front는 3, rear는 1이다.
- 10, 11, 15, 20 / 4 / 2: 데이터는 맞지만 dequeue()가 세 번 수행되어 front는 3이고, 17이 무시되므로 rear는 1이다.
오류나 개정된 내용이 보이면 알려주세요