자료구조 큐

 큐 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

visualgo.net/en/list(큐 자료구조 이해하기)

 

파이썬에서 queue 자료 구조를 사용하기 위해서

 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

일반적인 큐 외에 다양한 정책이 적용된 큐들이 있음

Queue()

import queue

# queue 의 정책 

data_queue = queue.Queue()
# queue 라이브러리에서 Fifo Queue() 클래스 사용

# 데이터를 넣기 위해서 put
data_queue.put("funcoding")
data_queue.put(1)

#queue의 크기 구하기 qsize()
data_queue.qsize()

#데이터를 꺼내기 get
data_queue.get()

get()을 실행하면 처음에 넣었던 funcoding이 출력됨

 

 

 

LifoQueue()

import queue

# queue 의 정책 

data_queue = queue.LifoQueue()
# queue 라이브러리에서 Lifo Queue() 클래스 사용

# 데이터를 넣기 위해서 put
data_queue.put("funcoding")
data_queue.put(1)

#queue의 크기 구하기 qsize()
data_queue.qsize()

#데이터를 꺼내기 get
data_queue.get()

get()을 실행하면 마지막에 넣었던 1이 출력됨

 

 

PriorityQueue()

각각의 데이터에 우선순위 번호를 같이 넣음. 추출할때 우선순위가 높은 데이터를 추출한다.

import queue

data_queue = queue.PriorityQueue()

#튜플형식으로 데이터를 넣는다. 
#(우선순위, 데이터) 우선순위는 낮을수록 높음
data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))

data_queue.qsize()
3

data_queue.get()
(5,1)

data_queue.get()
(10,"korea")

 

 

참고: 어디에 큐가 많이 쓰일까?

운영체제에서 멀티태스킹을 구현하기 위해서 프로세스 스케줄링을 구현할때 많이 쓰인다.

운영체제에서 프로세스를 스케줄링하는 방식을 이해하는 것이 중요하다.

운영체제와 함께 이해를 하는 것이 좋다.

 

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 (운영체제 참조)

큐의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

 

연습1: 리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현해보기

queue_list = list()
def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]; #선입선출 되어야 하기떄문에 0번이 젤 첨 들어간 데이터
    del queue_list[0] #추출된 데이터는 리스트에서 삭제해주어야 한다. del명령으로 삭제한다.
    return data

데이터 만들기

for index in range(10):
    enqueue(index)

len(queue_list)

10 (0~9)

 

dequeue()

10번을 실행한다고 했을때 출력값은 

0

1

2

3

4

...

9