[Data Structure] 큐(Queue)

야구를 보러가거나 놀이기구를 기다릴때, 기다린 순서대로 먼저 탄다. 큐를 줄을 서는 것으로 생각하면 된다.

 

큐

데이터가 논리적(물리적 x)로 저장되어 있는 자료구조

chunk라는 단위로 내부적으로 저장

FIFO(First In First Out)자료구조이다.

 

연산

Enqueue: 큐에 데이터를 넣는다.

Dequeue: 큐에 데이터를 꺼낸다.

 

 

 

시간복잡도

i번째 데이터 접근	O(N)
x라는 데이터 탐색	O(N)
맨 앞 데이터 접근(peek)	O(1)
데이터 추가(Enqueue)	O(1)
데이터 추가(Dequeue)	O(1)

 

사례

CPU 스케쥴링

운영체제에서 여러 프로세스가 CPU를 할당받으려고 할때, 큐에 추가된다.

 

네트워크 패킷

라우터에서 데이터 패킷이 들어오는 순서대로 큐에 저장되고, 들어온 순서에 맞춰서 전송한다.

 

배치 처리(Batch Processing)

한 번에 많은 양을 처리하거나 여러 개의 작업을 모아서 처리하는 방식인데, 여기에서 여러 개의 작업을 저장할 때, 큐를 사용해 가장 먼저 들어온 작업을 처리한다.