[컴공,자료구조2] 6장 연습문제

1. 큐(Queue)의 개념과 구현

큐(Queue)는 선입선출(FIFO, First-In-First-Out) 원칙을 기반으로 하는 자료구조이다. 즉, 큐에 데이터를 넣은 순서가 먼저 나오게 되는 구조다. 이는 은행 창구의 대기열이나 인쇄 작업의 인쇄 큐 등 일상생활에서 흔히 볼 수 있는 현상을 모델링한 것이다. 큐는 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나며, 이를 각각 `rear(뒤쪽)`, `front(앞쪽)`이라 부른다. 데이터를 넣는 연산은 enqueue(삽입), 데이터를 제거하는 연산은 dequeue(삭제)라고 하며, 이를 통해 큐는 작업의 순서를 유지하는 역할을 수행한다.

큐를 구현하는 방법은 크게 배열(Array)과 링크드 리스트(연결리스트)를 사용하는 방식이 있다. 배열 기반의 큐는 간단하고 구현이 용이하지만, 크기를 미리 정해야 하며, 원형 큐로 구현해야 공간 낭비를 막을 수 있다. 반면, 링크드 리스트를 이용한 큐는 크기 제한이 없고 동적 할당이 가능하나, 포인터를 사용하기 때문에 구현이 더 복잡하다. 예를 들어, 병원에서 환자가 들어와 기다리는 대기열을 생각할 수 있는데, 환자들이 순서에 따라 진료를 받기 위해 줄을 서듯이 큐는 데이터가 자연스럽게 순서대로 처…