Python 자료구조

큐 Queue

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  - 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/

용어

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능

참고

• Visualgo

Python 라이브러리를 활용한 Queue

import queue

Queue()

# 일반적인 FIFO Queue
data = queue.Queue()

# Enqueue
data.put("MSN")
data.put(12345)

# Queue Size
data.qsize()
>>> 2

# Dequeue
data.get()
>>> "MSN"
data.get()
>>> 12345

# Queue Size
data.qsize()
>>> 0

LifoQueue()

# LIFO = Last-In, First-Out
data = queue.LifoQueue()

# Enqueue
data.put("MSN")
data.put(12345)

# Dequeue
data.get()
>>> 12345
data.get()
>>> "MSN"

PriorQueue()

# 데이터에 우선순위를 부여
data = queue.PriorityQueue()

# Enqueue
data.put(42, "MSN")
data.put(15, 12345)
data.put(20, 'Sea')

# Dequeue
data.get()
>>> (15, 12345)
data.get()
>>> (20, 'Sea')
data.get()
>>> (42, "MSN")

연습

• 리스트 변수로 큐를 다루는 Enqueue, Dequeue 기능 구현

queue_list = []

def enqueue(data):
	queue_list.append(data)
    
def dequeue():
	data = queue_list[0]
    del queue_list[0]
    return data

• LifoQueue() 기능 구현

queue_list = []

def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[-1]
    del queue_list[-1]
    return data

• PriorQueue() 기능 구현

queue_list = []

def enqueue(index, data):
    queue_list.append((int(index),data))
    
def dequeue():
    data = queue_list.sorted(key=lambda x:x[0])
    del queue_list[queue_list.index(data)]
    return data