[Algorithm][Python] 자료구조: 큐(queue)

큐 (Queue)

1. 큐 구조

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

• 출처: http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

2. 알아둘 용어

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능
• Visualgo 사이트에서 시연해보며 이해하기 (enqueue / dequeue 만 클릭) : https://visualgo.net/en/list

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

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

3.1. Queue() 로 큐 만들기 (가장 일반적인 큐, FIFO)

import queue

data_queue = queue.Queue() # 라이브러리로 일반적인 Queue()를 생성해 준다. 생성자.

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() # 2

data_queue.get() # 'funcoding'

data_queue.qsize() # 1

data_queue.get() # 1

• queue.put() : 큐에 요소를 추가. (enqueue)
• queue.get() : 맨 뒤에 요소가 나옴. (dequeue)
• queue.qsize() : 큐의 길이를 나타냄

3.2. LifoQueue() 로 큐 만들기 (LIFO. Last-In, First-Out)

• LIFO 이면 스택아닌가? 왜 큐로 정의했을까 ?

import queue
data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1) # ["funcoding", 1]

data_queue.qsize() # 2

data_queue.get() # 1 나중에 들어간놈이 가장 먼저 나감.

3.3. PriorityQueue() 로 큐 만들기

• 우선순위가 정해진 큐.
• 우선순위가 높을수록 (숫자는 낮을수록?) 먼저 dequeue 됨.

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')

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

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 (운영체제 참조) 큐의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 이해해 두는것이 좋음

4. 프로그래밍 연습

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

queue_list = list() # 빈 배열 생성하기

def enqueue(data):
	queue_list.append(data) # enqueue 함수 정의하기

def dequeue():
	data = queue_list[0] # 0번째 요소를 data 에 할당하기
	del queue_list[0] # queue_list 0번째 요소 삭제하기
	return data # 삭제한 값 리턴하기

for index in range(10):
	enqueue(index) # index 값을 enqueue 하기

len(queue_list) # 10

dequeue() # 0