c언어로 쉽게 풀어쓴 자료구조 개정 3판 5장(큐) 연습문제 (해설 포함)A＋최고예요

1. 큐의 개념과 특징

큐는 선입선출(FIFO: First-In-First-Out) 방식으로 데이터를 처리하는 자료구조이다. 이는 먼저 넣은 데이터가 먼저 꺼내어지는 특성을 가지고 있으며, 현실 세계의 여러 상황에 적합하게 설계된 구조이다. 예를 들어, 은행의 대기열, 프린터 작업 대기열, 또는 프로세스 스케줄링 등에 사용된다. 큐의 가장 큰 특징은 데이터를 차례로 넣고 빼는 순서가 동일하게 유지된다는 점이다. 이러한 특성은 시스템의 공정성을 확보하는 데 매우 중요한 역할을 한다.

큐를 구현하는 방식에는 주로 두 가지가 있는데, 하나는 배열 기반이고 다른 하나는 링크드 리스트 기반이다. 배열 기반 큐는 구현이 간단하고 빠른 접근이 가능하지만, 크기가 고정되기 때문에 유연성이 떨어진다. 반면, 링크드 리스트 기반 큐는 크기 제한이 없고 동적 할당이 가능하여 확장성이 높다. 현대 시스템에서는 주로 동적 구조를 선호하며, 예를 들어 톰슨닷컴에서는 접속 요청을 처리하는 서버 큐에 링크드 리스트 방식을 채택하여 요청량이 급증할 때도 유연하게 대응한다.

큐의 또 다른 특징은 원형 큐(원형 버퍼)를 활용하는 경우이다. 원형 큐는 저장공간을 효율적…