[자료구조] 11. 큐의 응용

1. 원형 큐와 데크

1) 원형 큐(Circular Queue)

• 순차 큐의 단점을 보완한 큐의 한 형태로, 배열의 처음과 끝을 연결하여 원형으로 구성됨.

• 개념적으로 원형이므로 데이터를 이동시키지 않고 rear 포인터를 조정하여 삽입 가능.

 

논리적 구조

• 초기 상태에서는 front = rear = -1
• front는 첫 번째 원소의 앞을, rear는 마지막 원소를 가리킴.

 

순차 큐 vs 원형 큐

• 순차 큐: rear = rear + 1, front = front + 1
• 원형 큐: rear = (rear + 1) mod n, front = (front + 1) mod n

 

2) 데크(Deque: Double-Ended Queue)

• 양쪽 끝에서 삽입과 삭제가 가능한 큐의 특수한 형태.

 

추상 자료형(ADT)

• add_front(e), delete_front(), add_rear(e), delete_rear() 등 다양한 연산 제공.

 

구현 방법

• 배열 기반: 인덱스 관리 필요, 순서 변화로 비효율적.
• 연결 리스트 기반: 이중 연결 리스트 사용 시 효율적.

 

 

 

2. 큐의 응용

1) 응용 분야

• 시뮬레이션: 은행 대기열, 비행기 이착륙 등 현실 문제 해결.

• 버퍼링: 운영체제의 작업 큐, 프린터 버퍼 등 속도 차이 보정.

• 동영상 스트리밍: 데이터 패킷을 저장 후 재생(버퍼링).

 

2) 직·간접적인 활용

• 직접적 응용: 입력 버퍼, 데이터 패킷 처리, 프린터 큐 등.

• 간접적 응용: 알고리즘 설계 및 다양한 데이터 처리에 활용.

 

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.