[python] 큐

in Python on Queue


python에서 큐는 어떻게 사용할까?

큐(queue)는 선입선출, FIFO(First In First Out)기반의 자료구조다. 먼저 들어간게 먼저 나오는 것으로 매표소에서 사람들이 줄을 서면 먼저 선 사람이 먼저 표를 사고 줄에서 나오는 구조를 가지고 있다. 즉 큐를 사용하면 데이터를 추가한 순서대로 제거할 수 있기 때문에 스트리밍(streaming), 너비 우선 탐색(BFS) 등 개발할 때 많이 사용된다.

우선 파이썬으로 큐를 사용할 수 있는 방법으로는 크게 세 가지가 있다.

  1. list 사용
  2. queue 모듈 import
  3. deque import

list 사용

가장 간단한 방법이다. 범용 자료 구조인 list를 사용하면 큐의 동작을 이용할 수 있다.

  • 데이터 추가 : append(x), insert(index, x)
  • 데이터 삭제 : pop(index)
queue = [4,5,6]
queue.append(7)
queue.insert(0,3) // [3,4,5,6,7]

queue.pop() // 7
queue.pop(0) // 3

Queue

파이썬에서 큐를 사용하기 위해서는 queue 모듈의 Queue 클래스를 사용하면 된다. 이렇게 모듈에서 큐를 import 하는 것은 멀티 쓰레딩 환경에서 사용된다. 내부적으로 locking을 지원해서 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.

이 Queue는 방향성을 가지고 있지 않기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다. (큐의 앞, 뒤에서 원소를 넣고 빼내는 것을 구분하지 않고 오로지 큐의 앞에서만 원소를 빼기 때문이다.)

  • 데이터 추가 : put(x)
  • 데이터 삭제 : get()
from queue import Queue

que = Queue()
que.put(4)
que.put(5)
que.put(6)

que.get() // 4
que.get() // 5
que.get() // 6

성능

  • 데이터 추가/삭제 : O(1)
  • 데이터 접근 : O(N)

자세한 내용은 파이썬 공식 레퍼런스 를 참조하면 된다.

deque

처음에는 deque라는 단어만 봤을 때 dequeue라는 단어랑 비슷해 보여서 큐에서 원소를 빼는 건가 싶었지만 double-ended queue의 약자라고 한다. double-ended 라는 말에서 유추가 가능하겠지만 데이터를 양방향에서 추가하고 제거할 수 있다. 이 말은 앞의 Queue와는 다르게 방향성을 가지고 있다는 소리가 되겠다.

  • 데이터 삭제
    • 왼쪽(앞) : popleft()
    • 오른쪽(뒤) : pop()
  • 데이터 추가
    • 왼쪽 : appendleft(x)
    • 오른쪽 : append(x)
from collections import deque

queue = deque([1,2,3])
queue.append(4)
queue.append(5)
queue.appendleft(0) // [0,1,2,3,4,5]

queue.popleft() // 0
queue.pop() // 5

dddd