참고
Queue
NOTE
Queue ⇒ FIFO (First in, First Out) 원칙에 기반한 선형 자료구조!
add, poll 함수 등으로 데이터를 추가/제거 한다.
Queue 사용사례
NOTE
•
OS CPU Scheduling
◦
운영 체제에서는 다양한 프로세스가 동시에 실행될 수 있도록 스케줄링을 한다.
◦
Prioirty Queue를 사용하며, 우선순위에 따라 프로세스를 관리하고 CPU에 할당한다.
•
프린터 대기열
◦
여러 문서나 파일을 프린트 할 때, 요청된 작업부터 순차적으로 프린트한다.
•
Breadth-First Search(BFS)
◦
너비 우선탐색 에서는 시작 노드부터 시작하여, 노드의 이웃을 먼저 탐색한다.
◦
큐는 이런 방식으로 노드를 순차적으로 저장하고 처리하는데 사용한다.
•
주문 처리 시스템
◦
전자 상거래 시스템에서 사용자의 주문은 순서대로 처리된다.
◦
주문이 들어올때마다 큐에 추가되고, 백엔드 시스템은 큐에서 순차적으로 처리한다.
•
Data Streaming
Packet Queue: [ Packet1 ] -> [ Packet2 ] -> [ Packet3 ]
(First In) (Last In)
Java
복사
◦
실시간 데이터 스트리밍 시스템에서는 데이터 패킷을 순서대로 처리해야 한다.
◦
이 때 큐를 사용하여 패킷들을 순차적으로 정리하고 처리할 수 있다.
•
Load Balancing
Request Queue: [ Req1 ] -> [ Req2 ] -> [ Req3 ] -> [ Req4 ]
Server1 Server2 Server1 Server2
Java
복사
◦
큐를 사용하여 들어온 요청을 여러 서버에 공평하게 분배한다.
◦
이를 통해 서버의 부하를 균등하게 분산하며, 각 요청(Req)가 큐에 들어가고 분배된다.
•
Messging
◦
Pub/Sub를 통해 메시지를 생성하고, 이를 시스템에 전달한다. 이 메시지는 큐에 저장된다.
◦
Sub의 대표적인 종류에는 RabbitMq, Kafka, ActiveMq등이 있다.
Queue의 종류와 특징
NOTE
선형 큐
•
가장 기본적인 큐의 형태이다.
순환 큐
•
배열을 기반으로 하며, 배열의 마지막 요소 다음에는 배열의 1번째 요소가 온다.
•
주요 이점으로는 공간을 재사용한다는 점
우선순위 큐
•
각 항목이 우선순위와 함께 저장되는 큐
•
큐에서 요소를 꺼낼 때 가장 높은 우선순위의 요소가 먼저 나온다.
•
Heap같은 특별한 자료구조를 사용해야 구현이 가능하다.
•
ex) 응급실의 환자 대기열, 운영체제 프로세스 스케쥴링
Double-enabled Queue(Dequeue, 데크)
•
양쪽 끝에서 추가/제거 모두 가능하다.
•
스택과 큐의 특징을 모두 가지고 있다.
•
배열 또는 연결 리스트로 구현이 가능하다.