이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을
오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
● 잔재미코딩 유투브 오픈
[구독해보기]
5. 대표적인 데이터 구조4: 큐 (Queue)¶
- 줄을 서는 행위와 유사
- 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
- 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
- FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대
알아둘 용어¶
- Enqueue: 큐에 데이터를 넣는 기능
- Dequeue: 큐에서 데이터를 꺼내는 기능
- Visualgo 사이트에서 시연해보며 이해하기 (enqueue/dequeue 만 클릭해보며): https://visualgo.net/en/list
파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기¶
- queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
- 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
- Queue(): 가장 일반적인 큐 자료 구조
- LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택과 유사 방식)
- PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력
Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))¶
In [123]:
# 큐 만들기
import queue
data_queue = queue.Queue()
In [124]:
# 데이터 넣기
data_queue.put("korea")
data_queue.put(1)
In [125]:
# 큐 사이즈 확인하기
data_queue.qsize()
Out[125]:
In [126]:
# 데이터 꺼내기
data_queue.get()
Out[126]:
In [127]:
# 데이터 꺼내지면 큐 사이즈도 줄어듬
data_queue.qsize()
Out[127]:
In [128]:
data_queue.get()
Out[128]:
LifoQueue()로 큐 만들기 (LILO(Last-In, Last-Out))¶
In [129]:
# LifoQueue 만들기
import queue
data_queue = queue.LifoQueue()
In [130]:
# 데이터 넣기
data_queue.put("korea")
data_queue.put(1)
In [131]:
# 데이터 꺼내기
data_queue.get()
Out[131]:
PriorityQueue()로 큐 만들기¶
In [132]:
# LifoQueue 만들기
import queue
data_queue = queue.PriorityQueue()
In [133]:
# 데이터 넣기
data_queue.put((10, "korea")) # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함
data_queue.put((5, 1)) # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함
data_queue.put((15, "china")) # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함
In [134]:
# 데이터 꺼내기
data_queue.get() # <-- 우선순위값이 가장 낮은 데이터 순으로 출력 (1순위가 2순위보다 우선순위가 높죠!)
Out[134]:
In [135]:
# 데이터 꺼내기
data_queue.get()
Out[135]:
프로그래밍 연습
다음 추상 클래스를 상속받아서 리스트변수로 큐(FIFO) 클래스 만들어보기
다음 추상 클래스를 상속받아서 리스트변수로 큐(FIFO) 클래스 만들어보기
# 추상 클래스 만들기
from abc import *
class AbstractQueue(metaclass=ABCMeta):
@abstractmethod
def enqueue(self, data): # 데이터의 추가
raise NotImplemented
@abstractmethod
def dequeue(self): # 데이터의 꺼내오기
raise NotImplemented
프로그래밍 연습
위 코드에서 큐 타입에 따라 FIFO, LILO 큐를 만들 수 있는 클래스 만들어보기
위 코드에서 큐 타입에 따라 FIFO, LILO 큐를 만들 수 있는 클래스 만들어보기
In [136]:
from abc import *
class AbstractQueue(metaclass=ABCMeta):
@abstractmethod
def enqueue(self, data): # 데이터의 추가
raise NotImplemented
@abstractmethod
def dequeue(self): # 데이터의 꺼내오기
raise NotImplemented
In [137]:
class DaveQueue(AbstractQueue):
def __init__(self):
self.items = list()
def enqueue(self, data):
self.items.append(data)
def dequeue(self):
data = self.items[0]
del self.items[0]
return data
dave_queue = DaveQueue()
for num in range(10):
dave_queue.enqueue(num)
print (dave_queue.dequeue())
프로그래밍 연습
객체 생성시 큐 타입을 FIFO, LILO로 지정할 수 있는클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)
객체 생성시 큐 타입을 FIFO, LILO로 지정할 수 있는클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)
프로그래밍 연습
객체 생성시 큐 타입을 FIFO, LILO, PriorityQueue까지 지정할 수 있는 클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)
객체 생성시 큐 타입을 FIFO, LILO, PriorityQueue까지 지정할 수 있는 클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)
In [139]:
from abc import *
class AbstractQueue(metaclass=ABCMeta):
@abstractmethod
def enqueue(self, data): # 데이터의 추가
raise NotImplemented
@abstractmethod
def dequeue(self): # 데이터의 꺼내오기
raise NotImplemented
import queue
class QueueSet(AbstractQueue):
def __init__(self, type):
if type == 1:
self.data_queue = queue.Queue()
elif type == 2:
self.data_queue = queue.LifoQueue()
else:
self.data_queue = queue.PriorityQueue()
def enqueue(self, data):
self.data_queue.put(data)
def dequeue(self):
return self.data_queue.get()
fifo_queue = QueueSet(1)
for num in range(10):
fifo_queue.enqueue(num)
for index in range(10):
print (fifo_queue.dequeue())
lilo_queue = QueueSet(2)
for num in range(10):
lilo_queue.enqueue(num)
for index in range(10):
print (lilo_queue.dequeue())
priority_queue = QueueSet(3)
for num in range(10):
priority_queue.enqueue((1, num))
for index in range(10):
print (priority_queue.dequeue())