큐란 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 가장 먼저 나오는 FIFO(First In First Out)의 구조로 데이터를 저장하는 형식이다. 이러한 큐의 적용사례로는 놀이공원에서 놀이기구를 타기 위해 기다리는 손님들, 은행 대기 고객들 등이 있다. 주로 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다.
1.2. 큐 관련 용어 및 종류
- enqueue : 큐에 데이터를 넣는다. - dequeue : 큐에서 데이터를 꺼낸다.
1.2.1. 큐의 종류
선형큐 (Linear Queue) : 기본적인 큐, 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 앞으로 옮겨야된다.
원형큐 (Circle Queue) : 선형 큐 보완하기 위해 탄생. 아래 그림처럼 원형으로 돌면서 데이터가 채워지고 처음 들어온 데이터가 삭제되면(dequeue) Front인덱스가 다음 데이터로 이동하게된다. 선형큐에 경우 빈 자리를 직접 채워줘야 했지만 원형 큐는 자동으로 채워진다. 이때 다음 인덱스로 이동하는 식은 rear = (rear + 1 ) % size 이다
https://velog.io/@misun9283/Queue
우선순위 큐 (Prioirty Queue) : 우선순위 큐는 순서에 관계없이 큐에서 dequeue 될 때 우선순위에 맞게 dequeue된다.
LIFO (Last-In, First-Out) : dequeue했을 때 마지막으로 들어온 데이터가 가장 먼저 빠져나간다.
