queue

• queue module의 Queue 사용

from queue import Queue
# 혹은
import queue

• https://docs.python.org/3/library/queue.html

---

• list는 배열처럼 random access에 최적화된 자료구조 이기 때문에, list를 가지고 queue 처럼 사용하는 것은 성능적으로 불리함
  • pop(0), insert(0,x)의 시간복잡도는 $O(N)$ 임!! (충격적이게도..?)

---

Queue생성

queue.Queue([maxsize=N])

• class queue.Queue([maxsize=0]): FIFO 큐를 생성한다.
  • args
    • maxsize: queue의 maxsize를 결정한다. (default: 0, infinite)
  • return
    • Queue object

from queue import Queue

Q=Queue()

혹은

import queue

Q=queue.Queue(maxsize=10)

---

push

Queue.put()

• Queue.put( )
  • args
    • item: push할 item
    • [block=True]: 이 push를 할 때, block할 것인가?
    • [timeout=None]: block이라면 timeout은 얼마인가?

• 우리가 아는 Queue push는 여기서 queue.put()임
• block=True, timeout=None 시, put을 하면, free slot이 생길 때 까지 block된다.

from queue import Queue

if __name__ == '__main__':
    Q=Queue
    Q.put(5)
    
----

import queue

if __name__=='__main__':
    Q=queue.Queue()
    Q.put(5)

---

from queue import Queue

if __name__ == '__main__':
    Q=Queue(1)
    Q.put(1)
    Q.put(2) # 여기서 Q가 free slot이 생길 때 까지 블록됨
    
-----
import queue

Q=queue.Queue(1)
Q.put(1)
Q.put(2) # block!
    

---

from queue import Queue

if __name__ == '__main__':
    Q=Queue(1)
    Q.put(1)
    Q.put(2,block=False) # 여기서 queue.Full Exception 발생
    
-----
import queue

Q=queue.Queue(1)
Q.put(1)
try: 
    Q.put(2, block=False)
except queue.Full:
    print("Queue is full!")
    

---

Queue.put_nowait()

• Queue.put_nowait(): Queue.put(item, Timeout=False)와 같다.
  • args
    • item: push할 item

---

pop

Queue.get()

• 우리가 아는 Queue pop은 queue.get()임
  • args
    • [block=True]: 이 pop를 할 때, block할 것인가?
    • [timeout=None]: block이라면 timeout은 얼마인가?

• block=True, timeout=None 시, get을 하면, return slot이 생길 때 까지 block된다.

from queue import Queue

if __name__ == '__main__':
    Q=Queue
    Q.put(5)
    print(Q.get())

# ==== 출력 ==== #
5

-------
import queue

Q=Queue
Q.put(1)
try:
    Q.get(block=True)
except queue.Empty:
    print("Empty!")

---

Queue.get_nowait()

• Queue.get(False)와 같다.

import queue

Q=queue.Queue(maxsize=1)
try:
    item=Q.get_nowait() # 아무 것도 없는데 get을 하면 원래 block! 인데, nowait()이라 바로 익셉션
except queue.Empty:
    print("Queue is empty")
else:
    print(item)

# ==== 출력 ==== #
Queue is empty
    
    

---

size

Queue.qsize()

Queue.empty()

• Queue.empty()
  • args
  • return
    • True: 큐가 비어 있음
    • False: 큐가 비지 않음

---

Queue.full()

• Queue.full()
  • args
  • return
    • True: 큐가 가득 참
    • False: 큐가 가득 차진 않음

---

done?

Queue.task_done()

• Queue.task_done()

• 앞서 큐에 넣은 작업이 완료되었음을 나타냄
• 큐 consumer thread에서 사용된다.
• 작업을 꺼내는 데 사용되는 get()마다, 후속 task_done() 호출은 작업에 대한 처리가 완료되었음을 큐에 알려준다.

join()이 블로킹 중이면, 모든 항목이 처리되면 (큐로 put()된 모든 항목에 대해 task_Done() 호출이 수신되었음을 뜻함) 재개된다.

큐에 있는 항목보다 더 많이 호출되면 ValueError 를 발생시킨다.

---

Queue.join()

• 큐의 모든 항목을 꺼내서 처리할 때까지 블록한다.

• 완료되지 않은 작업 카운트는 항목이 큐에 추가될 때마다 올라간다.

• consumer thread가 task_done() 을 호출해서 항목을 꺼내고 작업이 모두 완료되었음을 나태낼 때마다 카운트가 내려간다.

• 완료되지 않은 작업 카운트가 0으로 떨어지면, join()은 블록 해제된다.

def worker():
    while True:
        item=q.get()
        if item is None:
            break
        do_work(item)
        q.task_done()

q=queue.Queue()
threads=[]

for i in range(num_worker_threads):
    t=threading.Thread(target=worker)
    t.start
    threads.append(t)


for item in source():
    q.put(item)
    
q.join()

for i in range(num_worker_threads):
    q.put(None)
for t in threads:
    t.join()

---

exception

queue.Empty

queue.Full

---

Python으로 BFS 구현시 주의점

• 'BFS'에서 필히 queue를 사용할 것인데...
• 의도: '00' pop, '01' pop 인데, '01' '01'만 Pop된다.
  

---

해결 방법

• 재사용 금지
• 즉석에서 객체를 만들어 push 할 것