자료구조 02 : 큐 (queue)

운영체제, 인터넷 네트워킹에서 많이

쓰이기 때문에 잘 알고 있어야 하는

자료구조 중 하나이다.

 

구조(정책), 필수 용어에 대해 잘 알아둘

필요가 있으며 관련 lib.를 활용하지 않고 

큐의 정책을 이해하여 순수 코딩으로

조건문/반복문/함수를 활용하여 큐를

구현해 볼 수 있도록 연습하는 것을 권장한다.

 

큐 구조

가장 먼저 넣은 데이터를 가장 먼저

꺼낼 수 있는 구조를 큐라고 한다.

 

일반적인 큐는 먼저 줄 선 사람이 먼저 입장하는

것과 같이 줄을 서는 행위와 유사하다.

FIFO(First-in, First-out), LILO(Last-in, Last-out)

방식(정책)이라고도 하며 스택과는 정반대의 형태이다.

 

데이터를 넣을 때는 위와 같이

앞쪽부터 순서대로 들어가고,

출력될 때는 앞에서부터 출력되며

잔여 데이터가 따라 붙는다.

당연히 이 상태에서 데이터를 추가하면

남은 데이터 뒤부터 차례로 쌓이다.

 

 

알아둘 용어

FIFO 뜻 (위 참고)

Enqueue : 큐에 데이터를 넣는 기능

Dequeueu : 큐에 데이터를 꺼내는 기능

 

 

파이썬 큐 라이브러리

일반적인 큐의 기본적인 구조는

FIFO이지만 변형된 구조도 있다.

그 종류엔 우선순위 큐와 LIFO 큐가 있다.

 

Queue() : 가장 일반적인 큐 (FIFO)

LifoQueueu() : 변형(특이) 큐 LIFO 

★PriorityQueue() : 데이터를 넣을 때 각각의

데이터마다 우선순위를 같이 부여하여 데이터를

추출할 때 우선순위가 높은* 데이터부터 출력하게

하는 큐이다. 즉, 넣는 시간 순서가 아닌 부여한

우선순위에 따라 데이터를 추출하는 순서가

달라진다. 따라서 자료구조를 넘어 알고리즘에도

많이 쓰이는 큐 정책이니 잘 알아두는 것이 좋다.

 

참고로 대입할 때는 튜플 형태로 대입한다.

*우선순위가 높다 = 숫자가 작다.

ex_1위가 2위보다 우선순위가 높다.

import queue
data_queue = queue.PriorityQueue()

# 데이터 입력
data_queue.put((13,"strawberry"))
data_queue.put((1,"apple"))
data_queue.put((4,5))
data_queue.put((20,"fig"))

# 데이터 출력
data_queue.get()

output >>> (1, "apple")

 

 

면접 질문.

큐가 어디에 많이 쓰이나요??

운영체제에서는 멀티 태스킹을 위한

프로세스 스케쥴링 방식을 구현하기 위해서

많이 쓰인다. (운영체제에 대한 이해 필요)