큐(Queue)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

웹 개발

대상자

• 프로그래밍 초보자 및 중급자
• 자료구조, 알고리즘 학습자
• JavaScript 기반 웹 개발자
• 난이도: 중간 (이론과 실습 예제 포함)

핵심 요약

• 큐(Queue)는 FIFO(First In, First Out) 원칙을 따르는 자료구조로, Enqueue와 Dequeue 연산이 핵심
• JavaScript에서 큐는 FRONT와 REAR 포인터로 구현되며, enqueue()와 dequeue() 메서드로 관리
• 시간 복잡도: enqueue()는 O(1), dequeue()는 O(n) (배열 기반 구현 시)
• 실용적 활용: CPU 스케줄링, 메시지 큐, 네트워크 패킷 관리 등 다양한 분야에서 사용

섹션별 세부 요약

1. 큐의 개념과 원칙

• FIFO 원칙에 따라 먼저 추가된 항목이 먼저 제거됨
• 예시: 티켓 구매 대기 줄, Enqueue는 끝에 추가, Dequeue는 앞에서 제거
• 큐 연산: IsEmpty, IsFull, Peek 등

2. 큐의 구현 방식

• FRONT와 REAR 포인터로 큐 관리

- FRONT는 첫 번째 요소, REAR는 마지막 요소를 가리킴

- 초기값: FRONT와 REAR는 -1로 설정

• JavaScript 예제 코드:

```javascript

class Queue {

constructor(maxSize) {

this.items = new Array(maxSize);

this.maxSize = maxSize;

this.front = -1;

this.rear = -1;

}

}

```

3. 큐의 시간 복잡도

• 배열 기반 큐:

- enqueue()는 끝에 추가하므로 O(1)

- dequeue()는 앞에서 제거하므로 O(n) (배열 이동 필요)

• 순환 큐(Circular Queue): 비어 있는 공간을 활용해 효율성 향상

4. 큐의 실용적 활용 사례

• CPU 스케줄링: FCFS, Round Robin 알고리즘
• 메시지 큐: RabbitMQ, Kafka, AWS SQS
• 네트워크 패킷 관리: 라우터, 스위치에서 패킷 저장
• 웹 개발: I/O 버퍼, 스트림, 파일 I/O

결론

• 큐는 FIFO 원칙을 기반으로 한 자료구조로, 실시간 시스템, 네트워크, 웹 개발 등 다양한 분야에서 핵심 역할
• JavaScript에서 배열 기반 큐 구현 시 enqueue()는 O(1)이지만 dequeue()는 O(n)으로, 순환 큐(Circular Queue)를 통해 공간 효율성 향상 가능
• 실무에서는 메시지 큐 시스템(RabbitMQ, Kafka 등)을 활용해 비동기 통신을 관리하는 것이 일반적