Queue(큐)

개념

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 형식의 자료 구조

LIFO(Last In First Out)
가장 최근에 스택에 추가한 항목(top)이 가장 먼저 제거될 항목이다.

이는 알고리즘 구현시 임시 목록에 객체를 추가한 다음 나중에 목록에서 객체를 꺼내려고 할 때 필요하다.

연산

• push(item) : item 큐에 추가한다.
• pop() : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다.
• front() : 큐의 가장 앞에 있는 정수를 출력한다.
• back() : 큐의 가장 뒤에 있는 정수를 출력한다.
• empty() : 큐가 비어 있으면 true
• size() : 큐의 크기를 반환한다.

사용 사례

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

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

💡 참고 포스팅

[자료구조] 큐(Queue)란
C++ 큐 자료구조