Queue

Stack vs. Queue 스택(Stack)과 큐(Queue)는 컴퓨터 과학에서 널리 사용되는 선형 자료구조로, 데이터의 저장 및 처리 방식에서 차이가 있다. 스택(Stack) 스택은 후입선출(LIFO, Last-In First-Out) 방식의 자료구조로, 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입과 삭제는 모두 스택의 **탑(top)**에서 이루어진다. 주요 연산: 삽입(Push): 데이터를 스택의 탑에 추가한다. 삭제(Pop): 스택의 탑에 있는 데이터를 제거하고 반환한다. 탑 확인(Peek): 스택의 탑에 있는 데이터를 제거하지 않고 확인한다. 비어있는지 확인(IsEmpty): 스택이 비어 있는지 여부를 확인한다. 큐(Queue) 큐는 선입선출(FIFO, First-In First-Out) 방식의 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거된다. 데이터의 삽입은 **후단(Rear)**에서, 삭제는 **전단(Front)**에서 이루어진다. ...

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 구현 예시: ...