20230720 [자료구조] 큐(queue)

큐(queue)란?

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식이다.

나중에 집어 넣은 데이터가 먼저 나오는 스택(https://velog.io/@u-ryu-00/20230708-자료구조-스택stack)과는 반대되는 개념이다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.

선입 선출(先入先出) 또는 FIFO(first in, first out)

먼저 온 것은 먼저 처리되고, 처리가 끝날 때까지 다음 것은 대기 상태에 놓이게 된다.

용어 정리

• put : 큐에 자료를 넣는 것
• get : 큐에서 자료를 꺼내는 것
• front : 데이터를 get할 수 있는 위치
• rear : 데이터를 put할 수 있는 위치
• 오버플로우(Overflow) : 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우 (put할 수 없는 경우)
• 언더플로우(Underflow) : 큐가 비어 있어 자료를 꺼낼 수 없는 경우 (get할 수 없는 경우)

종류

큐에는 선형과 환형이 있다.