Queue 큐 python
큐는 FIFO(First Input First Out, 선입 선출)입니다. 가장 먼저 들어간 자료를 가장 먼저 꺼내게 되죠.
쉽게 예를 들면 음식점에서 기다리는 줄을 생각해보면, 먼저 기다린 사람이 먼저 입장하게 되죠
큐에 원소를 넣는 작업을 enqueue, 원소를 꺼내는 작업을 dequeue이라고 합니다.두 연산은 O(1)에 이루어져야 합니다.
Python에서 Queue를 다뤄보죠
python 2에서는 Queue라는 라이브러리가 따로 있습니다.
import Queue
queue = Queue.Queue()
queue.put(1) # push
queue.get() # pop |
https://github.com/KimJeongChul/algorithm-python/blob/master/data-structure/queue_python2.ipynb
python 3에서는 queue 라이브러리(Queue, LifoQueue, PriorityQueue)로 명시되어 있습니다.
https://github.com/KimJeongChul/algorithm-python/blob/master/data-structure/queue-python3.ipynb
Queue
put과 get을 이용해 데이터를 삽입하고 뽑습니다.
from queue import Queue
queue = Queue()
queue.put(1)
print("queue", queue.queue)
queue.put(2)
print("queue", queue.queue) # ('queue', deque([1, 2]))
queue.put(3)
print("queue", queue.queue) # ('queue', deque([1, 2, 3]))
queue.get()
print("queue", queue.queue) # ('queue', deque([2, 3])) |
LifoQueue
stack과 비슷한 구조로 후입선출 입니다.
from queue import LifoQueue
queue = LifoQueue()
queue.put(1)
print("queue", queue.queue)
queue.put(2)
print("queue", queue.queue) # ('queue', [1, 2])
queue.put(3)
print("queue", queue.queue) # ('queue', [1, 2, 3])
queue.get()
print("queue", queue.queue) # ('queue', [1, 2]) |
Priority Queue
우선 순위 큐로 데이터는 Tuple로 저장됩니다.
우선 순위는 Tuple의 첫 번째 값에 따라 오름차순으로 정렬되며, Tuple의 첫 번째 원소의 낮은 값 부터 빠져나갑니다.
from queue import PriorityQueue
queue = PriorityQueue()
queue.put((10, "mango"))
print("queue", queue.queue)
queue.put((4, "banana"))
print("queue", queue.queue)
queue.put((2, "watermelon"))
print("queue", queue.queue) # ('queue', [(2, 'watermelon'), (10, 'mango'), (4, 'banana')])
print("dequque", queue.get()) # ('dequque', (2, 'watermelon'))
print("queue", queue.queue) # ('queue', [(4, 'banana'), (10, 'mango')])
queue.put((3, "strawberry"))
print("queue", queue.queue) # ('queue', [(3, 'strawberry'), (10, 'mango'), (4, 'banana')])
print("dequque", queue.get()) # ('dequque', (3, 'strawberry'))
print("queue", queue.queue) # ('queue', [(4, 'banana'), (10, 'mango')]) |
Queue를 class로 구현한다면 List의 append와 pop(0)을 이용해서 구현 가능합니다.
class Queue(list):
enqueue = list.append # push, enquque
def dequeue(self):
return self.pop(0)
def is_empty(self):
if not self:
return True
else:
return False |
사용법
queue = Queue()
queue.enqueue(1)
print("queue", queue)
queue.enqueue(2)
print("queue", queue)
queue.enqueue(3)
print("queue", queue) # ('queue', [1, 2, 3])
queue.dequeue()
print("queue", queue) # ('queue', [2, 3]) |
list를 사용하지 않고 Node라는 class를 구현하여 만들어 본다면 다음과 같습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def is_empty(self):
if not self.head:
return True
else:
return False
def enqueue(self, data):
node = Node(data)
if self.is_empty():
self.head = node
self.tail = node
return
self.tail.next = node
self.tail = node
def dequeue(self):
if self.is_empty():
return None
result = self.head.data
self.head = self.head.next
return result
def element(self):
top = self.head
head = self.head
result = [head.data]
while head.next != None:
head = head.next
result.append(head.data)
self.head = top
return result |
사용법
queue = Queue()
queue.enqueue(1)
print("queue", queue.element())
queue.enqueue(2)
print("queue", queue.element())
queue.enqueue(3)
print("queue", queue.element()) # ('queue', [1, 2, 3])
queue.dequeue()
print("queue", queue.element()) # ('queue', [2, 3]) |
이상 마칩니다ㅎㅎ
