[algorithm] Queue (Python)

Queue

• 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조 (선입선출) (FIFO)
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태
• ex) 은행 창구, 터널 등

 

큐 구현 예제

파이썬에서는 큐를 구현할 때 deque를 사용하여 구현한다.

list자료형으로 기능적으로는 큐를 구현할 수 있지만 시간복잡도가 더 높아서 비효율적으로 동작한다.

from collections import deque

queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

# output
>>> deque([3, 7, 1, 4])
>>> deque([4, 1, 7, 3])