Queue

Circular Queue (Circular Buffer) 이는 선형 큐의 확장된 버전으로, 데이터를 효율적으로 저장하고 관리하는 특정한 방식을 제공한다. Circular Queue는 마지막 요소가 첫 번째 요소와 연결되어 원형 구조를 형성하는 큐 데이터 구조이다. 이는 ‘Ring Buffer’라고도 불리며, 고정 크기의 배열을 사용하여 데이터를 연속적인 루프로 저장한다. https://www.geeksforgeeks.org/what-is-circular-queue-circular-queue-meaning/ 특징 원형 구조: 마지막 위치가 첫 번째 위치와 연결되어 있다. FIFO (First In First Out) 원칙을 따른다. 두 개의 포인터: 큐의 front와 rear를 추적하는 두 개의 포인터를 사용한다. 고정 크기: 초기화 시 크기가 설정되며, 이후 변경이 어렵다. 장점 메모리 효율성: 선형 큐의 주요 한계인 메모리 낭비 문제를 해결한다. 빠른 연산: 삽입과 삭제 연산의 시간 복잡도가 O(1)이다. 공간 재사용: 큐의 앞부분이 비어있을 때 재사용이 가능하다. 캐시 지역성: 연속된 메모리 사용으로 CPU 캐시 성능이 향상된다. 단점 크기 제한: 고정 크기로 인해 오버플로우와 데이터 손실 가능성이 있다. 구현 복잡성: 선형 큐보다 구현이 복잡하다. 디버깅 어려움: 원형 구조로 인해 디버깅이 어려울 수 있다. 동적 크기 조정의 어려움: 크기를 동적으로 조정하기 어렵다. 응용 CPU 스케줄링: 운영 체제에서 프로세스 관리에 사용된다. 트래픽 관리 시스템: 교차로에서의 효율적인 흐름 제어에 활용된다. 메모리 관리: 운영 체제의 메모리 관리에 사용된다. 스트리밍 서비스: 오디오 및 비디오 스트리밍에 활용된다. 네트워크 패킷 관리: 라우터와 스위치에서 패킷 데이터 처리에 사용된다. 동작 원리 초기화: front와 rear 포인터를 -1로 설정한다. 삽입(Enqueue): 큐가 가득 찼는지 확인한다. rear 포인터를 원형으로 증가시킨 ((rear + 1) % size). 새 요소를 rear 위치에 삽입한다[11]. 삭제(Dequeue): 큐가 비어있는지 확인한다. front 위치의 요소를 반환한다. front 포인터를 원형으로 증가시킨다 ((front + 1) % size). 구성 요소 배열: 데이터를 저장하는 고정 크기의 배열. front 포인터: 큐의 첫 번째 요소를 가리킨다. rear 포인터: 큐의 마지막 요소를 가리킨다. size: 큐의 최대 크기를 나타낸다. 구현 방식 JavaScript를 사용한 Circular Queue 구현 예시: ...