[Data Structure] Queue

Queue의 개념

컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식

Queue의 사용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

• BFS 구현
  • 처리해야 할 노드의 리스트를 저장하는 용도로 Queue를 사용
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
  • 노드를 접근한 순서대로 처리할 수 있음
• 캐시 구현
• 우선순위가 같은 작업 예약 (인쇄 대기열)
• 선입선출이 필요한 대기열 (티켓 카운터)
• 콜센터 고객 대기시간
• 프린터의 출력 처리
• 윈도우 시스템의 메시지 처리기
• 프로세스 관리

Python Queue

• List 이용
  • append()메소드와 pop()메소드를 이용하여 구현 가능
  • pop 연산의 시간 복잡도는 $O(N)$ 이어서 N이 커질 수록 연산이 매우 느려짐 ∴ 큐 자료구조 사용할 때 List는 추천하지 않음
    
• Deque 이용
  • from collections import deque를 이용하여 deque 라이브러리 import
  • append()메소드와 popleft()메소드를 이용하여 구현 가능
  • $O(1)$의 시간 복잡도를 갖기 때문에 List 자료 구조보다 성능이 훨씬 뛰어남
  • 단점 : 무작위 접근의 시간 복잡도가 $O(N)$이고, 내부적으로 linked list를 사용하고 있기 때문에 N번째 데이터에 접근하려면 N번의 순회가 필요함
• Queue 이용
  • from queue import Queue를 이용하여 queue 라이브러리 import
  • put() 메소드와 get() 메소드를 이용하여 구현 가능
  • Queue의 성능은 Deque의 성능과 동일
    • 데이터 추가/삭제 시간 복잡도 = $O(1)$
    • 데이터 접근 시간 복잡도 = $O(N)$임

➰ References

https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html
https://velog.io/@sossont/Python-Queue-자료구조-사용하기