큐는 선입선출 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조이다.
이를, FIFO(First in first out)이라고도 하고 선입선출이라고도 한다.
큐를 쉽게 이해하기 위해서 실생활에서 예를 하나 찾아보면, 공용 화장실을 생각해보면 쉽게 이해가 되실 거 같습니다. 누군가 먼저 화장실 안에 들어가서 볼일을 보고 있을 때, 뒤에 온 사람들은 먼저 온 순서대로 대기하고, 먼저 온 사람이 볼일을 끝내면 다음 사람이 들어가는 것이 자료구조 큐의 형태입니다.
주요 연산으로는 put과 get이 있는데, put은 큐에 새로운 데이터를 추가하는 연산이고, get은 큐에서 가장 오래된 데이터를 추출하는 연산이다.
데이터가 큐의 크기보다 많아진 경우를 오버플로우(overflow), 더 이상 추출할 데이터가 없는 경우를 언더플로우(underflow)라고 한다.
종류
선형 큐
막대 모양의 큐, 데이터 입/출력 시 모든 자료를 한 칸씩 옮겨야한다는 단점이 있다.
큐의 전단과 후단을 이용하여 입/출력 시의 문제를 해결 할 수 있지만, 입/출력을 하면 할 수록 가용 공간이 줄어드는 문제가 발생한다.