Queue 큐 python

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

이상 마칩니다ㅎㅎ