다음은 C 언어를 사용하여 원형 큐(circular queue)의 삽입… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음은 C 언어를 사용하여 원형 큐(circular queue)의 삽입(enqueue)과 삭제(dequeue) 연산을 구현한 것이다.
int Q[8] = {0};
int front = 0;
int rear = 0;

void enqueue(int item)
{
rear = (rear + 1) % 8;
if (front == rear) {
printf("Queue is full.\n");
return;
}
Q[rear] = item;
}

int dequeue()
{
int item;
if (front == rear) {
printf("Queue is empty.\n");
exit(1);
}
else {
front = (front + 1) % 8;
item = Q[front];
Q[front] = 0;
return item;
}
}
front와 rear의 값이 0인 공백 큐에 6개의 값 1, 3, 2, 4, 8, 6을 차례대로 삽입하고, 여기에서 2개의 값을 삭제한 다음, 다시 3개의 값 5, 7, 9를 차례대로 삽입할 때, 배열 Q의 최종 모습은?
Q[0]Q[1]Q[2]Q[3]Q[4]Q[5]Q[6]Q[7]
1
07924865
2
24865790
3
79024865
4
90248657
해설

배열 Q의 최종 모습은 7, 9, 0, 2, 4, 8, 6, 5이다.

enqueue는 rear를 먼저 1 증가시킨 뒤 저장하므로 1, 3, 2, 4, 8, 6은 Q[1]~Q[6]에 들어가고 rear=6이 된다. dequeue 2회로 front가 2가 되며 Q[1], Q[2]는 0으로 지워진다.

이어서 5는 Q[7], 7은 (7+1)%8=0이므로 Q[0], 9는 Q[1]에 저장된다. 이때 rear=1, front=2로 가득 찬 상태가 아니다.

  • 0, 7, 9, 2, …, 5 배치: 7과 9를 지워진 칸 Q[1], Q[2]에 넣은 것으로, rear는 7 다음 0으로 이어진다.
  • 2, 4, 8, 6, 5, 7, 9, 0 배치: 원소를 앞으로 당겨 저장한 것으로, 원형 큐는 원소를 이동시키지 않는다.
  • 9, 0, 2, …, 7 배치: Q[0]부터 저장을 시작했다고 본 것으로, 이 구현은 rear를 먼저 증가시켜 Q[1]부터 저장한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기