[알고리즘] 스택/큐 관련 Python module

※ 파이썬 내장모듈에서는 따로 스택 라이브러리가 존재하지 않는다.

✅ Collections의 deque 모듈

※ deque : 양방향 큐, 큐의 전단(front)와 후단(rear)에서 모두 삽입 및 삭제 가능

• Stack에서는 List나 deque나 시간 복잡도 면에서 별 차이 없음
• Queue에서는 List를 이용해 구현할 경우 O(N), deque으로 구현할 경우 O(1)
• 중간 요소를 삽입, 수정, 삭제하는 경우는 deque보다 List를 추천

from collection import deque

dq = deque()  #or deque(기존 리스트)

dq.append() # 덱의 오른쪽에 원소 삽입
dq.appendleft() # 덱의 왼쪽에 원소 삽입
dq.insert(i,e)  # i번째에 e삽입
dq.extend(리스트)  # 오른쪽에 리스트 삽입
dq.extendleft(리스트)  # 왼쪽에 리스트 삽입
dq.popleft() # 왼쪽 원소 제거 및 반환
dp.pop() # 오른쪽 원소 제거 및 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) # x와 같은 원소의 개수를 계산
dp.reverse()  # 덱 요소를 뒤집음
list(dp) # dp를 리스트로 사용

✅ Queue 모듈

• Thread 환경을 위해 만들어져있어 일반적인 상황에서 사용은 권장되지 않는다.
• Queue() : 일반적인 큐
• LifoQueue() : 나중에 입력된 데이터가 먼저 출력 (스택)
• PriorityQueue() : 데이터마다 우선순위를 넣어, 우선순위가 높은 순으로 출력
  • put(), get() 함수의 시간 복잡도는 O(log n)

from queue import Queue
from queue import LifoQueue
from queue import PriorityQueue

Q = Queue()
L = LifoQueue()
P = PriorityQueue()

Q.put() # 데이터 삽입 (뒤부터)
Q.get() # 데이터 삭제 및 반환
Q.qsize() # 요소 개수 (= len)

L.put() # 데이터 삽입 (뒤부터)
L.get() # 데이터 삭제 및 반환 (뒤부터)
L.qsize() # 요소 개수

P.put((1, "a"))
P.put((3, "c"))
P.put((2, "b"))
P.get() # (1, "a")
P.get() # (2, "b")
P.qsize() # 요소 개수
P.empty() # 원소가 들어있는지 확인 (비어있으면 True)

# 위의 결과를 역순으로 반환하고 싶다면,
P.put((-1, "a"))
P.put((-3, "c"))
P.put((-2, "b"))
print(P.get()[1])  # "c"
print(P.get()[1])  # "b"

 


참고
https://mong9data.tistory.com/36
https://cocobi.tistory.com/204